Extended canonical duality and conic programming for solving 0-1 quadratic programming problems

Pages: 779 - 793, Volume 6, Issue 4, November 2010

doi:10.3934/jimo.2010.6.779       Abstract        References        Full Text (182.4K)       Related Articles

Cheng Lu - Department of Mathematical Sciences, Tsinghua University, Beijing, China (email)
Zhenbo Wang - Department of Mathematical Sciences, Tsinghua University, Beijing, China (email)
Wenxun Xing - Department of Mathematical Sciences, Tsinghua University, Beijing, China (email)
Shu-Cherng Fang - Department of Industrial and System Engineering, North Carolina State University, Raleigh, NC 27695, United States (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.
Mathematics Subject Classification:  49N15, 49M37, 90C26, 90C20.

Received: February 2010;      Revised: April 2010;      Published: September 2010.

 References