Undercover Branching

  • In this paper, we present a new branching strategy for nonconvex MINLP that aims at driving the created subproblems towards linearity. It exploits the structure of a minimum cover of an MINLP, a smallest set of variables that, when fixed, render the remaining system linear: whenever possible, branching candidates in the cover are preferred. Unlike most branching strategies for MINLP, Undercover branching is not an extension of an existing MIP branching rule. It explicitly regards the nonlinearity of the problem while branching on integer variables with a fractional relaxation solution. Undercover branching can be naturally combined with any variable-based branching rule. We present computational results on a test set of general MINLPs from MINLPLib, using the new strategy in combination with reliability branching and pseudocost branching. The computational cost of Undercover branching itself proves negligible. While it turns out that it can influence the variable selection only on a smaller set of instances, for those that are affected, significant improvements in performance are achieved.

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Timo Berthold, Ambros M. Gleixner
Editor:Vincenzo Bonifaci, Camil Demetrescu, Alberto Marchetti-Spaccamela
Document Type:In Proceedings
Parent Title (English):Experimental Algorithms, 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013, Proceedings
Volume:7933
First Page:212
Last Page:223
Series:Lecture Notes in Computer Science
Year of first publication:2013
Preprint:urn:nbn:de:0297-zib-18030
DOI:http://dx.doi.org/10.1007/978-3-642-38527-8_20

$Rev: 13581 $