Combining Lift‐and‐Project and Reduce‐and‐Split

Combining Lift‐and‐Project and Reduce‐and‐Split

0.00 Avg rating0 Votes
Article ID: iaor20134946
Volume: 25
Issue: 3
Start Page Number: 475
End Page Number: 487
Publication Date: Jun 2013
Journal: INFORMS Journal on Computing
Authors: , , ,
Keywords: branch-and-cut, relaxation methods, mixed integer programming
Abstract:

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch‐and‐cut solvers for mixed‐integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed‐form expression. In this paper, we use the lift‐and‐project framework introduced by Balas and Perregaard to provide the basis, and the reduce‐and‐split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed‐integer cut and alternates between lift‐and‐project and reduce‐and‐split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce‐and‐split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods.

Reviews

Required fields are marked *. Your email address will not be published.