A RECIPE FOR SEMIDEFINITE RELAXATION FOR (0,1)-QUADRATIC PROGRAMMING

被引:125
作者
POLJAK, S
RENDL, F
WOLKOWICZ, H
机构
[1] UNIV PASSAU,FAC MATH & INFORMAT,D-94030 PASSAU,GERMANY
[2] GRAZ TECH UNIV,INST MATH,A-8010 GRAZ,AUSTRIA
[3] UNIV WATERLOO,DEPT COMBINATOR & OPTIMIZAT,WATERLOO,ON N2L 3G1,CANADA
关键词
QUADRATIC BOOLEAN PROGRAMMING; SEMIDEFINITE PROGRAMMING; BOUNDS; LAGRANGIAN DUALITY; PARAMETRIC PROGRAMMING; TRUST REGION SUBPROBLEMS; MINMAX EIGENVALUE PROBLEMS; QUADRATIC ASSIGNMENT PROBLEM; GRAPH PARTITIONING; MAX-CLIQUE; THETA FUNCTION;
D O I
10.1007/BF01100205
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We review various relaxations of (0,1)-quadratic programming problems. These include semidefinite programs, parametric trust region problems and concave quadratic maximization. All relaxations that we consider lead to efficiently solvable problems. The main contributions of the paper are the following. Using Lagrangian duality, we prove equivalence of the relaxations in a unified and simple way. Some of these equivalences have been known previously, but our approach leads to short and transparent proofs. Moreover we extend the approach to the case of equality constrained problems by taking the squared linear constraints into the objective function. We show how this technique can be applied to the Quadratic Assignment Problem, the Graph Partition Problem and the Max-Clique Problem. Finally we show our relaxation to be best possible among all quadratic majorants with zero trace.
引用
收藏
页码:51 / 73
页数:23
相关论文
共 28 条
[1]   ON THE EQUIVALENCE BETWEEN ROOF DUALITY AND LAGRANGIAN-DUALITY FOR UNCONSTRAINED 0-1 QUADRATIC-PROGRAMMING PROBLEMS [J].
ADAMS, WP ;
DEARING, PM .
DISCRETE APPLIED MATHEMATICS, 1994, 48 (01) :1-20
[2]  
ALIZADEH F, 1992, 2ND P ANN INT PROGR
[3]  
[Anonymous], 2016, LINEAR NONLINEAR PRO
[4]   A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS [J].
BALAS, E ;
CERIA, S ;
CORNUEJOLS, G .
MATHEMATICAL PROGRAMMING, 1993, 58 (03) :295-324
[5]  
BALAS E, 1994, COMMUNICATION
[6]  
Bertsekas D. P, 1982, REINFORCEMENT LEARNI
[7]   LAPLACIAN EIGENVALUES AND THE MAXIMUM CUT PROBLEM [J].
DELORME, C ;
POLJAK, S .
MATHEMATICAL PROGRAMMING, 1993, 62 (03) :557-574
[8]  
FALKNER J, IN PRESS SEMIDEFINIT
[9]  
FINKE G, 1987, ANN DISCRETE MATH, V31, P61
[10]  
FORGO F, 1988, NONCONVEX PROGRAMMIN