We survey two aspects of mixed-integer nonlinear programming which have attracted less attention (so far) than solution methods, solvers and applications: namely, whether the class of these problems can be solved algorithmically, and, for the subclasses which can, whether they are hard to solve. We start by reviewing the problem of representing a solution, which is linked to the correct abstract computational model to consider. We then cast some traditional logic results in the light of mixed-integer nonlinear programming, and come to the conclusion that it is not a solvable class: instead, its formal sentences belong to two different theories, one of which is decidable while the other is not. Lastly, we give a tutorial on computational complexity and survey some interesting hardness results in nonconvex quadratic and nonlinear programming.
Accepté le :
DOI : 10.1051/ro/2018036
Keywords: Undecidability, hardness, mathematical programming
Liberti, Leo 1
@article{RO_2019__53_1_81_0,
author = {Liberti, Leo},
title = {Undecidability and hardness in mixed-integer nonlinear programming},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {81--109},
year = {2019},
publisher = {EDP Sciences},
volume = {53},
number = {1},
doi = {10.1051/ro/2018036},
zbl = {1414.90237},
mrnumber = {3904273},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2018036/}
}
TY - JOUR AU - Liberti, Leo TI - Undecidability and hardness in mixed-integer nonlinear programming JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 81 EP - 109 VL - 53 IS - 1 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ro/2018036/ DO - 10.1051/ro/2018036 LA - en ID - RO_2019__53_1_81_0 ER -
%0 Journal Article %A Liberti, Leo %T Undecidability and hardness in mixed-integer nonlinear programming %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 81-109 %V 53 %N 1 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ro/2018036/ %R 10.1051/ro/2018036 %G en %F RO_2019__53_1_81_0
Liberti, Leo. Undecidability and hardness in mixed-integer nonlinear programming. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 81-109. doi: 10.1051/ro/2018036
[1] , , and , NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137 (2013) 453–476. | Zbl | MR | DOI
[2] , Turán’s graph theorem. Am. Math. Mon. 102 (1995) 808–816. | Zbl | MR
[3] , and , On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, in Proceedings of International Conference on Polynomial System Solving (2004).
[4] , and , Algorithms, in Real Algebraic Geometry. Springer, New York (2006). | Zbl | MR
[5] , , and , Is the distance geometry problem in NP?, in Distance Geometry: Theory, Methods, and Applications. Edited by , , and . Springer, New York (2013) 85–94. | Zbl | MR | DOI
[6] , , , , and , Mixed-integer nonlinear optimization. Acta Numer. 22 (2013) 1–131. | Zbl | MR | DOI
[7] and , Bilinear separation of two sets in n-space. Comput. Optim. Appl. 2 (1993) 207–227. | Zbl | MR | DOI
[8] , Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74 (1996) 121–140. | Zbl | MR | DOI
[9] and , Polynomial solvability of variants of the trust-region subproblem, in Vol. 25 of SODA. Proceedings of the 25th Annual ACM Symposium on Discrete Algorithms. ACM, Philadelphia (2014) 380–390. | Zbl | MR
[10] , and , On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions, and universal machines. Bull. Am. Math. Soc. 21 (1989) 1–46. | Zbl | MR | DOI
[11] , Evolution towards the maximum clique. J. Glob. Optim. 10 (1997) 143–164. | Zbl | MR | DOI
[12] , Copositive optimization — recent developments and applications. Eur. J. Oper. Res. 216 (2012) 509–520. | Zbl | MR | DOI
[13] , , , , and , On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18 (2000) 301–320. | Zbl | MR | DOI
[14] , , , and , On the optimal design of water distribution networks: a practical MINLP approach. Optim. Eng. 13 (2012) 219–246. | Zbl | MR | DOI
[15] , , , , , , , On modularity clustering. IEEE Trans. Knowl. Data Eng. 20 (2008) 172–188. | DOI
[16] and , Optimal running and planning of a biomass-based energy production process. Energy Policy 36 (2008) 2430–2438. | DOI
[17] , Bruno Buchberger’s PhD Thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero-dimensional polynomial ideal. J. Symb. Comput. 41 (2006) 475–511. | Zbl | MR | DOI
[18] and , Non-convex mixed-integer nonlinear programming: a survey. Surv. Oper. Res. Manag. Sci. 17 (2012) 97–106. | MR
[19] , , and , Optimal design of electrical machines: mathematical programming formulations. COMPEL 32 (2013) 977–996. | Zbl | DOI
[20] and , Polynomial Programming Using Gröbner Bases. Technical Report, University of Illinois at Urbana-Champaign (1994).
[21] and , Exploiting chordal structure in polynomial ideas: a Gröbner basis approach. SIAM J. Discrete Math. 30 (2016) 1534–1570. | Zbl | MR | DOI
[22] , The intrinsic computational difficulty of functions, Logic, Methodology and Philosophy of Science, edited by . North-Holland, Amsterdam (1965) 24–30. | Zbl | MR
[23] , Quantifier elimination for real closed fields. ACM SIGSAM Bull. 8 (1974) 80–90. | DOI
[24] , The complexity of theorem-proving procedures, in Proc. of STOC ’71 Proceedings of the third annual ACM symposium on Theory of computing. New York (1971) 151–158. | Zbl
[25] and , Abstract interpretation: a unified lattice model for static analysis of programs by construction of approximations of fixed points. Princ. Program. Lang. 4 (1977) 238–252.
[26] , Application-oriented mixed integer non-linear programming. 4OR 8 (2010) 319–322. | Zbl | DOI
[27] and , Mixed-integer nonlinear programming tools: a practical overview. 4OR 9 (2011) 329–349. | Zbl | MR | DOI
[28] , Arithmetical problems and recursively enumerable predicates. J. Symb. Logic 18 (1953) 33–41. | Zbl | MR | DOI
[29] , and , The decision problem for exponential Diophantine equations. Ann. Math. 74 (1961) 425–436. | Zbl | MR | DOI
[30] , Copositive programming — a survey, in Recent Advances in Optimization and its Applications in Engineering, edited by et al. Springer, Heidelberg (2010). | DOI
[31] , Paths, trees and flowers. Can. J. Math. 17 (1965) 449–467. | Zbl | MR | DOI
[32] , Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, New York (1995). | Zbl | DOI
[33] , Deterministic Global Optimization. Kluwer Academic Publishers, Dordrecht (2000). | MR | DOI
[34] , Gödel’s Theorem: An Incomplete Guide to I1 Use and Abuse. Peters, Wellesley (2005). | Zbl | MR | DOI
[35] , and , Quantifier elimination over finite fields using Gröbner bases, edited by . Algebraic Informatics. Vol. 6742 of Lect. Note Comput. Sci. Springer, New York (2011) 140–157. | Zbl | MR
[36] , Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte Math. Phys. 38 (1930) 173–198. | JFM | MR
[37] , Mixed-integer programming approach for the synthesis of integrated process flowsheets. Comput. Chem. Eng. 9 (1985) 463–482. | DOI
[38] (Ed.), Global Optimization in Engineering Design. Kluwer Academic Publishers, Dordrecht (1996). | Zbl | MR | DOI
[39] and , Mixed-integer nonlinear programming: a survey of algorithms and applications, edited by , , and . Large-Scale Optimization with Applications, Part II: Optimal Design and Control. Springer (1997) 73–100. | Zbl | MR | DOI
[40] , and , Computing global minima to polynomial optimization problems using Gröbner bases. J. Glob. Optim. 7 (1995) 115–125. | Zbl | MR | DOI
[41] , Combinatorial Theory, 2nd edn. Wiley, New York (1986). | Zbl | MR
[42] , , and , Different transformations for solving nonconvex trim-loss problem by MINLP. Eur. J. Oper. Res. 105 (1998) 594–603. | Zbl | DOI
[43] , and , A polynomially bounded algorithm for a singly constrained quadratic program. Math. Program.18 (1980) 338–343. | Zbl | MR | DOI
[44] , , and , Nonlinear integer programming, 50 Years of Integer Programming, edited by , , , , , , and . Springer, Berlin (2010) 561–618. | Zbl
[45] and , Constraint qualification failure in action. Oper. Res. Lett. 44 (2016) 503–506. | Zbl | MR | DOI
[46] , The extreme rays of the 5 × 5 copositive cone. Linear Algebra Appl. 437 (2012) 1538–1547. | Zbl | MR | DOI
[47] , Complexity and algorithms for nonlinear optimization problems. 4OR 3 (2005) 171–216. | Zbl | MR | DOI
[48] , There cannot be any algorithm for integer programming with quadratic constraints. Oper. Res. 21 (1973) 221–224. | Zbl | MR | DOI
[49] , Universal Diophantine equation. J. Symb. Logic 47 (1982) 549–571. | Zbl | MR | DOI
[50] , Cutting circles and polygons from area-minimizing rectangles. J. Glob. Optim. 43 (2009) 299–328. | Zbl | MR | DOI
[51] , Reducibility among combinatorial problems. Complexity of computer computations, edited by and . Vol. 5 of IBM Research Symposia. Plenum, New York (1972) 85–104. | Zbl | MR | DOI
[52] , An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press, Cambridge (2015). | Zbl | MR | DOI
[53] and (Eds.), Mixed integer nonlinear programming. Vol. 154 of IMA. Springer, New York (2012). | MR | DOI
[54] , Reformulations in mathematical programming: definitions and systematics. RAIRO-RO 43 (2009) 55–86. | Zbl | MR | Numdam | DOI
[55] and , Open research areas in distance geometry, Open Problems in Optimization, edited by and . Springer, New York (2018). | MR
[56] and , Mathematical programming: turing completeness and applications to software analysis. J. Comb. Optim. 28 (2014) 82–104. | Zbl | MR | DOI
[57] , , and , Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20 (2009) 1286–1310. | Zbl | MR | DOI
[58] , , , and , A mixed-integer nonlinear optimization approach for well placement and geometry, in Proceedings of the 14th European Conference on the Mathematics of Oil Recovery. Vol. XIV of ECMOR, Houten. EAGE (2014) A38.
[59] , Notes on logic. Number 6 in Mathematical Studies. Van Nostrand, New York (1966). | Zbl | MR
[60] , and , Bounds on the Kissing Numbers in ℝn: Mathematical Programming Formulations. Technical Report, University of Massachusetts, Amherst, USA (1996).
[61] , Enumerable sets are Diophantine. Sov. Math. Dokl. 11 (1970) 354–357. | Zbl
[62] , NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9 (1996) 113–119. | Zbl | MR | DOI
[63] , On the complexity of polyhedral separability. Discrete Comput. Geom. 3 (1988) 325–337. | Zbl | MR | DOI
[64] , and , A multiplicative weights update algorithm for MINLP. EURO J. Comput. Optim. 5 (2017) 31–86. | Zbl | MR | DOI
[65] , and , Optimal design of electromechanical actuators: a new method based on global optimization. IEEE Trans. Magn. 34 (1998) 299–307. | DOI
[66] , On the Betti numbers of real varieties. Proc. Am. Math. Soc. 15 (1964) 275–280. | Zbl | MR | DOI
[67] and , Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17 (1965) 533–540. | Zbl | MR | DOI
[68] and , Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39 (1987) 117–129. | Zbl | MR | DOI
[69] , Complete search in continuous global optimization and constraint satisfaction. Acta Numer. 13 (2004) 271–369. | Zbl | MR | DOI
[70] and , Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7 (1988) 33–35. | Zbl | MR | DOI
[71] and , Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1 (1991) 15–22. | Zbl | MR | DOI
[72] and , Open questions in complexity theory for numerical optimization. Math. Program. 57 (1992) 337–339. | Zbl | MR | DOI
[73] , , and , A mixed-integer nonlinear program for the optimal design and dispatch of distributed generation systems. Optim. Eng. 15 (2014) 167–197. | Zbl | MR | DOI
[74] , , , , , and T. Terlaky, Finding optimal nuclear reactor core reload patterns using nonlinear optimization and search heuristics. Eng. Optim. 32 (1999) 143–176. | DOI
[75] and , Unified complexity analysis for Newton LP methods. Math. Program. 53 (1992) 1–16. | Zbl | MR | DOI
[76] , , , and , A progressive method to solve large-scale AC optimal power flow with discrete variables and control of the feasibility, in Proceedings of the Power Systems Computation Conference. Vol. 18 of PSCC, Piscataway. IEEE (2014).
[77] , Computationally related problems. SIAM J. Comput. 3 (1974) 262–279. | Zbl | MR | DOI
[78] , , and , Alternating current optimal power flow with generator selection, Combinatorial Optimization (Proceedings of ISCO 2018) Edited by , and . In Vol. 10856 of Lecture Notes in Computer Science. Springer, New York (2018) 364–375. | MR | DOI
[79] , Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003). | Zbl | MR
[80] and , A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999). | Zbl | MR | DOI
[81] , A Decision Method for Elementary Algebra and Geometry. Technical Report R-109, Rand Corporation (1951). | Zbl | MR | DOI
[82] and , Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht (2002). | Zbl | MR | DOI
[83] , On computable numbers, with an application to the Entscheidungs problem. Proc. Lond. Math. Soc. 42 (1937) 230–265. | JFM | Zbl | MR | DOI
[84] , Quadratic programming is in NP. Inf. Process. Lett. 36 (1990) 73–77. | Zbl | MR | DOI
[85] , Nonlinear Optimization: Complexity Issues. Oxford University Press, Oxford (1991). | Zbl | MR
[86] , Complexity issues in global optimization: a survey, edited by and . Vol. 1 of Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht (1995) 27–41. | Zbl | MR | DOI
[87] and , Proving Polynomial-Time for Sphere-Constrained Quadratic Programming. Technical Report 90-1182, Dept. of Comp. Sci., Cornell University (1990).
[88] , An all-integer programming algorithm with parabolic constraints. J. Soc. Ind. Appl. Math. 11 (1963) 855–870. | Zbl | MR | DOI
[89] , Unsolvability of some optimization problems. Appl. Math. Comput. 174 (2006) 921–926. | Zbl | MR
Cité par Sources :
