<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5382</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>2015-03-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Branching on multi-aggregated variables</title>
    <abstract language="eng">In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules.&#13;
We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-53829</identifier>
    <identifier type="doi">10.1007/978-3-319-18008-3_10</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-53829</enrichment>
    <enrichment key="SourceTitle">Integration of AI and OR Techniques in Constraint Programming</enrichment>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Anna Melchiori</author>
    <author>Timo Berthold</author>
    <author>Ambros Gleixner</author>
    <author>Domenico Salvagnin</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-10</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming, branch-and-bound, branching rule, strong branching</value>
    </subject>
    <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="berthold">Berthold, Timo</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="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/5382/ZR-15-10.pdf</file>
  </doc>
  <doc>
    <id>5750</id>
    <completedYear/>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>141</pageFirst>
    <pageLast>156</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>9075</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2015-04-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Branching on Multi-aggregated Variables</title>
    <abstract language="eng">In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules.&#13;
&#13;
We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.</abstract>
    <parentTitle language="eng">Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2015</parentTitle>
    <identifier type="doi">10.1007/978-3-319-18008-3_10</identifier>
    <enrichment key="Series">Lecture Notes in Computer Science</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-53829</enrichment>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Anna Melchiori</author>
    <author>Timo Berthold</author>
    <author>Ambros Gleixner</author>
    <author>Domenico Salvagnin</author>
    <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="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>
  </doc>
</export-example>
