Friday, 10:30 - 10:55 h, Room: H 3013


Paolo Serafini
Compact formulations for large-scale LP problems

Coauthor: Giuseppe Lancia


There are many combinatorial problems which can be effectively dealt with via Integer Linear Programming by using column-generation or constraint-generation techniques. When the pricing for column generation can be solved by Linear Programming, it is possible to embed the positive reduced cost condition into the dual of the relaxed integer primal. Similarly, for constraint generation, if the separation problem is a Linear Program, it can be embedded into the integer primal. The new model has polynomial size and has the same lower bounds as the original exponential size model. We call "compact'' this reformulation. The compact reformulation may provide new insight into the problem structure and sometimes exhibits a computational better performance than the original formulation. It is possible to develop compact models for the following problems: Bin packing, Max cut, Stable set, TSP, Minimum routing cost tree, Steiner tree, Cycle packing, Alternate cycle decomposition, Job Shop, Protein fold comparison and various variant of TSP, like Prize collecting TSP and Time window TSP.


Talk 1 of the contributed session Fri.1.H 3013
"Extended formulations" [...]
Cluster 2
"Combinatorial optimization" [...]


  Online lending company provides a wide range of ways to get money by means of Payday Loans Tennessee. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.