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" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.