Backdoor Branching

Backdoor Branching

0.00 Avg rating0 Votes
Article ID: iaor20134963
Volume: 25
Issue: 4
Start Page Number: 693
End Page Number: 700
Publication Date: Sep 2013
Journal: INFORMS Journal on Computing
Authors: ,
Keywords: covering problems, relaxation methods, mixed integer programming
Abstract:

We present an exact mixed‐integer programming (MIP) solution scheme where a set‐covering model is used to find a small set of first‐choice branching variables. In a preliminary ‘sampling’ phase, our method quickly collects a number of relevant low‐cost fractional solutions that qualify as obstacles for the linear programming (LP) relaxation bound improvement. Then a set covering model is solved to detect a small subset of variables (a ‘backdoor,’ in the artificial intelligence jargon) that ‘cover the fractionality’ of the collected fractional solutions. These backdoor variables are put in a priority branching list, and a black‐box MIP solver is eventually run–in its default mode–by taking this list into account, thus avoiding any other interference with its highly optimized internal mechanisms. Computational results on a large set of instances from the literature are presented, showing that some speedup can be achieved even with respect to a state‐of‐the‐art solver such as IBM ILOG CPLEX 12.2.

Reviews

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