<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>7496</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>2019-11-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Computational Aspects of Infeasibility Analysis in Mixed Integer Programming</title>
    <abstract language="eng">The analysis of infeasible subproblems plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications, obtained by domain propagation, that led to infeasibility. The result of this analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept is called conflict graph analysis and has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. Every ray of the dual LP provides a set of multipliers that can be used to generate a single new globally valid linear constraint. This method is called dual proof analysis. The main contribution of this paper is twofold. Firstly, we present three enhancements of dual proof analysis: presolving via variable cancellation, strengthening by applying mixed integer rounding functions, and a filtering mechanism. Further, we provide an intense computational study evaluating the impact of every presented component regarding dual proof analysis. Secondly, this paper presents the first integrated approach to use both conflict graph and dual proof analysis simultaneously within a single MIP solution process. All experiments are carried out on general MIP instances from the standard public test set MIPLIB 2017; the presented algorithms have been implemented within the non-commercial MIP solver SCIP and the commercial MIP solver FICO Xpress.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-74962</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Jakob Witzig</author>
    <submitter>Jakob Witzig</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <series>
      <title>ZIB-Report</title>
      <number>19-54</number>
    </series>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</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="heinz">Heinz, Stefan</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="BEAM-ME">BEAM-ME</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/7496/supplement.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/7496/ZR-19-54__Witzig_Berthold_Heinz__Computational_Aspects_of_Infeasibility_Analysis_in_MIP.pdf</file>
  </doc>
  <doc>
    <id>1775</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-02-14</completedDate>
    <publishedDate>2013-02-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Analyzing 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 a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86 publicly available test instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-17754</identifier>
    <identifier type="doi">10.3934/naco.2012.2.739</identifier>
    <enrichment key="SourceTitle">Appeared in: Numerical Algebra, Control and Optimization vol. 2, no. 4 (2012) pp. 739-748</enrichment>
    <author>Timo Berthold</author>
    <submitter>Timo Berthold</submitter>
    <author>Ambros Gleixner</author>
    <author>Stefan Heinz</author>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-08</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer quadratically constrained programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>nonconvex</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>global optimization</value>
    </subject>
    <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/1775/ZR-13-08.pdf</file>
  </doc>
  <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>1192</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-12-21</completedDate>
    <publishedDate>2010-12-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">ParaSCIP - a parallel extension of SCIP</title>
    <abstract language="eng">Mixed integer programming (MIP) has become one of the most important techniques in Operations Research and Discrete Optimization. SCIP (Solving Constraint Integer Programs) is currently one of the fastest non-commercial MIP solvers. It is based on the branch-and-bound procedure in which the problem is recursively split into smaller subproblems, thereby creating a so-called branching tree. We present ParaSCIP, an extension of SCIP, which realizes a parallelization on a distributed memory computing environment. ParaSCIP uses SCIP solvers as independently running processes to solve subproblems (nodes of the branching tree) locally. This makes the parallelization development independent of the SCIP development. Thus, ParaSCIP directly profits from any algorithmic progress in future versions of SCIP. Using a first implementation of ParaSCIP, we were able to solve two previously unsolved instances from MIPLIB2003, a standard test set library for MIP solvers. For these computations, we used up to 2048 cores of the HLRN~II supercomputer.</abstract>
    <identifier type="serial">10-27</identifier>
    <identifier type="doi">10.1007/978-3-642-24025-6_12</identifier>
    <identifier type="url">http://www.springerlink.com/content/t2160206253v7661/</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11921</identifier>
    <enrichment key="SourceTitle">Bischof, Christian et al. (eds.): Competence in High Performance Computing 2010. Proceedings of an International Conference on Competence in High Performance Computing, June 2010, Schloss Schwetzingen, Germany. Berlin: Springer, 2012, S. 135-148.</enrichment>
    <author>Yuji Shinano</author>
    <submitter>-empty- (Opus4 user: admin)</submitter>
    <author>Tobias Achterberg</author>
    <submitter>Stefan Heinz</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-27</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>massive parallization</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>ParaSCIP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>branch-and-cut</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>branch-and-bound</value>
    </subject>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="68W10">Parallel algorithms</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1192/ZR-10-27.pdf</file>
  </doc>
  <doc>
    <id>4288</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-10-21</completedDate>
    <publishedDate>2013-10-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving hard MIPLIB2003 problems with ParaSCIP on Supercomputers: An update</title>
    <abstract language="eng">Contemporary supercomputers can easily provide years of&#13;
 CPU time per wall-clock hour. One challenge of today's software&#13;
 development is how to harness this wast computing power in order to solve&#13;
really hard mixed integer  programming instances. In 2010,  two out of&#13;
six open MIPLIB2003 instances  could be solved by ParaSCIP in more than&#13;
ten consecutive runs, restarting from checkpointing files.&#13;
 The contribution of this paper is threefold:&#13;
For the first time, we present computational results of single runs for&#13;
those two instances. Secondly, we provide new improved upper and lower&#13;
bounds for all of the remaining four open MIPLIB2003 instances.&#13;
 Finally, we explain which new developments led to these results and&#13;
discuss the current progress of ParaSCIP. Experiments were conducted on&#13;
HLRNII, on HLRN III, and on the Titan supercomputer, using up to 35,200 cores.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-42888</identifier>
    <author>Yuji Shinano</author>
    <submitter>Yuji Shinano</submitter>
    <author>Tobias Achterberg</author>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-66</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIPLIB2003</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ParaSCIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ubiquity Generator Framework</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Supercomputer</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="persons" number="michael.winkler">Winkler, Michael</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/4288/zib-report-13-66.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/4288/ZR-13-66-revisedversion.pdf</file>
  </doc>
  <doc>
    <id>1813</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>jpn</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>2013-04-22</completedDate>
    <publishedDate>2013-04-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="jpn">制約整数計画ソルバ SCIP の並列化</title>
    <title language="eng">Parallelizing the Constraint Integer Programming Solver SCIP</title>
    <abstract language="jpn">制約整数計画(CIP: Constraint Integer Programming)は，制約プログラミング(CP: Constraint Programming)，混合整数計画(MIP: Mixed Integer Programming), 充足可能性問題(SAT: Satisfiability Problems)の研究分野におけるモデリング技術と解法を統合している．その結果，制約整数計画は，広いクラスの最適化問題を扱うことができる．SCIP (Solving Constraint Integer Programs)は，CIPを解くソルバとして実装され,Zuse Institute Berlin (ZIB)の研究者を中心として継続的に拡張が続けられている．本論文では，著者らによって開発されたSCIP に対する2種類の並列化拡張を紹介する． 一つは，複数計算ノード間で大規模に並列動作するParaSCIP である． もう一つは，複数コアと共有メモリを持つ１台の計算機上で(スレッド)並列で動作するFiberSCIP である． ParaSCIP は，HLRN IIスーパーコンピュータ上で， 一つのインスタンスを解くために最大7,168 コアを利用した動作実績がある．また，統計数理研究所のFujitsu PRIMERGY RX200S5上でも，最大512コアを利用した動作実績がある．統計数理研究所のFujitsu PRIMERGY RX200S5上 では，これまでに最適解が得られていなかったMIPLIB2010のインスタンスであるdg012142に最適解を与えた．</abstract>
    <abstract language="eng">The paradigm of Constraint Integer Programming (CIP) combines modeling and solving techniques from the fields of Constraint Programming (CP), Mixed Integer Programming (MIP) and Satisfiability Problems (SAT). The paradigm allows us to address a wide range of optimization problems. SCIP is an implementation of the idea of CIP and is now continuously extended by a group of researchers centered at Zuse Institute Berlin (ZIB). This paper introduces two parallel extensions of SCIP. One is ParaSCIP, which is intended to run on a large scale distributed memory computing environment, and the other is FiberSCIP, intended to run on shared memory computing environments. ParaSCIP has successfully been run on the HLRN II supercomputer utilizing up to 7,168 cores to solve a single difficult MIP. It has also been tested on an ISM supercomputer (Fujitsu PRIMERGY RX200S5 using up to 512 cores). The previously unsolved instance dg012142 from MIPLIB2010 was solved by using the ISM supercomputer.</abstract>
    <additionalTitle language="eng">Parallelizing the Constraint Integer Programming Solver SCIP</additionalTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-18130</identifier>
    <author>Yuji Shinano</author>
    <submitter>Yuji Shinano</submitter>
    <author>Tobias Achterberg</author>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Stefan Vigerske</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-22</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Constraint Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parallel Computing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Distributed Memory</value>
    </subject>
    <collection role="msc" number="68W10">Parallel algorithms</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</collection>
    <collection role="persons" number="michael.winkler">Winkler, Michael</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1813/para-scip.pdf</file>
  </doc>
  <doc>
    <id>1559</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>jpn</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-07-25</completedDate>
    <publishedDate>2012-07-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="jpn">SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法</title>
    <title language="eng">Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite</title>
    <abstract language="jpn">この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し，その３つの構成要素：モデリン&#13;
グ言語Zimpl, 線形計画（LP: linear programming) ソルバSoPlex, そして，制約整数計画(CIP: constraint&#13;
integer programming) に対するソフトウェア・フレームワークSCIP, について述べる．本論文では，この３つの&#13;
構成要素を利用して，どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization&#13;
problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化&#13;
し解くのかを説明する．SCIP は，現在，最も高速なMIP,MINLP ソルバの１つである．いくつかの例により，&#13;
Zimpl, SCIP, SoPlex の利用方法を示すとともに，利用可能なインタフェースの概要を示す．最後に，将来の開&#13;
発計画の概要について述べる．</abstract>
    <abstract language="eng">This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how in concert these can be used to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview over available interfaces, and outline plans for future development.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15598</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming. Masakazu Muramatsu (ed. ) 2012, pp. 165-192</enrichment>
    <author>Timo Berthold</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Ambros Gleixner</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Yuji Shinano</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-24</number>
    </series>
    <subject>
      <language>mul</language>
      <type>uncontrolled</type>
      <value>SCIP, MIP, MINLP, CIP, LP, modeling, optimization</value>
    </subject>
    <collection role="msc" number="90C05">Linear programming</collection>
    <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="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</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/1559/ZR-12-24.pdf</file>
  </doc>
  <doc>
    <id>1067</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-03-03</completedDate>
    <publishedDate>2008-03-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Pseudo-Boolean Problems with SCIP</title>
    <abstract language="eng">Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field. In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.</abstract>
    <identifier type="serial">08-12</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1095</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10671</identifier>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-12</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Pseudo-Boolean</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Branch-And-Cut</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierungssoftware</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Pseudo-Boolean</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization software</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</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="90C27">Combinatorial optimization</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.orig.Vers.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.orig.Vers.ps</file>
  </doc>
  <doc>
    <id>1295</id>
    <completedYear>2010</completedYear>
    <publishedYear>2010</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">MIPLIB 2010</title>
    <abstract language="eng">This paper reports on the fifth version of the Mixed Integer Programming Library.  &#13;
The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups.&#13;
This includes the main benchmark test set of 87 instances, which&#13;
are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved.&#13;
For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to&#13;
test the accuracy of provided solutions using exact arithmetic.</abstract>
    <identifier type="serial">10-31</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-12953</identifier>
    <identifier type="doi">10.1007/s12532-011-0025-9</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Programming Computation vol. 3 iss. 2 (2011), pp. 103-163</enrichment>
    <author>Thorsten Koch</author>
    <submitter>Timo Berthold</submitter>
    <author>Tobias Achterberg</author>
    <author>Erling Andersen</author>
    <author>Oliver Bastert</author>
    <author>Timo Berthold</author>
    <author>Robert E. Bixby</author>
    <author>Emilie Danna</author>
    <author>Gerald Gamrath</author>
    <author>Ambros Gleixner</author>
    <author>Stefan Heinz</author>
    <author>Andrea Lodi</author>
    <author>Hans Mittelmann</author>
    <author>Ted Ralphs</author>
    <author>Domenico Salvagnin</author>
    <author>Daniel Steffy</author>
    <author>Kati Wolter</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-31</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Problem Instances</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>IP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIPLIB</value>
    </subject>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</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="koch">Koch, Thorsten</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="projects" number="SPP1307-ExactIP">SPP1307-ExactIP</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1295/miplib5.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1295/miplib5.ps</file>
  </doc>
  <doc>
    <id>1565</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-07-31</completedDate>
    <publishedDate>2012-07-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite</title>
    <abstract language="eng">This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how these can be used in concert to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview of available interfaces, and outline plans for future development.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15654</identifier>
    <author>Timo Berthold</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Gerald Gamrath</author>
    <author>Ambros Gleixner</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Yuji Shinano</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-27</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl</value>
    </subject>
    <collection role="msc" number="90C05">Linear programming</collection>
    <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="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</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/1565/ZR-12-27.pdf</file>
  </doc>
  <doc>
    <id>1137</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-07-09</completedDate>
    <publishedDate>2009-07-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Extending a CIP framework to solve MIQCPs</title>
    <abstract language="eng">This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.</abstract>
    <identifier type="serial">09-23</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1186</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11371</identifier>
    <enrichment key="SourceTitle">App. in: Mixed Integer Nonlinear Programming. Jon Lee, Sven Leyffer (eds.) The IMA Volumes in Mathematics and its Applications, 154. Springer 2011, pp. 427-444</enrichment>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-23</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer quadratically constrained programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>convex relaxation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>nonconvex</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C20">Quadratic programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</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="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/1137/ZR_09_23rev.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23rev.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.ps</file>
  </doc>
  <doc>
    <id>4994</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>2014-05-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Jack of all Trades? Solving stochastic mixed-integer nonlinear constraint programs</title>
    <abstract language="eng">Natural gas is one of the most important energy sources in Germany and Europe.  In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate.&#13;
&#13;
Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems.&#13;
&#13;
The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-49947</identifier>
    <identifier type="doi">10.4171/137</identifier>
    <enrichment key="SourceTitle">Appeared in: Matheon - Mathematics for Key Technologies. EMS 2014, pp. 135-146</enrichment>
    <author>Thomas Arnold</author>
    <submitter>Timo Berthold</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Stefan Vigerske</author>
    <author>René Henrion</author>
    <author>Martin Grötschel</author>
    <author>Thorsten Koch</author>
    <author>Caren Tischendorf</author>
    <author>Werner Römisch</author>
    <series>
      <title>ZIB-Report</title>
      <number>14-14</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>gas transport optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer nonlinear programming</value>
    </subject>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/4994/B-koch-thorsten.pdf</file>
  </doc>
  <doc>
    <id>5551</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-07-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Structure-based primal heuristics for mixed integer programming</title>
    <abstract language="eng">Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-55518</identifier>
    <identifier type="doi">http://dx.doi.org/10.1007/978-4-431-55420-2_3</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-55518</enrichment>
    <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>15-26</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming, large neighborhood search, primal heuristics, 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/5551/ZR-15-26.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>
