Cloud branching

  • Branch-and-bound methods for mixed-integer programming (MIP) are traditionally based on solving a linear programming (LP) relaxation and branching on a variable which takes a fractional value in the (single) computed relaxation optimum. In this paper we study branching strategies for mixed-integer programs that exploit the knowledge of multiple alternative optimal solutions (a cloud) of the current LP relaxation. These strategies naturally extend state-of-the-art methods like strong branching, pseudocost branching, and their hybrids. We show that by exploiting dual degeneracy, and thus multiple alternative optimal solutions, it is possible to enhance traditional methods. We present preliminary computational results, applying the newly proposed strategy to full strong branching, which is known to be the MIP branching rule leading to the fewest number of search nodes. It turns out that cloud branching can reduce the mean running time by up to 30% on standard test sets.

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Timo Berthold, Domenico Salvagnin
Editor:Carla Gomes, Meinolf Sellmann
Document Type:In Collection
Parent Title (English):Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
Volume:7874
First Page:28
Last Page:43
Series:Lecture Notes in Computer Science
Publisher:Springer
Year of first publication:2013
Preprint:urn:nbn:de:0297-zib-17301
DOI:http://dx.doi.org/10.1007/978-3-642-38171-3_3

$Rev: 13581 $