|
 
|
[MR10] On the bridge between combinatorial optimization and nonlinear optimization: new semidefinite bounds for 0-1 quadratic problems leading to Newton methods
Rapport Scientifique : Date de dépot: 2010/01/01, (Tech. Rep.: CEDRIC-10-1924)
motcle:
Résumé:
This paper presents new semidefinite programming bounds for 0-1 quadratic problems with linear or quadratic constraints. These bounds are obtained by Lagrangian duality
and convex optimization; and they have interesting numerical features: the tightness is improved by Newton-like method, and the final accuracy level is controlled by real parameter acting like a cursor. This gives ways to trade computing time for a (small) deterioration of the quality of the usual semidefinite bounds, in view of enhancing this efficiency in exact resolution schemes. The numerical properties are illustrated on standard test-problems
(unconstrained 0-1 quadratic problems, heaviest k-subgraphs problems, and graph bisection problems). Extensive comparisons with usual bounds (obtained by linear, quadratic or semidefinite programming) are provided on those problems.
Commentaires:
Soumis
Collaboration:
LIPN
BibTeX
| @techreport { | |||
| MR10, | |||
| title | = | "{On the bridge between combinatorial optimization and nonlinear optimization: new semidefinite bounds for 0-1 quadratic problems leading to Newton methods}", | |
| author | = | "J. Malick and F. Roupin", | |
| number | = | "{CEDRIC-10-1924}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2010}, | |
| note | = | "{Soumis}", | |
| } | |||
