Which is the minimum number of variables that need branching for a given MIP instance? Can this information be effective in producing compact branching trees, hence improving the performance of a state-of-the-art solver? In this paper we present a restart exact MIP solution scheme where a set covering model is used to find a small set of variables (a “backdoor”, in the terminology of [8]) to be used as first-choice variables for branching. In a preliminary “sampling” phase, our method quickly collects a number of relevant low-cost fractional solutions that qualify as obstacles for LP bound improvement. Then a set covering model is solved to detect a small subset of variables (the backdoor) 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 MIPLIB 2010 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.

Backdoor Branching

FISCHETTI, MATTEO;MONACI, MICHELE
2011

Abstract

Which is the minimum number of variables that need branching for a given MIP instance? Can this information be effective in producing compact branching trees, hence improving the performance of a state-of-the-art solver? In this paper we present a restart exact MIP solution scheme where a set covering model is used to find a small set of variables (a “backdoor”, in the terminology of [8]) to be used as first-choice variables for branching. In a preliminary “sampling” phase, our method quickly collects a number of relevant low-cost fractional solutions that qualify as obstacles for LP bound improvement. Then a set covering model is solved to detect a small subset of variables (the backdoor) 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 MIPLIB 2010 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.
Integer Programming and Combinatorial Optimization - IPCO 2011
9783642208065
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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/11577/165239
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? ND
social impact