Solving quadratic (0,1)-problems by semidefinite programs and cutting planes

被引：135

作者：

Helmberg, C

Rendl, F

机构：

[1] Konrad Zuse Zentrum Informat Tech Berlin, D-14195 Berlin, Germany

[2] Graz Tech Univ, Inst Math, A-8010 Graz, Austria

来源：

MATHEMATICAL PROGRAMMING | 1998年 / 82卷 / 03期

关键词：

quadratic; (0; l)-programming; max-cut problem; semidefinite program; branch and bound;

D O I：

10.1007/BF01580072

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present computational experiments for solving quadratic (0, 1) problems. Our approach combines a semidefinite relaxation with a cutting plane technique, and is applied in a Branch and Bound setting. Our experiments indicate that this type of approach is very robust, and allows to solve many moderately sized problems, having say, less than 100 binary variables, in a routine manner. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

引用

页码：291 / 315

页数：25

共 45 条

[11] De Simone C., 1989, DISCRETE MATH, V79, P71
[12] LAPLACIAN EIGENVALUES AND THE MAXIMUM CUT PROBLEM
DELORME, C
POLJAK, S
[J]. MATHEMATICAL PROGRAMMING, 1993, 62 (03) : 557 - 574
[13] COMBINATORIAL PROPERTIES AND THE COMPLEXITY OF A MAX-CUT APPROXIMATION
DELORME, C
POLJAK, S
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 1993, 14 (04) : 313 - 333
[14] EXACT GROUND-STATES OF ISING SPIN-GLASSES - NEW EXPERIMENTAL RESULTS WITH A BRANCH-AND-CUT ALGORITHM
DESIMONE, C
DIEHL, M
JUNGER, M
MUTZEL, P
REINELT, G
RINALDI, G
[J]. JOURNAL OF STATISTICAL PHYSICS, 1995, 80 (1-2) : 487 - 496
[15] DESIMONE C, 1994, OPTIM METHOD SOFTW, V3, P195, DOI DOI 10.1080/10556789408805564
[16] DEZA M, 1994, J COMPUT APPL MATH, V55, P191, DOI 10.1016/0377-0427(94)90020-5
[17] THE HYPERMETRIC CONE IS POLYHEDRAL
DEZA, M
GRISHUKHIN, VP
LAURENT, M
[J]. COMBINATORICA, 1993, 13 (04) : 397 - 411
[18] APPLICATIONS OF CUT POLYHEDRA .2.
DEZA, M
LAURENT, M
[J]. JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 1994, 55 (02) : 217 - 247
[19] Deza M., 1997, ALGORITHMS COMBINATO, V15
[20] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Goemans, MX
Williamson, DP
[J]. JOURNAL OF THE ACM, 1995, 42 (06) : 1115 - 1145

← 1 2 3 4 5 →