Old Wine in a New Bottle: The MILP Road to MIQCP
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.
Entry Submitted: 07/08/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|