<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>4254</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-09-23</completedDate>
    <publishedDate>2013-09-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Improving strong branching by domain propagation</title>
    <abstract language="eng">One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way.&#13;
This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-42546</identifier>
    <identifier type="doi">10.1007/s13675-014-0021-8</identifier>
    <enrichment key="SourceTitle">EURO Journal on Computational Optimization</enrichment>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>13-47</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branching rule</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>variable selection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>strong branching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>domain propagation</value>
    </subject>
    <collection role="ccs" number="G.4">MATHEMATICAL SOFTWARE</collection>
    <collection role="msc" number="90-08">Computational methods</collection>
    <collection role="msc" number="90B40">Search theory</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/4254/ZR-13-47.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/4254/ZR-13-47-RevisedVersion.pdf</file>
  </doc>
</export-example>
