<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1803</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2013-04-16</completedDate>
    <publishedDate>2013-04-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Undercover Branching</title>
    <abstract language="eng">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.&#13;
&#13;
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.&#13;
&#13;
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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-18030</identifier>
    <identifier type="doi">10.1007/978-3-642-38527-8_20</identifier>
    <enrichment key="SourceTitle">Appeared in: Experimental Algorithms.     12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings</enrichment>
    <author>Timo Berthold</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Ambros Gleixner</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-14</number>
    </series>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1803/ZR-13-14.pdf</file>
  </doc>
</export-example>
