SOLVING QUADRATIC (0,1)-PROBLEMS BY SEMIDEFINITE PROGRAMS AND CUTTINGPLANES

Authors
HELMBERG C RENDL F
Citation
C. Helmberg et F. Rendl, SOLVING QUADRATIC (0,1)-PROBLEMS BY SEMIDEFINITE PROGRAMS AND CUTTINGPLANES, Mathematical programming, 82(3), 1998, pp. 291-315
Citations number
44
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming","Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
82
Issue
3
Year of publication
1998
Pages
291 - 315
Database
ISI
SICI code
0025-5610(1998)82:3<291:SQ(BSP>2.0.ZU;2-X
Abstract
We present computational experiments for solving quadratic (0, 1) prob lems. Our approach combines a semidefinite relaxation with a cutting p lane technique, and is applied in a Branch and Bound setting. Our expe riments indicate that this type of approach is very robust, and allows to solve many moderately sized problems, having say, less than 100 bi nary variables, in a routine manner. (C) 1998 The Mathematical Program ming Society, Inc. Published by Elsevier Science B.V.