Unbounded Convex Sets for Non-Convex Mixed-Integer Quadratic Programming
Samuel Burer (samuel-bureruiowa.edu)
Abstract: This paper introduces a fundamental family of unbounded convex sets that arises in the context of non-convex mixed-integer quadratic programming. It is shown that any mixed-integer quadratic program with linear constraints can be reduced to the minimisation of a linear function over a set in the family. Some fundamental properties of the convex sets are derived, along with connections to some other well-studied convex sets. Several classes of valid and facet-inducing inequalities are also derived.
Keywords: mixed-integer non-linear programming, global optimisation, polyhedral combinatorics, convex analysis
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Category 2: Nonlinear Optimization (Quadratic Programming )
Category 3: Combinatorial Optimization (Polyhedra )
Citation: Eventually published as: S. Burer & A.N. Letchford (2014) Unbounded convex sets for non-convex mixed-integer quadratic programming. Math. Program., 143(1-2), 231-256.
Entry Submitted: 09/18/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|