We study an exact separation procedure-SEP-MK-for the knapsack set with a single continuous variable X MK. Then, we address the question of whether SEP-MK can be of practical use in tightening mixed-integer programming (MIP) formulations when using standard (floating-point) MIP solvers. To this purpose, we present a separation procedure for MIP problems-SEP-MIP MK-where we derive knapsack sets of the form X MK by aggregating the continuous variables in the mixed knapsack inequalities of the formulation. Then, we use SEP-MK to generate cutting planes. Before the continuous variables are aggregated, the mixed knapsack inequalities are modified through the use of a bound substitution procedure to take into account fixed and variable bounds on the continuous variables. Bound substitution is made according to some heuristic rules, so even if its basic component SEP-MK is "]exact," the overall separation procedure for MIP problems, SEP-MIP MK, is heuristic. We perform a computational study on a wide set of mixed-integer programming instances from the MIPLIB 2003 [Achterberg, T., T. Koch, A. Martin. 2006. Mixed Integer Problem Library (MIPLIB) 2003. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Berlin. http://miplib.zib.de] and Mittelmann [Mittelmann, H. 2010.MILP testcases. http://plato.asu.edu/ftp/milp] benchmark sets. Computational experiments confirm that lifted cover and mixed-integer rounding (MIR) inequalities are effective from a computational viewpoint. Nevertheless, there are several instances where SEP-MIP MK is able to significantly raise the lower bounds given by lifted cover and MIR inequalities. © 2012 INFORMS.

Computational testing of a separation procedure for knapsack sets with a single continuous variable

Avella P;
2012

Abstract

We study an exact separation procedure-SEP-MK-for the knapsack set with a single continuous variable X MK. Then, we address the question of whether SEP-MK can be of practical use in tightening mixed-integer programming (MIP) formulations when using standard (floating-point) MIP solvers. To this purpose, we present a separation procedure for MIP problems-SEP-MIP MK-where we derive knapsack sets of the form X MK by aggregating the continuous variables in the mixed knapsack inequalities of the formulation. Then, we use SEP-MK to generate cutting planes. Before the continuous variables are aggregated, the mixed knapsack inequalities are modified through the use of a bound substitution procedure to take into account fixed and variable bounds on the continuous variables. Bound substitution is made according to some heuristic rules, so even if its basic component SEP-MK is "]exact," the overall separation procedure for MIP problems, SEP-MIP MK, is heuristic. We perform a computational study on a wide set of mixed-integer programming instances from the MIPLIB 2003 [Achterberg, T., T. Koch, A. Martin. 2006. Mixed Integer Problem Library (MIPLIB) 2003. Konrad-Zuse-Zentrum für Informationstechnik Berlin, Berlin. http://miplib.zib.de] and Mittelmann [Mittelmann, H. 2010.MILP testcases. http://plato.asu.edu/ftp/milp] benchmark sets. Computational experiments confirm that lifted cover and mixed-integer rounding (MIR) inequalities are effective from a computational viewpoint. Nevertheless, there are several instances where SEP-MIP MK is able to significantly raise the lower bounds given by lifted cover and MIR inequalities. © 2012 INFORMS.
Exact separation; Knapsack set with a single continuous variable
File in questo prodotto:
File Dimensione Formato  
Avebba, Boccia, Vasiliev - Knapsack exact separation.pdf

non disponibili

Licenza: Non specificato
Dimensione 251.01 kB
Formato Adobe PDF
251.01 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/20.500.12070/1618
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact