Undecidability and hardness in mixed-integer nonlinear programming
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 81-109.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018036
Classification : 90C11, 90C26
Mots-clés : Undecidability, hardness, mathematical programming
Liberti, Leo 1

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},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1},
     year = {2019},
     doi = {10.1051/ro/2018036},
     zbl = {1414.90237},
     mrnumber = {3904273},
     language = {en},
     url = {http://archive.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  - http://archive.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 http://archive.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. http://archive.numdam.org/articles/10.1051/ro/2018036/

[1] A. Ahmadi, A. Olshevsky, P. Parrilo and J. Tsitsiklis, NP-hardness of deciding convexity of quartic polynomials and related problems. Math. Program. 137 (2013) 453–476. | DOI | MR | Zbl

[2] M. Aigner, Turán’s graph theorem. Am. Math. Mon. 102 (1995) 808–816. | MR | Zbl

[3] M. Bardet, J.C. Faugère and B. Salvy, 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] S. Basu, R. Pollack and M.-F. Roy, Algorithms, in Real Algebraic Geometry. Springer, New York (2006). | MR | Zbl

[5] N. Beeker, S. Gaubert, C. Glusa and L. Liberti, Is the distance geometry problem in NP?, in Distance Geometry: Theory, Methods, and Applications. Edited by A. Mucherino, C. Lavor, L. Liberti and N. Maculan. Springer, New York (2013) 85–94. | DOI | MR | Zbl

[6] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke and A. Mahajan, Mixed-integer nonlinear optimization. Acta Numer. 22 (2013) 1–131. | DOI | MR | Zbl

[7] K. Bennett and O. Mangasarian, Bilinear separation of two sets in n-space. Comput. Optim. Appl. 2 (1993) 207–227. | DOI | MR | Zbl

[8] D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74 (1996) 121–140. | DOI | MR | Zbl

[9] D. Bienstock and A. Michalka, 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. | MR | Zbl

[10] L. Blum, M. Shub and S. Smale, 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. | DOI | MR | Zbl

[11] I. Bomze, Evolution towards the maximum clique. J. Glob. Optim. 10 (1997) 143–164. | DOI | MR | Zbl

[12] I. Bomze, Copositive optimization — recent developments and applications. Eur. J. Oper. Res. 216 (2012) 509–520. | DOI | MR | Zbl

[13] I. Bomze, M. Dür, E.D. Klerk, C. Roos, A. Quist and T. Terlaky, On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18 (2000) 301–320. | DOI | MR | Zbl

[14] C. Bragalli, C. D’Ambrosio, J. Lee, A. Lodi and P. Toth, On the optimal design of water distribution networks: a practical MINLP approach. Optim. Eng. 13 (2012) 219–246. | DOI | MR | Zbl

[15] U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, D. Wagner, On modularity clustering. IEEE Trans. Knowl. Data Eng. 20 (2008) 172–188. | DOI

[16] M. Bruglieri and L. Liberti, Optimal running and planning of a biomass-based energy production process. Energy Policy 36 (2008) 2430–2438. | DOI

[17] B. Buchberger, 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. | DOI | MR | Zbl

[18] S. Burer and A. Letchford, Non-convex mixed-integer nonlinear programming: a survey. Surv. Oper. Res. Manag. Sci. 17 (2012) 97–106. | MR

[19] S. Cafieri, L. Liberti, F. Messine and B. Nogarede, Optimal design of electrical machines: mathematical programming formulations. COMPEL 32 (2013) 977–996. | DOI | Zbl

[20] Y.-J. Chang and B. Wah, Polynomial Programming Using Gröbner Bases. Technical Report, University of Illinois at Urbana-Champaign (1994).

[21] D. Cifuentes and P. Parrilo, Exploiting chordal structure in polynomial ideas: a Gröbner basis approach. SIAM J. Discrete Math. 30 (2016) 1534–1570. | DOI | MR | Zbl

[22] A. Cobham, The intrinsic computational difficulty of functions, Logic, Methodology and Philosophy of Science, edited by Y. Bar-Hillel. North-Holland, Amsterdam (1965) 24–30. | MR | Zbl

[23] G. Collins, Quantifier elimination for real closed fields. ACM SIGSAM Bull. 8 (1974) 80–90. | DOI

[24] S. Cook, 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] P. Cousot and R. Cousot, 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] C. D’Ambrosio, Application-oriented mixed integer non-linear programming. 4OR 8 (2010) 319–322. | DOI | Zbl

[27] C. D’Ambrosio and A. Lodi, Mixed-integer nonlinear programming tools: a practical overview. 4OR 9 (2011) 329–349. | DOI | MR | Zbl

[28] M. Davis, Arithmetical problems and recursively enumerable predicates. J. Symb. Logic 18 (1953) 33–41. | DOI | MR | Zbl

[29] M. Davis, H. Putnam and J. Robinson, The decision problem for exponential Diophantine equations. Ann. Math. 74 (1961) 425–436. | DOI | MR | Zbl

[30] M. Dür, Copositive programming — a survey, in Recent Advances in Optimization and its Applications in Engineering, edited by M. Dür et al. Springer, Heidelberg (2010). | DOI

[31] J. Edmonds, Paths, trees and flowers. Can. J. Math. 17 (1965) 449–467. | DOI | MR | Zbl

[32] C. Floudas, Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, New York (1995). | DOI | Zbl

[33] C. Floudas, Deterministic Global Optimization. Kluwer Academic Publishers, Dordrecht (2000). | DOI | MR

[34] T. Franzen, Gödel’s Theorem: An Incomplete Guide to I1 Use and Abuse. Peters, Wellesley (2005). | DOI | MR | Zbl

[35] S. Gao, A. Platzer and E. Clarke, Quantifier elimination over finite fields using Gröbner bases, edited by F. Winkler. Algebraic Informatics. Vol. 6742 of Lect. Note Comput. Sci. Springer, New York (2011) 140–157. | MR | Zbl

[36] K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte Math. Phys. 38 (1930) 173–198. | JFM | MR

[37] I. Grossmann, Mixed-integer programming approach for the synthesis of integrated process flowsheets. Comput. Chem. Eng. 9 (1985) 463–482. | DOI

[38] I. Grossmann (Ed.), Global Optimization in Engineering Design. Kluwer Academic Publishers, Dordrecht (1996). | DOI | MR | Zbl

[39] I. Grossmann and Z. Kravanja, Mixed-integer nonlinear programming: a survey of algorithms and applications, edited by L. Biegler, T. Coleman, A. Conn and F. Santosa. Large-Scale Optimization with Applications, Part II: Optimal Design and Control. Springer (1997) 73–100. | DOI | MR | Zbl

[40] K. Hägglöf, P. Lindberg and L. Svensson, Computing global minima to polynomial optimization problems using Gröbner bases. J. Glob. Optim. 7 (1995) 115–125. | DOI | MR | Zbl

[41] M. Hall, Combinatorial Theory, 2nd edn. Wiley, New York (1986). | MR | Zbl

[42] I. Harjunkoski, T. Westerlund, R. Pörn and H. Skrifvars, Different transformations for solving nonconvex trim-loss problem by MINLP. Eur. J. Oper. Res. 105 (1998) 594–603. | DOI | Zbl

[43] R. Helgason, J. Kennington and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program. Math. Program.18 (1980) 338–343. | DOI | MR | Zbl

[44] R. Hemmecke, M. Köppe, J. Lee and R. Weismantel, Nonlinear integer programming, 50 Years of Integer Programming, edited by M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi and L. Wolsey. Springer, Berlin (2010) 561–618. | Zbl

[45] H. Hijazi and L. Liberti, Constraint qualification failure in action. Oper. Res. Lett. 44 (2016) 503–506. | DOI | MR | Zbl

[46] R. Hildebrand, The extreme rays of the 5 × 5 copositive cone. Linear Algebra Appl. 437 (2012) 1538–1547. | DOI | MR | Zbl

[47] D. Hochbaum, Complexity and algorithms for nonlinear optimization problems. 4OR 3 (2005) 171–216. | DOI | MR | Zbl

[48] R. Jeroslow, There cannot be any algorithm for integer programming with quadratic constraints. Oper. Res. 21 (1973) 221–224. | DOI | MR | Zbl

[49] J. Jones, Universal Diophantine equation. J. Symb. Logic 47 (1982) 549–571. | DOI | MR | Zbl

[50] J. Kallrath, Cutting circles and polygons from area-minimizing rectangles. J. Glob. Optim. 43 (2009) 299–328. | DOI | MR | Zbl

[51] R. Karp, Reducibility among combinatorial problems. Complexity of computer computations, edited by R. Miller and W. Thatcher. Vol. 5 of IBM Research Symposia. Plenum, New York (1972) 85–104. | DOI | MR | Zbl

[52] J.-B. Lasserre, An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press, Cambridge (2015). | DOI | MR | Zbl

[53] J. Lee and S. Leyffer (Eds.), Mixed integer nonlinear programming. Vol. 154 of IMA. Springer, New York (2012). | DOI | MR

[54] L. Liberti, Reformulations in mathematical programming: definitions and systematics. RAIRO-RO 43 (2009) 55–86. | DOI | Numdam | MR | Zbl

[55] L. Liberti and C. Lavor, Open research areas in distance geometry, Open Problems in Optimization, edited by A. Migalas and P. Pardalos. Springer, New York (2018). | MR

[56] L. Liberti and F. Marinelli, Mathematical programming: turing completeness and applications to software analysis. J. Comb. Optim. 28 (2014) 82–104. | DOI | MR | Zbl

[57] C. Ling, J. Nie, L. Qi and Y. Ye, Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20 (2009) 1286–1310. | DOI | MR | Zbl

[58] C. Lizon, C. D’Ambrosio, L. Liberti, M.L. Ravalec and D. Sinoquet, 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] R. Lyndon, Notes on logic. Number 6 in Mathematical Studies. Van Nostrand, New York (1966). | MR | Zbl

[60] N. Maculan, P. Michelon and J. Macgregor Smith, Bounds on the Kissing Numbers in ℝn: Mathematical Programming Formulations. Technical Report, University of Massachusetts, Amherst, USA (1996).

[61] Y. Matiyasevich, Enumerable sets are Diophantine. Sov. Math. Dokl. 11 (1970) 354–357. | Zbl

[62] T. Matsui, NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9 (1996) 113–119. | DOI | MR | Zbl

[63] N. Megiddo, On the complexity of polyhedral separability. Discrete Comput. Geom. 3 (1988) 325–337. | DOI | MR | Zbl

[64] L. Mencarelli, Y. Sahraoui and L. Liberti, A multiplicative weights update algorithm for MINLP. EURO J. Comput. Optim. 5 (2017) 31–86. | DOI | MR | Zbl

[65] F. Messine, B. Nogarede and J.-L. Lagouanelle, Optimal design of electromechanical actuators: a new method based on global optimization. IEEE Trans. Magn. 34 (1998) 299–307. | DOI

[66] J. Milnor, On the Betti numbers of real varieties. Proc. Am. Math. Soc. 15 (1964) 275–280. | DOI | MR | Zbl

[67] T. Motzkin and E. Straus, Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17 (1965) 533–540. | DOI | MR | Zbl

[68] K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39 (1987) 117–129. | DOI | MR | Zbl

[69] A. Neumaier, Complete search in continuous global optimization and constraint satisfaction. Acta Numer. 13 (2004) 271–369. | DOI | MR | Zbl

[70] P. Pardalos and G. Schnitger, Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7 (1988) 33–35. | DOI | MR | Zbl

[71] P. Pardalos and S. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1 (1991) 15–22. | DOI | MR | Zbl

[72] P. Pardalos and S. Vavasis, Open questions in complexity theory for numerical optimization. Math. Program. 57 (1992) 337–339. | DOI | MR | Zbl

[73] K. Pruitt, S. Leyffer, A. Newman and R. Braun, A mixed-integer nonlinear program for the optimal design and dispatch of distributed generation systems. Optim. Eng. 15 (2014) 167–197. | DOI | MR | Zbl

[74] A. Quist, R.V. Geemert, J. Hoogenboom, T. Illes, E.D. Klerk, C. Roos and T. Terlaky, Finding optimal nuclear reactor core reload patterns using nonlinear optimization and search heuristics. Eng. Optim. 32 (1999) 143–176. | DOI

[75] J. Renegar and M. Shub, Unified complexity analysis for Newton LP methods. Math. Program. 53 (1992) 1–16. | DOI | MR | Zbl

[76] M. Ruiz, J. Maeght, A. Marié, P. Panciatici and A. Renaud, 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] S. Sahni, Computationally related problems. SIAM J. Comput. 3 (1974) 262–279. | DOI | MR | Zbl

[78] E. Salgado, A. Scozzari, F. Tardella and L. Liberti, Alternating current optimal power flow with generator selection, Combinatorial Optimization (Proceedings of ISCO 2018) Edited by J. Lee, G. Rinaldi and R. Mahjoub. In Vol. 10856 of Lecture Notes in Computer Science. Springer, New York (2018) 364–375. | DOI | MR

[79] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003). | MR | Zbl

[80] H. Sherali and W. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999). | DOI | MR | Zbl

[81] A. Tarski, A Decision Method for Elementary Algebra and Geometry. Technical Report R-109, Rand Corporation (1951). | DOI | MR | Zbl

[82] M. Tawarmalani and N. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht (2002). | DOI | MR | Zbl

[83] A. Turing, On computable numbers, with an application to the Entscheidungs problem. Proc. Lond. Math. Soc. 42 (1937) 230–265. | DOI | JFM | MR | Zbl

[84] S. Vavasis, Quadratic programming is in NP. Inf. Process. Lett. 36 (1990) 73–77. | DOI | MR | Zbl

[85] S. Vavasis, Nonlinear Optimization: Complexity Issues. Oxford University Press, Oxford (1991). | MR | Zbl

[86] S. Vavasis, Complexity issues in global optimization: a survey, edited by R. Horst and P. Pardalos. Vol. 1 of Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht (1995) 27–41. | DOI | MR | Zbl

[87] S. Vavasis and R. Zippel, Proving Polynomial-Time for Sphere-Constrained Quadratic Programming. Technical Report 90-1182, Dept. of Comp. Sci., Cornell University (1990).

[88] C. Witzgall, An all-integer programming algorithm with parabolic constraints. J. Soc. Ind. Appl. Math. 11 (1963) 855–870. | DOI | MR | Zbl

[89] W. Zhu, Unsolvability of some optimization problems. Appl. Math. Comput. 174 (2006) 921–926. | MR | Zbl

Cité par Sources :