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.

Compact formulations for large-scale LP problems

LANCIA, Giuseppe;SERAFINI, Paolo
2012-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/868377
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact