There Cannot be any Algorithm for Integer Programming with Quadratic Constraints

R. C. Jeroslow
R. C. Jeroslow
Carnegie-Mellon University, Pittsburgh, Pennsylvania
Search for more papers by this author

Carnegie-Mellon University, Pittsburgh, Pennsylvania

Published Online:1 Feb 1973https://doi.org/10.1287/opre.21.1.221

Abstract

This paper studies a class of integer programming problems in which squares of variables may occur in the constraints, and shows that no computing device can be programmed to compute the optimum criterion value for all problems in this class.

Cited by
- All-Quadratic Mixed-Integer Problems: A Study on Evolution Strategies and Mathematical Programming
  29 May 2026 | Evolutionary Computation, Vol. 34, No. 2
- Maximum Satisfiability Formulations for Nonlinear Integer Programming
  29 August 2025
- Developments in tropical convexity
- Quantifier Elimination for Regular Integer Linear-Exponential Programming
- Multiobjective Mixed-Integer Quadratic Models: A Study on Mathematical Programming and Evolutionary Computation
  IEEE Transactions on Evolutionary Computation, Vol. 29, No. 3
- Granularity for Mixed-Integer Polynomial Optimization Problems
  6 March 2025 | Journal of Optimization Theory and Applications, Vol. 205, No. 2
- Bilinear branch and check for unspecified parallel machine scheduling with shift consideration
  European Journal of Operational Research, Vol. 320, No. 1
- Collaborative electric vehicle routing with meet points
  Communications in Transportation Research, Vol. 4
- Integer programming using a single atom
  1 August 2024 | Quantum Science and Technology, Vol. 9, No. 4
- Gurobi Optimization for 5GC Refactoring
- On the Behavior of the Mixed-Integer SMS-EMOA on Box-Constrained Quadratic Bi-Objective Models
  24 July 2023
- Complexity of linear relaxations in integer programming
  18 February 2021 | Mathematical Programming, Vol. 194, No. 1-2
- Nested vehicle routing problem: Optimizing drone-truck surveillance operations
  Transportation Research Part C: Emerging Technologies, Vol. 139
- Inversion of convection–diffusion equation with discrete sources
  25 July 2020 | Optimization and Engineering, Vol. 22, No. 3
- Preface
  5 July 2021 | Mathematical Programming, Vol. 188, No. 2
- Minotaur: a mixed-integer nonlinear optimization toolkit
  7 November 2020 | Mathematical Programming Computation, Vol. 13, No. 2
- Local Optimization of Nonconvex Mixed-Integer Quadratically Constrained Quadratic Programming Problems
- On the facet defining inequalities of the mixed-integer bilinear covering set
  27 July 2020 | Mathematical Methods of Operations Research, Vol. 92, No. 3
- DC programming and DCA for supply chain and production management: state-of-the-art models and methods
  29 August 2019 | International Journal of Production Research, Vol. 58, No. 20
- Generating Valid Linear Inequalities for Nonlinear Programs via Sums of Squares
  12 August 2020 | Journal of Optimization Theory and Applications, Vol. 186, No. 3
- Analysis and implementation of fractional-order chaotic system with standard components
  Journal of Advanced Research, Vol. 25
- Quasi-translations for fast hybrid nonlinear model predictive control
  Control Engineering Practice, Vol. 97
- Object-Centric Task and Motion Planning in Dynamic Environments
  IEEE Robotics and Automation Letters, Vol. 5, No. 2
- SDN assisted self organizing network architecture for multi-RAT networks and mobility prediction
  28 June 2018 | Wireless Networks, Vol. 26, No. 1
- Path-based MAXBAND with green-split variables and traffic dispersion
  10 July 2018 | Transportmetrica B: Transport Dynamics, Vol. 7, No. 1
- Mixed Integer Programming For Sparse Coding: Application to Image Denoising
  IEEE Transactions on Computational Imaging, Vol. 5, No. 3
- QPLIB: a library of quadratic programming instances
  22 September 2018 | Mathematical Programming Computation, Vol. 11, No. 2
- Piecewise linear bounding of univariate nonlinear functions and resulting mixed integer linear programming-based solution methods
  European Journal of Operational Research, Vol. 275, No. 3
- Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming
  17 December 2018 | Journal of Global Optimization, Vol. 73, No. 4
- Undecidability and hardness in mixed-integer nonlinear programming
  31 January 2019 | RAIRO - Operations Research, Vol. 53, No. 1
- Mixed logical dynamical modeling and hybrid model predictive control of public transport operations
  Transportation Research Part B: Methodological, Vol. 114
- Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations
  9 April 2018 | Mathematical Programming, Vol. 170, No. 1
- Training Beam Sequence Optimization for Millimeter Wave MIMO Tracking Systems
- Norm bounds and underestimators for unconstrained polynomial integer minimization
  23 September 2017 | Mathematical Methods of Operations Research, Vol. 87, No. 1
- Fast NMPC with Mixed-Integer Controls Using Quasi-Translations
  IFAC-PapersOnLine, Vol. 51, No. 20
- Mixed-integer quadratic programming is in NP
  18 June 2016 | Mathematical Programming, Vol. 162, No. 1-2
- Process Optimization
- Multi-Path Signal Synchronization Model with Phase Ratio and Dispersion Constraints
  29 September 2017 | MATEC Web of Conferences, Vol. 124
- Resource allocation in shared spectrum access communications for operators with diverse service requirements
  29 July 2016 | EURASIP Journal on Advances in Signal Processing, Vol. 2016, No. 1
- Scheduling under linear constraints
  European Journal of Operational Research, Vol. 253, No. 2
- The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming
  25 June 2015 | Journal of Global Optimization, Vol. 64, No. 2
- Optimal Spacing of “Covered” and “Exposed” Time Intervals in a Stochastic Process with High Penalty Costs: Applications to Parking and Insurance
  6 February 2017 | INFOR: Information Systems and Operational Research, Vol. 53, No. 3
- Power-aware automated hybrid pipelining of combinational circuits
- Power-Aware Automated Pipelining of Combinational Circuits
- Mathematical programming: Turing completeness and applications to software analysis
  16 February 2014 | Journal of Combinatorial Optimization, Vol. 28, No. 1
- Optimizing a multi-stage production/inventory system by DC programming based approaches
  5 October 2013 | Computational Optimization and Applications, Vol. 57, No. 2
- Getting Started
  26 September 2014
- Semidefinite Bounds
  26 September 2014
- Linear Inequalities and Polyhedra
  26 September 2014
- Valid Inequalities for Structured Integer Programs
  26 September 2014
- Reformulations and Relaxations
  26 September 2014
- Enumeration
  26 September 2014
- Mixed-integer nonlinear optimization
  2 April 2013 | Acta Numerica, Vol. 22
- Mixed integer nonlinear programming tools: an updated practical overview
  12 January 2013 | Annals of Operations Research, Vol. 204, No. 1
- Non-convex mixed-integer nonlinear programming: A survey
  Surveys in Operations Research and Management Science, Vol. 17, No. 2
- The MILP Road to MIQCP
  15 November 2011
- On the Complexity of Nonlinear Mixed-Integer Optimization
  15 November 2011
- Disjunctive Cuts for Nonconvex MINLP
  15 November 2011
- Exploiting VM Migration for the Automated Power and Performance Management of Green Cloud Computing Systems
- Mixed integer nonlinear programming tools: a practical overview
  15 November 2011 | 4OR, Vol. 9, No. 4
- Joint Scheduling and Resource Allocation in the OFDMA Downlink: Utility Maximization Under Imperfect Channel-State Information
  IEEE Transactions on Signal Processing, Vol. 59, No. 11
- Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations
  12 May 2010 | Mathematical Programming, Vol. 124, No. 1-2
- Nonlinear Integer Programming
  6 November 2009
- The Chvátal-Gomory Closure of an Ellipsoid Is a Polyhedron
- Finding discrete global minima with a filled function for integer programming
  European Journal of Operational Research, Vol. 189, No. 1
- Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs
- Integer Polynomial Optimization in Fixed Dimension
  Jesús A. De Loera,
  Raymond Hemmecke,
  Matthias Köppe,
  Robert Weismantel,
  1 February 2006 | Mathematics of Operations Research, Vol. 31, No. 1
- A new filled function method for nonlinear integer programming problem
  Applied Mathematics and Computation, Vol. 173, No. 2
- Complexity of integer quasiconvex polynomial optimization
  Journal of Complexity, Vol. 21, No. 4
- An approximate algorithm for nonlinear integer programming
  Applied Mathematics and Computation, Vol. 93, No. 2-3
- 陳列空間之配置模式
  Journal of the Chinese Institute of Industrial Engineers, Vol. 15, No. 1
- Integer Programming
  SSRN Electronic Journal, Vol. 44
- A Reference Direction Interactive Algorithm of the Multiple Objective Nonlinear Integer Programming
- An approximate algorithm for nonlinear integer programming
  European Journal of Operational Research, Vol. 74, No. 1
- Computability and Complexity of Polynomial Optimization Problems
- Convex separable optimization is not much harder than linear optimization
  1 October 1990 | Journal of the ACM, Vol. 37, No. 4
- On duality for Boolean programming
  European Journal of Operational Research, Vol. 46, No. 3
- Bibliography
- Chapter VI Integer programming
- A new branching rule for the branch and bound algorithm for solving nonlinear integer programming problems
  BIT, Vol. 28, No. 3
- References
  22 August 2014
- Computation-oriented reductions of predicate to propositional logic
  Decision Support Systems, Vol. 4, No. 2
- References
- Nonlinear Algebra and Optimization on Rings are “Hard”
  SIAM Journal on Computing, Vol. 16, No. 5
- An efficient branch and bound algorithm to solve the quadratic integer programming problem
  Computing, Vol. 30, No. 3
- Zur konstruktivität bei (gcmischt-) ganzzahigen optimierungsaufgaben
  27 June 2007 | Mathematische Operationsforschung und Statistik. Series Optimization, Vol. 14, No. 3
- Untersuchungen über eine günstige verzweigungsreihenfolge der variablen bei branch and bound-verfahren
  27 June 2007 | Mathematische Operationsforschung und Statistik. Series Optimization, Vol. 13, No. 2
- An NP-Complete Number-Theoretic Problem
  1 July 1979 | Journal of the ACM, Vol. 26, No. 3
- Integer programming formulation of combinatorial optimization problems
  Discrete Mathematics, Vol. 16, No. 1
- References††The first comprehensive references list is due to Balinski and Spielberg (1969). A later list appears in the work of Garfinkel and Nemhauser (1972b).

Volume 21, Issue 1

January-February 1973

Pages 1-400

Article Information

Metrics

Information

Published Online:February 01, 1973

Cite as

R. C. Jeroslow, (1973) There Cannot be any Algorithm for Integer Programming with Quadratic Constraints. Operations Research 21(1):221-224.

https://doi.org/10.1287/opre.21.1.221

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

There Cannot be any Algorithm for Integer Programming with Quadratic Constraints

Abstract

Volume 21, Issue 1

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News