Portal de Periódicos da CAPES

Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable

2011; Institute for Operations Research and the Management Sciences; Volume: 24; Issue: 1 Linguagem: Inglês

10.1287/ijoc.1100.0441

1526-5528

Pasquale Avella, Maurizio Boccia, Igor Vasilyev,

Advanced Manufacturing and Logistics Optimization

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.