Optimization Online


Unbounded Convex Sets for Non-Convex Mixed-Integer Quadratic Programming

Samuel Burer (samuel-burer***at***uiowa.edu)
Adam Letchford (a.n.letchford***at***lancaster.ac.uk)

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
Entry Accepted: 09/18/2011
Entry Last Modified: 05/31/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society