Mixed-integer quadratic programming is in NP

DOI10.1007/S10107-016-1036-0zbMath1362.90298arXiv1407.4798OpenAlexW1486787620WikidataQ57568051 ScholiaQ57568051MaRDI QIDQ517303

Marco Molinaro, Alberto Del Pia, Santanu S. Dey

Publication date: 23 March 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.4798

zbMATH Keywords

complexityinteger programmingquadratic programming

Mathematics Subject Classification ID

Mixed integer programming (90C11) Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20)

Related Items (21)

Simple Strategies in Multi-Objective MDPs ⋮ Proximity in concave integer quadratic programming ⋮ On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming ⋮ On the Mixed Binary Representability of Ellipsoidal Regions ⋮ Mixed-Integer Convex Representability ⋮ Scheduling for a processor sharing system with linear slowdown ⋮ Phragmén's voting methods and justified representation ⋮ Complexity of optimizing over the integers ⋮ An approximation algorithm for indefinite mixed integer quadratic programming ⋮ Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications ⋮ Conic formulation of QPCCs applied to truly sparse QPs ⋮ Termination of polynomial loops ⋮ Long-Run Average Behavior of Vector Addition Systems with States ⋮ Subdeterminants and Concave Integer Quadratic Programming ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ On approximation algorithms for concave mixed-integer quadratic programming ⋮ Ellipsoidal mixed-integer representability ⋮ Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ Characterizations of mixed binary convex quadratic representable sets ⋮ Exact Augmented Lagrangian Duality for Mixed Integer Quadratic Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Chvátal closures for mixed integer programming problems
• FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
• Some simplified NP-complete graph problems
• Note on the complexity of the mixed-integer hull of a polyhedron
• Quadratic programming is in NP
• Some NP-complete problems in quadratic and nonlinear programming
• On the Computational Complexity of Determining the Solvability or Unsolvability of the Equation X 2 - DY 2 = -1
• On the complexity of integer programming
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Reducibility among Combinatorial Problems
• Integer quadratic programming in the plane
• There Cannot be any Algorithm for Integer Programming with Quadratic Constraints

This page was built for publication: Mixed-integer quadratic programming is in NP