<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1199</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-03-16</completedDate>
    <publishedDate>2011-03-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the computational impact of MIQCP solver components</title>
    <abstract language="eng">We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on linear outer approximation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.</abstract>
    <identifier type="serial">11-01</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11998</identifier>
    <author>Timo Berthold</author>
    <submitter>-empty- (Opus4 user: )</submitter>
    <author>Ambros Gleixner</author>
    <submitter>Timo Berthold</submitter>
    <author>Stefan Heinz</author>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-01</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIQCP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>mixed-integer quadratically constrained programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>computational</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>nonconvex</value>
    </subject>
    <collection role="ccs" number="G.4">MATHEMATICAL SOFTWARE</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C30">Nonlinear programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</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/1199/ZR-11-01.pdf</file>
  </doc>
  <doc>
    <id>1298</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-05-31</completedDate>
    <publishedDate>2011-05-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Large Neighborhood Search beyond MIP</title>
    <abstract language="eng">Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation.&#13;
&#13;
In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.</abstract>
    <identifier type="serial">11-21</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-12989</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 9th Metaheuristics International Conference (MIC 2011).  2011. Luca di Gaspar et al. eds. ISBN 978-88-900984-3-7, pp. 51-60</enrichment>
    <author>Timo Berthold</author>
    <submitter>Timo Berthold</submitter>
    <author>Stefan Heinz</author>
    <author>Marc Pfetsch</author>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-21</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Large Neighborhood Search</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Primal Heuristic</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIQCP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Pseudo-Boolean</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="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1298/lns4cip.pdf</file>
  </doc>
</export-example>
