Free Access
Review
Issue
RAIRO-Oper. Res.
Volume 53, Number 1, January-March 2019
Page(s) 81 - 109
DOI https://doi.org/10.1051/ro/2018036
Published online 31 January 2019
  • 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. [Google Scholar]
  • M. Aigner, Turán’s graph theorem. Am. Math. Mon. 102 (1995) 808–816. [Google Scholar]
  • 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). [Google Scholar]
  • S. Basu, R. Pollack and M.-F. Roy, Algorithms, in Real Algebraic Geometry. Springer, New York (2006). [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke and A. Mahajan, Mixed-integer nonlinear optimization. Acta Numer. 22 (2013) 1–131. [CrossRef] [Google Scholar]
  • K. Bennett and O. Mangasarian, Bilinear separation of two sets in n-space. Comput. Optim. Appl. 2 (1993) 207–227. [Google Scholar]
  • D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74 (1996) 121–140. [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • I. Bomze, Evolution towards the maximum clique. J. Glob. Optim. 10 (1997) 143–164. [CrossRef] [Google Scholar]
  • I. Bomze, Copositive optimization — recent developments and applications. Eur. J. Oper. Res. 216 (2012) 509–520. [Google Scholar]
  • 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. [CrossRef] [MathSciNet] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • M. Bruglieri and L. Liberti, Optimal running and planning of a biomass-based energy production process. Energy Policy 36 (2008) 2430–2438. [Google Scholar]
  • 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. [Google Scholar]
  • S. Burer and A. Letchford, Non-convex mixed-integer nonlinear programming: a survey. Surv. Oper. Res. Manag. Sci. 17 (2012) 97–106. [Google Scholar]
  • S. Cafieri, L. Liberti, F. Messine and B. Nogarede, Optimal design of electrical machines: mathematical programming formulations. COMPEL 32 (2013) 977–996. [CrossRef] [Google Scholar]
  • Y.-J. Chang and B. Wah, Polynomial Programming Using Gröbner Bases. Technical Report, University of Illinois at Urbana-Champaign (1994). [Google Scholar]
  • D. Cifuentes and P. Parrilo, Exploiting chordal structure in polynomial ideas: a Gröbner basis approach. SIAM J. Discrete Math. 30 (2016) 1534–1570. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • G. Collins, Quantifier elimination for real closed fields. ACM SIGSAM Bull. 8 (1974) 80–90. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • C. D’Ambrosio, Application-oriented mixed integer non-linear programming. 4OR 8 (2010) 319–322. [CrossRef] [Google Scholar]
  • C. D’Ambrosio and A. Lodi, Mixed-integer nonlinear programming tools: a practical overview. 4OR 9 (2011) 329–349. [CrossRef] [Google Scholar]
  • M. Davis, Arithmetical problems and recursively enumerable predicates. J. Symb. Logic 18 (1953) 33–41. [CrossRef] [Google Scholar]
  • M. Davis, H. Putnam and J. Robinson, The decision problem for exponential Diophantine equations. Ann. Math. 74 (1961) 425–436. [Google Scholar]
  • 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). [Google Scholar]
  • J. Edmonds, Paths, trees and flowers. Can. J. Math. 17 (1965) 449–467. [CrossRef] [MathSciNet] [Google Scholar]
  • C. Floudas, Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press, New York (1995). [Google Scholar]
  • C. Floudas, Deterministic Global Optimization. Kluwer Academic Publishers, Dordrecht (2000). [CrossRef] [Google Scholar]
  • T. Franzen, Gödel’s Theorem: An Incomplete Guide to I1 Use and Abuse. Peters, Wellesley (2005). [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • K. Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte Math. Phys. 38 (1930) 173–198. [Google Scholar]
  • I. Grossmann, Mixed-integer programming approach for the synthesis of integrated process flowsheets. Comput. Chem. Eng. 9 (1985) 463–482. [Google Scholar]
  • I. Grossmann (Ed.), Global Optimization in Engineering Design. Kluwer Academic Publishers, Dordrecht (1996). [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • M. Hall, Combinatorial Theory, 2nd edn. Wiley, New York (1986). [Google Scholar]
  • 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. [Google Scholar]
  • R. Helgason, J. Kennington and H. Lall, A polynomially bounded algorithm for a singly constrained quadratic program. Math. Program. 18 (1980) 338–343. [Google Scholar]
  • 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. [Google Scholar]
  • H. Hijazi and L. Liberti, Constraint qualification failure in action. Oper. Res. Lett. 44 (2016) 503–506. [CrossRef] [Google Scholar]
  • R. Hildebrand, The extreme rays of the 5 × 5 copositive cone. Linear Algebra Appl. 437 (2012) 1538–1547. [Google Scholar]
  • D. Hochbaum, Complexity and algorithms for nonlinear optimization problems. 4OR 3 (2005) 171–216. [CrossRef] [Google Scholar]
  • R. Jeroslow, There cannot be any algorithm for integer programming with quadratic constraints. Oper. Res. 21 (1973) 221–224. [Google Scholar]
  • J. Jones, Universal Diophantine equation. J. Symb. Logic 47 (1982) 549–571. [CrossRef] [Google Scholar]
  • J. Kallrath, Cutting circles and polygons from area-minimizing rectangles. J. Glob. Optim. 43 (2009) 299–328. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • J.-B. Lasserre, An Introduction to Polynomial and Semi-Algebraic Optimization. Cambridge University Press, Cambridge (2015). [CrossRef] [Google Scholar]
  • J. Lee and S. Leyffer (Eds.), Mixed integer nonlinear programming. Vol. 154 of IMA. Springer, New York (2012). [CrossRef] [Google Scholar]
  • L. Liberti, Reformulations in mathematical programming: definitions and systematics. RAIRO-RO 43 (2009) 55–86. [CrossRef] [Google Scholar]
  • 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). [Google Scholar]
  • L. Liberti and F. Marinelli, Mathematical programming: turing completeness and applications to software analysis. J. Comb. Optim. 28 (2014) 82–104. [Google Scholar]
  • 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. [Google Scholar]
  • 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. [Google Scholar]
  • R. Lyndon, Notes on logic. Number 6 in Mathematical Studies. Van Nostrand, New York (1966). [Google Scholar]
  • N. Maculan, P. Michelon and J. MacGregor Smith, Bounds on the Kissing Numbers inn: Mathematical Programming Formulations. Technical Report, University of Massachusetts, Amherst, USA (1996). [Google Scholar]
  • Y. Matiyasevich, Enumerable sets are Diophantine. Sov. Math. Dokl. 11 (1970) 354–357. [Google Scholar]
  • T. Matsui, NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9 (1996) 113–119. [CrossRef] [Google Scholar]
  • N. Megiddo, On the complexity of polyhedral separability. Discrete Comput. Geom. 3 (1988) 325–337. [Google Scholar]
  • L. Mencarelli, Y. Sahraoui and L. Liberti, A multiplicative weights update algorithm for MINLP. EURO J. Comput. Optim. 5 (2017) 31–86. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • J. Milnor, On the Betti numbers of real varieties. Proc. Am. Math. Soc. 15 (1964) 275–280. [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39 (1987) 117–129. [Google Scholar]
  • A. Neumaier, Complete search in continuous global optimization and constraint satisfaction. Acta Numer. 13 (2004) 271–369. [CrossRef] [Google Scholar]
  • P. Pardalos and G. Schnitger, Checking local optimality in constrained quadratic programming is NP-hard. Oper. Res. Lett. 7 (1988) 33–35. [CrossRef] [Google Scholar]
  • P. Pardalos and S. Vavasis, Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1 (1991) 15–22. [CrossRef] [Google Scholar]
  • P. Pardalos and S. Vavasis, Open questions in complexity theory for numerical optimization. Math. Program. 57 (1992) 337–339. [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • J. Renegar and M. Shub, Unified complexity analysis for Newton LP methods. Math. Program. 53 (1992) 1–16. [Google Scholar]
  • 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). [Google Scholar]
  • S. Sahni, Computationally related problems. SIAM J. Comput. 3 (1974) 262–279. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003). [Google Scholar]
  • H. Sherali and W. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishers, Dodrecht (1999). [CrossRef] [Google Scholar]
  • A. Tarski, A Decision Method for Elementary Algebra and Geometry. Technical Report R-109, Rand Corporation (1951). [Google Scholar]
  • M. Tawarmalani and N. Sahinidis, Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer, Dordrecht (2002). [Google Scholar]
  • A. Turing, On computable numbers, with an application to the Entscheidungs problem. Proc. Lond. Math. Soc. 42 (1937) 230–265. [CrossRef] [MathSciNet] [Google Scholar]
  • S. Vavasis, Quadratic programming is in NP. Inf. Process. Lett. 36 (1990) 73–77. [Google Scholar]
  • S. Vavasis, Nonlinear Optimization: Complexity Issues. Oxford University Press, Oxford (1991). [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • S. Vavasis and R. Zippel, Proving Polynomial-Time for Sphere-Constrained Quadratic Programming. Technical Report 90-1182, Dept. of Comp. Sci., Cornell University (1990). [Google Scholar]
  • C. Witzgall, An all-integer programming algorithm with parabolic constraints. J. Soc. Ind. Appl. Math. 11 (1963) 855–870. [CrossRef] [Google Scholar]
  • W. Zhu, Unsolvability of some optimization problems. Appl. Math. Comput. 174 (2006) 921–926. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.