Old Wine in a New Bottle: The MILP Road to MIQCP

Samuel Burer(samuel-bureruiowa.edu)
Anureet Saxena(asaxenaaxiomainc.com)

Abstract: This paper surveys results on the NP-hard mixed-integer quadratically constrained programming problem. The focus is strong convex relaxations and valid inequalities, which can become the basis of efficient global techniques. In particular, we discuss relaxations and inequalities arising from the algebraic description of the problem as well as from dynamic procedures based on disjunctive programming. These methods can be viewed as generalizations of techiniques for mixed-integer linear programming. We also present brief computational results to indicate the strength and computational requirements of the these methods.

Keywords: mixed integer quadratic programming, convex relaxations, valid inequalities, global optimization

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Global Optimization (Theory )

Citation: Manuscript, Dept of Management Sciences, University of Iowa, July 2009.

Download: [PDF]

Entry Submitted: 07/08/2009
Entry Accepted: 07/09/2009
Entry Last Modified: 07/08/2009

Modify/Update this entry