Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable
Pasquale Avella, Maurizio Boccia, Igor Vasilyev
INFORMS Journal on Computing · 2012 · Volume 24 · Issue 1
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.
Keywords
knapsack set with a single continuous variable, exact separation
Enable JavaScript for citation tools and additional paper interactions.