ncku-talk2011-03-24

NCTS(South)/ NCKU Math Colloquium

DATE 2011-03-24　15:10-16:00

PLACE R204, 2F, NCTS, NCKU

SPEAKER Professor Duan Li（The Chinese University of Hong Kong）

TITLE Quadratic 0-1 Programming: SDP Relaxations and Gap Reduction

ABSTRACT Quadratic 0-1 (binary) programming plays an important role in integer programming and combinatorial optimization. Many combinatorial problems such as max-cut, max-bisection, quadratic assignment and quadratic knapsack problems can be modeled as quadratic 0-1 (binary) programming problems. This class of problems are in general NP-hard and have attracted much attention in recent years in both continuous and discrete optimization communities.
In this talk, we first review different ways of getting convex relaxations for 0-1 quadratic programming problems, including linear programming relaxation, reformulation linearization technique (RLT) and semidefinite programming (SDP) relaxations. We then focus on the SDP relaxations for 0-1 quadratic programs. We first consider the gap between the unconstrained binary quadratic program and its SDP relaxation. We show that the SDP bound can be improved by using the a distance measure from the binary set to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. We then discuss the gap reduction for binary quadratic program with equality constraints and quadratic knapsack program. Recent progress on gap reduction for other types of 0-1 quadratic programs will be also mentioned. Finally, we discuss some open questions and conjectures for future research.

NCTS(South)/ NCKU Math Colloquium

DATE	2011-03-24　15:10-16:00

PLACE	R204, 2F, NCTS, NCKU

SPEAKER	Professor Duan Li（The Chinese University of Hong Kong）

TITLE	Quadratic 0-1 Programming: SDP Relaxations and Gap Reduction

ABSTRACT	Quadratic 0-1 (binary) programming plays an important role in integer programming and combinatorial optimization. Many combinatorial problems such as max-cut, max-bisection, quadratic assignment and quadratic knapsack problems can be modeled as quadratic 0-1 (binary) programming problems. This class of problems are in general NP-hard and have attracted much attention in recent years in both continuous and discrete optimization communities. In this talk, we first review different ways of getting convex relaxations for 0-1 quadratic programming problems, including linear programming relaxation, reformulation linearization technique (RLT) and semidefinite programming (SDP) relaxations. We then focus on the SDP relaxations for 0-1 quadratic programs. We first consider the gap between the unconstrained binary quadratic program and its SDP relaxation. We show that the SDP bound can be improved by using the a distance measure from the binary set to certain affine subspace, while the computation of this distance can be achieved by the cell enumeration of hyperplane arrangement. We then discuss the gap reduction for binary quadratic program with equality constraints and quadratic knapsack program. Recent progress on gap reduction for other types of 0-1 quadratic programs will be also mentioned. Finally, we discuss some open questions and conjectures for future research.