{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T23:46:25Z","timestamp":1781135185717,"version":"3.54.1"},"reference-count":89,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T00:00:00Z","timestamp":1548892800000},"content-version":"vor","delay-in-days":30,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"DOI":"10.13039\/100010661","name":"H2020","doi-asserted-by":"crossref","award":["764759"],"award-info":[{"award-number":["764759"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,5,4]]},"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1051\/ro\/2018036","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T08:11:07Z","timestamp":1525767067000},"page":"81-109","source":"Crossref","is-referenced-by-count":38,"title":["Undecidability and hardness in mixed-integer nonlinear programming"],"prefix":"10.1051","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3139-6821","authenticated-orcid":false,"given":"Leo","family":"Liberti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"250","published-online":{"date-parts":[[2019,1,31]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/s10107-011-0499-2","volume":"137","author":"Ahmadi","year":"2013","journal-title":"Math. Program."},{"key":"R2","first-page":"808","volume":"102","author":"Aigner","year":"1995","journal-title":"Am. Math. Mon."},{"key":"R3","unstructured":"Bardet M., Faug\u00e8re J.C. and Salvy B., On the complexity of Gr\u00f6bner basis computation of semi-regular overdetermined algebraic equations, in Proceedings of International Conference on Polynomial System Solving (2004)."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Basu S., Pollack R. and Roy M.-F., Algorithms, in Real Algebraic Geometry. Springer, New York (2006).","DOI":"10.1007\/3-540-33099-2"},{"key":"R5","unstructured":"Beeker N., Gaubert S., Glusa C. and Liberti L., Is the distance geometry problem in NP?, in Distance Geometry: Theory, Methods, and Applications. Edited by Mucherino A., Lavor C., Liberti L. and Maculan N.. Springer, New York (2013) 85\u201394."},{"key":"R6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0962492913000032","volume":"22","author":"Belotti","year":"2013","journal-title":"Acta Numer."},{"key":"R7","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF01299449","volume":"2","author":"Bennett","year":"1993","journal-title":"Comput. Optim. Appl."},{"key":"R8","first-page":"121","volume":"74","author":"Bienstock","year":"1996","journal-title":"Math. Program."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Bienstock D. and Michalka A., 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\u2013390.","DOI":"10.1137\/1.9781611973402.28"},{"key":"R10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"Blum","year":"1989","journal-title":"Bull. Am. Math. Soc."},{"key":"R11","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1023\/A:1008230200610","volume":"10","author":"Bomze","year":"1997","journal-title":"J. Glob. Optim."},{"key":"R12","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.ejor.2011.04.026","volume":"216","author":"Bomze","year":"2012","journal-title":"Eur. J. Oper. Res."},{"key":"R13","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1023\/A:1026583532263","volume":"18","author":"Bomze","year":"2000","journal-title":"J. Glob. Optim."},{"key":"R14","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s11081-011-9141-7","volume":"13","author":"Bragalli","year":"2012","journal-title":"Optim. Eng."},{"key":"R15","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","volume":"20","author":"Brandes","year":"2008","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"R16","doi-asserted-by":"crossref","first-page":"2430","DOI":"10.1016\/j.enpol.2008.01.009","volume":"36","author":"Bruglieri","year":"2008","journal-title":"Energy Policy"},{"key":"R17","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.jsc.2005.09.007","volume":"41","author":"Buchberger","year":"2006","journal-title":"J. Symb. Comput."},{"key":"R18","first-page":"97","volume":"17","author":"Burer","year":"2012","journal-title":"Surv. Oper. Res. Manag. Sci."},{"key":"R19","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1108\/03321641311305863","volume":"32","author":"Cafieri","year":"2013","journal-title":"COMPEL"},{"key":"R20","unstructured":"Chang Y.-J. and Wah B., Polynomial Programming Using Gr\u00f6bner Bases. Technical Report, University of Illinois at Urbana-Champaign (1994)."},{"key":"R21","doi-asserted-by":"crossref","first-page":"1534","DOI":"10.1137\/151002666","volume":"30","author":"Cifuentes","year":"2016","journal-title":"SIAM J. Discrete Math."},{"key":"R22","unstructured":"Cobham A., The intrinsic computational difficulty of functions, Logic, Methodology and Philosophy of Science, edited by Bar-Hillel Y.. North-Holland, Amsterdam (1965) 24\u201330."},{"key":"R23","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/1086837.1086852","volume":"8","author":"Collins","year":"1974","journal-title":"ACM SIGSAM Bull."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Cook S., The complexity of theorem-proving procedures, in Proc. of STOC \u201971 Proceedings of the third annual ACM symposium on Theory of computing. New York (1971) 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"R25","first-page":"238","volume":"4","author":"Cousot","year":"1977","journal-title":"Princ. Program. Lang."},{"key":"R26","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s10288-010-0118-8","volume":"8","author":"D\u2019Ambrosio","year":"2010","journal-title":"4OR"},{"key":"R27","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s10288-011-0181-9","volume":"9","author":"D\u2019Ambrosio","year":"2011","journal-title":"4OR"},{"key":"R28","doi-asserted-by":"crossref","first-page":"33","DOI":"10.2307\/2266325","volume":"18","author":"Davis","year":"1953","journal-title":"J. Symb. Logic"},{"key":"R29","doi-asserted-by":"crossref","first-page":"425","DOI":"10.2307\/1970289","volume":"74","author":"Davis","year":"1961","journal-title":"Ann. Math."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"D\u00fcr M., Copositive programming \u2014 a survey, in Recent Advances in Optimization and its Applications in Engineering, edited by D\u00fcr M. et al. Springer, Heidelberg (2010).","DOI":"10.1007\/978-3-642-12598-0_1"},{"key":"R31","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"Floudas C., Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, New York (1995).","DOI":"10.1093\/oso\/9780195100563.003.0011"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"Floudas C., Deterministic Global Optimization. Kluwer Academic Publishers, Dordrecht (2000).","DOI":"10.1007\/978-1-4757-4949-6"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"Franzen T., G\u00f6del\u2019s Theorem: An Incomplete Guide to I1 Use and Abuse. Peters, Wellesley (2005).","DOI":"10.1201\/b10700"},{"key":"R35","unstructured":"Gao S., Platzer A. and Clarke E., Quantifier elimination over finite fields using Gr\u00f6bner bases, edited by Winkler F.. Algebraic Informatics. Vol. 6742 of Lect. Note Comput. Sci. Springer, New York (2011) 140\u2013157."},{"key":"R36","first-page":"173","volume":"38","author":"G\u00f6del","year":"1930","journal-title":"Monatshefte Math. Phys."},{"key":"R37","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/0098-1354(85)80023-5","volume":"9","author":"Grossmann","year":"1985","journal-title":"Comput. Chem. Eng."},{"key":"R38","unstructured":"Grossmann I. (Ed.), Global Optimization in Engineering Design. Kluwer Academic Publishers, Dordrecht (1996)."},{"key":"R39","unstructured":"Grossmann I. and Kravanja Z., Mixed-integer nonlinear programming: a survey of algorithms and applications, edited by Biegler L., Coleman T., Conn A. and Santosa F.. Large-Scale Optimization with Applications, Part II: Optimal Design and Control. Springer (1997) 73\u2013100."},{"key":"R40","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BF01097057","volume":"7","author":"H\u00e4ggl\u00f6f","year":"1995","journal-title":"J. Glob. Optim."},{"key":"R41","unstructured":"Hall M., Combinatorial Theory, 2nd edn. Wiley, New York (1986)."},{"key":"R42","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1016\/S0377-2217(97)00066-0","volume":"105","author":"Harjunkoski","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"R43","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/BF01588328","volume":"18","author":"Helgason","year":"1980","journal-title":"Math. Program."},{"key":"R44","doi-asserted-by":"crossref","unstructured":"Hemmecke R., K\u00f6ppe M., Lee J. and Weismantel R., Nonlinear integer programming, 50 Years of Integer Programming, edited by J\u00fcnger M., Liebling T., Naddef D., Nemhauser G., Pulleyblank W., Reinelt G., Rinaldi G. and Wolsey L.. Springer, Berlin (2010) 561\u2013618.","DOI":"10.1007\/978-3-540-68279-0_15"},{"key":"R45","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/j.orl.2016.05.006","volume":"44","author":"Hijazi","year":"2016","journal-title":"Oper. Res. Lett."},{"key":"R46","doi-asserted-by":"crossref","first-page":"1538","DOI":"10.1016\/j.laa.2012.04.017","volume":"437","author":"Hildebrand","year":"2012","journal-title":"Linear Algebra Appl."},{"key":"R47","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s10288-005-0078-6","volume":"3","author":"Hochbaum","year":"2005","journal-title":"4OR"},{"key":"R48","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1287\/opre.21.1.221","volume":"21","author":"Jeroslow","year":"1973","journal-title":"Oper. Res."},{"key":"R49","doi-asserted-by":"crossref","first-page":"549","DOI":"10.2307\/2273588","volume":"47","author":"Jones","year":"1982","journal-title":"J. Symb. Logic"},{"key":"R50","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s10898-007-9274-6","volume":"43","author":"Kallrath","year":"2009","journal-title":"J. Glob. Optim."},{"key":"R51","doi-asserted-by":"crossref","unstructured":"Karp R., Reducibility among combinatorial problems. Complexity of computer computations, edited by Miller R. and Thatcher W.. Vol. 5 of IBM Research Symposia. Plenum, New York (1972) 85\u2013104.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"Lasserre J.-B., An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press, Cambridge (2015).","DOI":"10.1017\/CBO9781107447226"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"Lee J. and Leyffer S. (Eds.), Mixed integer nonlinear programming. Vol. 154 of IMA. Springer, New York (2012).","DOI":"10.1007\/978-1-4614-1927-3"},{"key":"R54","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1051\/ro\/2009005","volume":"43","author":"Liberti","year":"2009","journal-title":"RAIRO-RO"},{"key":"R55","doi-asserted-by":"crossref","unstructured":"Liberti L. and Lavor C., Open research areas in distance geometry, Open Problems in Optimization, edited by Migalas A. and Pardalos P.. Springer, New York (2018).","DOI":"10.1007\/978-3-319-99142-9_11"},{"key":"R56","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/s10878-014-9715-3","volume":"28","author":"Liberti","year":"2014","journal-title":"J. Comb. Optim."},{"key":"R57","doi-asserted-by":"crossref","first-page":"1286","DOI":"10.1137\/080729104","volume":"20","author":"Ling","year":"2009","journal-title":"SIAM J. Optim."},{"key":"R58","doi-asserted-by":"crossref","unstructured":"Lizon C., D\u2019Ambrosio C., Liberti L., Ravalec M.L. and Sinoquet D., 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.","DOI":"10.3997\/2214-4609.20141889"},{"key":"R59","unstructured":"Lyndon R., Notes on logic. Number 6 in Mathematical Studies. Van Nostrand, New York (1966)."},{"key":"R60","unstructured":"Maculan N., Michelon P. and MacGregor Smith J., Bounds on the Kissing Numbers in \u211dn: Mathematical Programming Formulations. Technical Report, University of Massachusetts, Amherst, USA (1996)."},{"key":"R61","first-page":"354","volume":"11","author":"Matiyasevich","year":"1970","journal-title":"Sov. Math. Dokl."},{"key":"R62","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF00121658","volume":"9","author":"Matsui","year":"1996","journal-title":"J. Glob. Optim."},{"key":"R63","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF02187916","volume":"3","author":"Megiddo","year":"1988","journal-title":"Discrete Comput. Geom."},{"key":"R64","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s13675-016-0069-8","volume":"5","author":"Mencarelli","year":"2017","journal-title":"EURO J. Comput. Optim."},{"key":"R65","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1109\/20.650361","volume":"34","author":"Messine","year":"1998","journal-title":"IEEE Trans. Magn."},{"key":"R66","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","volume":"15","author":"Milnor","year":"1964","journal-title":"Proc. Am. Math. Soc."},{"key":"R67","doi-asserted-by":"crossref","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"Motzkin","year":"1965","journal-title":"Can. J. Math."},{"key":"R68","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"Murty","year":"1987","journal-title":"Math. Program."},{"key":"R69","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1017\/S0962492904000194","volume":"13","author":"Neumaier","year":"2004","journal-title":"Acta Numer."},{"key":"R70","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0167-6377(88)90049-1","volume":"7","author":"Pardalos","year":"1988","journal-title":"Oper. Res. Lett."},{"key":"R71","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"Pardalos","year":"1991","journal-title":"J. Glob. Optim."},{"key":"R72","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/BF01581088","volume":"57","author":"Pardalos","year":"1992","journal-title":"Math. Program."},{"key":"R73","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/s11081-013-9226-6","volume":"15","author":"Pruitt","year":"2014","journal-title":"Optim. Eng."},{"key":"R74","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1080\/03052159908941295","volume":"32","author":"Quist","year":"1999","journal-title":"Eng. Optim."},{"key":"R75","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01585691","volume":"53","author":"Renegar","year":"1992","journal-title":"Math. Program."},{"key":"R76","doi-asserted-by":"crossref","unstructured":"Ruiz M., Maeght J., Mari\u00e9 A., Panciatici P. and Renaud A., 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).","DOI":"10.1109\/PSCC.2014.7038395"},{"key":"R77","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"Sahni","year":"1974","journal-title":"SIAM J. Comput."},{"key":"R78","unstructured":"Salgado E., Scozzari A., Tardella F. and Liberti L., Alternating current optimal power flow with generator selection, Combinatorial Optimization (Proceedings of ISCO 2018) Edited by Lee J., Rinaldi G. and Mahjoub R.. In Vol. 10856 of Lecture Notes in Computer Science. Springer, New York (2018) 364\u2013375."},{"key":"R79","unstructured":"Schrijver A., Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)."},{"key":"R80","doi-asserted-by":"crossref","unstructured":"Sherali H. and Adams W., A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999).","DOI":"10.1007\/978-1-4757-4388-3"},{"key":"R81","doi-asserted-by":"crossref","unstructured":"Tarski A., A Decision Method for Elementary Algebra and Geometry. Technical Report R-109, Rand Corporation (1951).","DOI":"10.1525\/9780520348097"},{"key":"R82","unstructured":"Tawarmalani M. and Sahinidis N., Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht (2002)."},{"key":"R83","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","volume":"42","author":"Turing","year":"1937","journal-title":"Proc. Lond. Math. Soc."},{"key":"R84","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(90)90100-C","volume":"36","author":"Vavasis","year":"1990","journal-title":"Inf. Process. Lett."},{"key":"R85","unstructured":"Vavasis S., Nonlinear Optimization: Complexity Issues. Oxford University Press, Oxford (1991)."},{"key":"R86","unstructured":"Vavasis S., Complexity issues in global optimization: a survey, edited by Horst R. and Pardalos P.. Vol. 1 of Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht (1995) 27\u201341."},{"key":"R87","unstructured":"Vavasis S. and Zippel R., Proving Polynomial-Time for Sphere-Constrained Quadratic Programming. Technical Report 90-1182, Dept. of Comp. Sci., Cornell University (1990)."},{"key":"R88","doi-asserted-by":"crossref","first-page":"855","DOI":"10.1137\/0111063","volume":"11","author":"Witzgall","year":"1963","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"R89","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1016\/j.amc.2005.05.025","volume":"174","author":"Zhu","year":"2006","journal-title":"Appl. Math. Comput."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018036\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,22]],"date-time":"2022-08-22T18:07:13Z","timestamp":1661191633000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":89,"journal-issue":{"issue":"1"},"alternative-id":["ro170301"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018036","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}