Many inequalities for Mixed-Integer Linear Programs (MILPs) or pure Integer Linear Programs (ILPs) are derived from the Gomory corner relaxation, where all the nonbinding constraints at an optimal LP vertex are relaxed. Computational results show that the corner relaxation gives a good approximation of the integer hull for problems with general-integer variables, but the approximation is less satisfactory for problems with 0-1 variables only. A possible explanation is that, for 0-1 ILPs, even the non-binding variable bound constraints xj≥0 or xj≤1 play an important role, hence their relaxation produces weaker bounds.In this note we address a relaxation for 0-1 ILPs that explicitly takes all variable bound constraints into account. More specifically, we introduce the concept of knapsack closure as a tightening of the classical Chvátal-Gomory (CG) closure. The knapsack closure is obtained as follows: for all inequalities wTx≥w0 valid for the LP relaxation, add to the original system all the valid inequalities for the knapsack polytope conv{xε{0,1}n:wTx≥w0}. A MILP model for the corresponding separation problem is also introduced. © 2010 Elsevier B.V.
On the knapsack closure of 0-1 integer linear programs / Fischetti M.; Lodi A.. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - ELETTRONICO. - 36:C(2010), pp. 799-804. [10.1016/j.endm.2010.05.101]
On the knapsack closure of 0-1 integer linear programs
Lodi A.
2010
Abstract
Many inequalities for Mixed-Integer Linear Programs (MILPs) or pure Integer Linear Programs (ILPs) are derived from the Gomory corner relaxation, where all the nonbinding constraints at an optimal LP vertex are relaxed. Computational results show that the corner relaxation gives a good approximation of the integer hull for problems with general-integer variables, but the approximation is less satisfactory for problems with 0-1 variables only. A possible explanation is that, for 0-1 ILPs, even the non-binding variable bound constraints xj≥0 or xj≤1 play an important role, hence their relaxation produces weaker bounds.In this note we address a relaxation for 0-1 ILPs that explicitly takes all variable bound constraints into account. More specifically, we introduce the concept of knapsack closure as a tightening of the classical Chvátal-Gomory (CG) closure. The knapsack closure is obtained as follows: for all inequalities wTx≥w0 valid for the LP relaxation, add to the original system all the valid inequalities for the knapsack polytope conv{xε{0,1}n:wTx≥w0}. A MILP model for the corresponding separation problem is also introduced. © 2010 Elsevier B.V.File | Dimensione | Formato | |
---|---|---|---|
On the knapsack closure of 0-1 Integer Linea aam.pdf
Open Access dal 02/08/2012
Descrizione: aam
Tipo:
Postprint
Licenza:
Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione
216.75 kB
Formato
Adobe PDF
|
216.75 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.