<?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>
  <doc>
    <id>1770</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-12-21</completedDate>
    <publishedDate>2012-12-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Improving strong branching by propagation</title>
    <abstract language="eng">Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers.&#13;
It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small.&#13;
In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching.&#13;
Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-17701</identifier>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>12-46</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>strong branching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>domain propagation</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</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/1770/ZR-12-46.pdf</file>
  </doc>
  <doc>
    <id>6538</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-10-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Structure-driven fix-and-propagate heuristics for mixed integer programming</title>
    <abstract language="eng">Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-65387</identifier>
    <identifier type="doi">10.1007/s12532-019-00159-1</identifier>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-56</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>primal heuristics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>fix-and-propagate</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>large neighborhood search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>domain propagation</value>
    </subject>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="michael.winkler">Winkler, Michael</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6538/ZR-17-56.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/6538/ZR-17-56-revised.pdf</file>
  </doc>
</export-example>
