Extended canonical duality and conic programming for
solving 0-1 quadratic programming problems
Cheng Lu - Department of Mathematical Sciences, Tsinghua University, Beijing, China (email)
Abstract: An extended canonical dual approach for solving 0-1 quadratic programming problems is introduced. We derive the relationship between the optimal solutions to the extended canonical dual problem and the original problem and prove that there exists no duality gap in-between. The extended canonical dual approach leads to a sufficient condition for global optimality, which is more general than known results of this kind. To solve the extended canonical dual problem, we construct corresponding conic programming problems and study their relationship to the extended canonical dual problem. Using this relationship, we design an algorithm for solving the extended canonical dual problem. Our work extends the known solvable sub-class of 0-1 quadratic programming problems.
Keywords: 0-1 quadratic programming, canonical duality, conic relaxation.
Received: February 2010; Revised: April 2010; Published: September 2010.
2011 Impact Factor.66