Thursday, 13:45 - 14:10 h, Room: H 3012


Agn├Ęs Gorge
Quadratic cuts for semidefinite relaxation of combinatorial problems

Coauthors: Abdel Lisser, Riadh Zorgati


Semidefinite Programming is well-known for providing tight relaxations of combinatorial problems. In practice, only few real-world applications of this approach have been reported, especially on 0/1 Linear Programming, which is yet a large part of practical combinatorial problems. The reasons for this are twofold. First, some powerful MILP software are already available. Furthermore, for such problems, it is necessary to tighten the basic semidefinite relaxation with cuts, since as it is, it is equivalent to the linear relaxation. Then, we face the difficulty of picking the right cuts to tighten the relaxation in the most relevant fashion. These cuts might be quadratic, in order to outperform the linear relaxation.
We present here a systematic approach to compute such cuts. This method extends naturally to binary programs with non convex quadratic constraints, for which no dedicated software are currently available.
Finally, we apply this technique to a well-known problem of energy management i.e., the scheduling of the nuclear outages, a combinatorial problem with quadratic objective and non-convex quadratic constraints. Numerical results on real life instances are given.


Talk 2 of the contributed session Thu.2.H 3012
"Nonlinear combinatorial optimization" [...]
Cluster 2
"Combinatorial optimization" [...]


  online loans . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.