Compact formulations for large-scale LP problems

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 variants of TSP, like Prize collecting TSP and Time window TSP.