<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>862</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-05-04</completedDate>
    <publishedDate>2005-05-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">MIPLIB 2003</title>
    <abstract language="eng">This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances.</abstract>
    <identifier type="serial">05-28</identifier>
    <identifier type="opus3-id">862</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8625</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Letters 34 (2006), Nr. 4, 1-12. DOI 10.1016/j.orl.2005.07.009</enrichment>
    <author>Tobias Achterberg</author>
    <author>Thorsten Koch</author>
    <author>Alexander Martin</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-28</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mathematical Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>IP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Instances</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C06">Large-scale problems</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/862/ZR-05-28.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/862/ZR-05-28.ps</file>
  </doc>
  <doc>
    <id>853</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-03-22</completedDate>
    <publishedDate>2005-03-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Conflict Analysis in Mixed Integer Programming</title>
    <abstract language="eng">Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal. In this paper we try to remedy this situation by generalizing the SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50\% in the geometric mean. However, the total solving time increased by 15\%. on infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90\%, thereby reducing the solving time by 60\%.</abstract>
    <identifier type="serial">05-19</identifier>
    <identifier type="opus3-id">853</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8537</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Optimization 4 (2007) 4-20</enrichment>
    <author>Tobias Achterberg</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-19</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 cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>conflict analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="G.4">MATHEMATICAL SOFTWARE</collection>
    <collection role="ccs" number="I.2.3">Deduction and Theorem Proving (F.4.1)</collection>
    <collection role="ccs" number="I.2.8">Problem Solving, Control Methods, and Search (F.2.2)</collection>
    <collection role="msc" number="90-08">Computational methods</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/853/ZR-05-19.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/853/ZR-05-19.ps</file>
  </doc>
  <doc>
    <id>917</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2006-05-05</completedDate>
    <publishedDate>2006-05-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Software for Teaching Modeling of Integer Programming Problems</title>
    <abstract language="eng">Modern applications of mathematical programming must take into account a multitude of technical details, business demands, and legal requirements. Teaching the mathematical modeling of such issues and their interrelations requires real-world examples that are well beyond the toy sizes that can be tackled with the student editions of most commercial software packages. We present a new tool, which is freely available for academic use including complete source code. It consists of an algebraic modeling language and a linear mixed integer programming solver. The performance and features of the tool are in the range of current state-of-the-art commercial tools, though not in all aspects as good as the best ones. Our tool does allow the execution and analysis of large real-world instances in the classroom and can therefore enhance the teaching of problem solving issues. Teaching experience has been gathered and practical usability was tested in classes at several universities and a two week intensive block course at TU Berlin. The feedback from students and teachers has been very positive.</abstract>
    <identifier type="serial">06-23</identifier>
    <identifier type="opus3-id">917</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9176</identifier>
    <author>Tobias Achterberg</author>
    <author>Martin Grötschel</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>06-23</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Modelling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIP-Solver</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Algebraic Modelling Languages</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Teaching</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68N99">None of the above, but in this section</collection>
    <collection role="msc" number="90-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="97-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="97U70">Technological tools. Calculators</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/917/ZR-06-23.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/917/ZR-06-23.ps</file>
  </doc>
  <doc>
    <id>794</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2004-05-28</completedDate>
    <publishedDate>2004-05-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">SCIP - a framework to integrate Constraint and Mixed Integer Programming</title>
    <abstract language="eng">Constraint Programs and Mixed Integer Programs are closely related optimization problems originating from different scientific areas. Today's state-of-the-art algorithms of both fields have several strategies in common, in particular the branch-and-bound process to recursively divide the problem into smaller sub problems. On the other hand, the main techniques to process each sub problem are different, and it was observed that they have complementary strenghts. We propose a programming framework {\sffamily SCIP} that integrates techniques from both fields in order to exploit the strenghts of both, Constraint Programming and Mixed Integer Programming. In contrast to other proposals of recent years to combine both fields, {\sffamily SCIP} does not focus on easy implementation and rapid prototyping, but is tailored towards expert users in need of full, in-depth control and high performance.</abstract>
    <identifier type="serial">04-19</identifier>
    <identifier type="opus3-id">795</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7947</identifier>
    <author>Tobias Achterberg</author>
    <series>
      <title>ZIB-Report</title>
      <number>04-19</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Constraint Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>CP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-bound</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="90-08">Computational methods</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="">ZIB Allgemein</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="projects" number="ZIB-Infeas">ZIB-Infeas</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/794/ZR-04-19.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/794/ZR-04-19.pdf</file>
  </doc>
  <doc>
    <id>875</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-09-16</completedDate>
    <publishedDate>2005-09-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Improving the Feasibility Pump</title>
    <abstract language="eng">The Feasibility Pump of Fischetti, Glover, Lodi, and Bertacco has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, tends to be poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: in 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original Feasibility Pump.</abstract>
    <identifier type="serial">05-42</identifier>
    <identifier type="opus3-id">875</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8754</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Optimization 4 (2007) 77-86</enrichment>
    <author>Tobias Achterberg</author>
    <author>Timo Berthold</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-42</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>feasibility pump</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90-08">Computational methods</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/875/ZR-05-42.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/875/ZR-05-42.ps</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>1080</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-08-05</completedDate>
    <publishedDate>2008-08-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Effects of Minor Changes in Model Formulations</title>
    <abstract language="eng">Starting with the description of the Traveling Salesmen Problem formulation as given by van Vyve and Wolsey in the article Approximate extended formulations'', we investigate the effects of small variations onto the performance of contemporary mixed integer programming solvers. We will show that even minor changes in the formulation of the model can result in performance difference of more than a factor of 1000. As the results show it is not obvious which changes will result in performance improvements and which not.</abstract>
    <identifier type="serial">08-29</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1115</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10808</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Thorsten Koch</author>
    <author>Andreas Tuchscherer</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-29</number>
    </series>
    <collection role="ddc" number="510">Mathematik</collection>
    <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="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="MATHEON-B14:Comb-Log">MATHEON-B14:Comb-Log</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1080/ZR_08_29.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1080/ZR_08_29.ps</file>
  </doc>
  <doc>
    <id>1052</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-01-04</completedDate>
    <publishedDate>2008-01-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming: a New Approach to Integrate CP and MIP</title>
    <abstract language="eng">This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving. SCIP is available in source code and free for non-commercial use. We demonstrate the usefulness of CIP on two tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.</abstract>
    <identifier type="serial">08-01</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1081</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10520</identifier>
    <enrichment key="SourceTitle">Appeared in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008 (L. Perron und M. A. Trick, eds.), Lecture Notes in Computer Science, 5015, 2008, pp. 6–20</enrichment>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Timo Berthold</author>
    <author>Thorsten Koch</author>
    <author>Kati Wolter</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-01</number>
    </series>
    <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>deu</language>
      <type>uncontrolled</type>
      <value>Chipverifikation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint 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>optimization software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chip verification</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="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1052/ZR_08_01.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1052/ZR_08_01.ps</file>
  </doc>
  <doc>
    <id>1037</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-11-21</completedDate>
    <publishedDate>2007-11-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Property Checking with Constraint Integer Programming</title>
    <abstract language="eng">We address the property checking problem for SoC design verification at the register transfer level (RTL) by integrating techniques from integer programming, constraint programming, and SAT solving. Specialized domain propagation and preprocessing algorithms for individual RTL operations extend a general constraint integer programming framework. Conflict clauses are learned by analyzing infeasible LPs and deductions, and by employing reverse propagation. Experimental results show that our approach outperforms SAT techniques for proving the validity of properties on circuits containing arithmetics.</abstract>
    <identifier type="serial">07-37</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1065</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10376</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Raik Brinkmann</author>
    <author>Markus Wedler</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-37</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>formale Chip Verifikation</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>scip</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Eigenschaftsprüfer</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>formal chip verification</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>scip</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>property checking</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>micro chip</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90-04">Explicit machine computation and programs (not the theory of computation or programming)</collection>
    <collection role="msc" number="90-08">Computational methods</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="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1037/ZR_07_37.pdf</file>
  </doc>
  <doc>
    <id>1018</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-10-15</completedDate>
    <publishedDate>2007-10-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming</title>
    <abstract language="eng">This thesis introduces the novel paradigm of constraint integer programming (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method.</abstract>
    <abstract language="deu">Diese Arbeit stellt einen integrierten Ansatz aus Constraint Programming (CP) und Gemischt-Ganzzahliger Programmierung (Mixed Integer Programming, MIP) vor, den wir Constraint Integer Programming (CIP) nennen. Sowohl Modellierungs- als auch Lösungstechniken beider Felder fließen in den neuen integrierten Ansatz ein, um die unterschiedlichen Stärken der beiden Gebiete zu kombinieren. Als weiteren Beitrag stellen wir der wissenschaftlichen Gemeinschaft die Software SCIP zur Verfügung, die ein Framework für Constraint Integer Programming darstellt und zusätzlich Techniken des SAT-Lösens beinhaltet. SCIP ist im Source Code für akademische und nicht-kommerzielle Zwecke frei erhältlich. Unser Ansatz des Constraint Integer Programming ist eine Verallgemeinerung von MIP, die zusätzlich die Verwendung beliebiger Constraints erlaubt, solange sich diese durch lineare Bedingungen ausdrücken lassen falls alle ganzzahligen Variablen auf feste Werte eingestellt sind. Die Constraints werden von einer beliebigen Kombination aus CP- und MIP-Techniken behandelt. Dies beinhaltet insbesondere die Domain Propagation, die Relaxierung der Constraints durch lineare Ungleichungen, sowie die Verstärkung der Relaxierung durch dynamisch generierte Schnittebenen. Die derzeitige Version von SCIP enthält alle Komponenten, die für das effiziente Lösen von Gemischt-Ganzzahligen Programmen benötigt werden. Die vorliegende Arbeit liefert eine ausführliche Beschreibung dieser Komponenten und bewertet verschiedene Varianten in Hinblick auf ihren Einfluß auf das Gesamt-Lösungsverhalten anhand von aufwendigen praktischen Experimenten. Dabei wird besonders auf die algorithmischen Aspekte eingegangen. Der zweite Hauptteil der Arbeit befasst sich mit der Chip-Design-Verifikation, die ein wichtiges Thema innerhalb des Fachgebiets der Electronic Design Automation darstellt. Chip-Hersteller müssen sicherstellen, dass der logische Entwurf einer Schaltung der gegebenen Spezifikation entspricht. Andernfalls würde der Chip fehlerhaftes Verhalten aufweisen, dass zu Fehlfunktionen innerhalb des Gerätes führen kann, in dem der Chip verwendet wird. Ein wichtiges Teilproblem in diesem Feld ist das Eigenschafts-Verifikations-Problem, bei dem geprüft wird, ob der gegebene Schaltkreisentwurf eine gewünschte Eigenschaft aufweist. Wir zeigen, wie dieses Problem als Constraint Integer Program modelliert werden kann und geben eine Reihe von problemspezifischen Algorithmen an, die die Struktur der einzelnen Constraints und der Gesamtschaltung ausnutzen. Testrechnungen auf Industrie-Beispielen vergleichen unseren Ansatz mit den bisher verwendeten SAT-Techniken und belegen den Erfolg unserer Methode.</abstract>
    <identifier type="opus3-id">1038</identifier>
    <identifier type="urn">urn:nbn:de:kobv:83-opus-16117</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <advisor>Martin Grötschel</advisor>
    <advisor>Robert E. Bixby</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Chip-Verifikation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chip verification</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="ccs" number="B.8.1">Reliability, Testing, and Fault-Tolerance (NEW)</collection>
    <collection role="ccs" number="G.1.6">Optimization</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1018/achterberg_tobias.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1018/Achterberg_Constraint_Integer_ProgrammingDissZweite_Vers.pdf</file>
  </doc>
  <doc>
    <id>6037</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>2016-12-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Presolve Reductions in Mixed Integer Programming</title>
    <abstract language="eng">Mixed integer programming has become a very powerful tool for modeling and&#13;
solving real-world planning and scheduling problems, with the breadth of&#13;
applications appearing to be almost unlimited.   A critical component in&#13;
the solution of these mixed-integer programs is a set of routines commonly&#13;
referred to as presolve.  Presolve can be viewed as a collection of&#13;
preprocessing techniques that reduce the size of and, more importantly,&#13;
improve the ``strength'' of the given model formulation, that is, the degree&#13;
to which the constraints of the formulation accurately describe the&#13;
underlying polyhedron of integer-feasible solutions.  As our computational&#13;
results will show, presolve is a key factor in the speed with which we can&#13;
solve mixed-integer programs, and is often the difference between a model&#13;
being intractable and solvable, in some cases easily solvable.  In this&#13;
paper we describe the presolve functionality in the Gurobi commercial&#13;
mixed-integer programming code.&#13;
This includes an overview, or taxonomy of the different methods that are&#13;
employed, as well as more-detailed descriptions of several of the techniques,&#13;
with some of them appearing, to our knowledge, for the first time in the&#13;
literature.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-60370</identifier>
    <author>Tobias Achterberg</author>
    <submitter>Tobias Achterberg</submitter>
    <author>Robert E. Bixby</author>
    <author>Zonghao Gu</author>
    <author>Edward Rothberg</author>
    <author>Dieter Weninger</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-44</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>presolving</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Gurobi</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="msc" number="90-04">Explicit machine computation and programs (not the theory of computation or 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="achterberg">Achterberg, Tobias</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</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/6037/Presolve.pdf</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>1325</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-07-14</completedDate>
    <publishedDate>2011-07-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Rounding and Propagation Heuristics for Mixed Integer Programming</title>
    <abstract language="eng">Primal heuristics are an important component of state-of-the-art codes for&#13;
mixed integer programming. In this paper, we focus on primal heuristics&#13;
that only employ computationally inexpensive procedures such as rounding&#13;
and logical deductions (propagation). We give an overview of eight&#13;
different approaches. To assess the impact of these primal  heuristics on&#13;
the ability to find feasible solutions, in particular early during search,&#13;
we introduce a new performance measure, the primal integral. Computational&#13;
experiments evaluate this and other measures on MIPLIB~2010 benchmark&#13;
instances.</abstract>
    <identifier type="serial">11-29</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-13255</identifier>
    <identifier type="doi">10.1007/978-3-642-29210-1_12</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2011. Diethard Klatte et al. (eds.) Springer 2012, pp. 71-76</enrichment>
    <author>Tobias Achterberg</author>
    <submitter>Timo Berthold</submitter>
    <author>Timo Berthold</author>
    <author>Gregor Hendel</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-29</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>primal heuristic</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>domain propagation</value>
    </subject>
    <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="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="hendel">Hendel, Gregor</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/1325/ZR-11-29.pdf</file>
  </doc>
  <doc>
    <id>1159</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-11-30</completedDate>
    <publishedDate>2009-11-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The MCF-Separator --  Detecting and Exploiting Multi-Commodity Flow Structures in MIPs</title>
    <abstract language="eng">Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity-flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of SCIP and CPLEX. We make use of the complemented mixed integer rounding framework (cMIR) but provide a special purpose aggregation heuristic that exploits the network structure. Our separation scheme speeds-up the computation for a large set of MIPs coming from network design problems by a factor of two on average.</abstract>
    <identifier type="serial">09-38</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1218</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11592</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Christian Raack</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>network detection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cut-based inequalities</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cplex</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>scip</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</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="achterberg">Achterberg, Tobias</collection>
    <collection role="projects" number="MATHEON-B3">MATHEON-B3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1159/ZR_09_38.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1159/ZR_09_38.ps</file>
  </doc>
  <doc>
    <id>1112</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-01-28</completedDate>
    <publishedDate>2009-01-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming</title>
    <abstract language="eng">This thesis introduces the novel paradigm of "constraint integer programming" (CIP), which integrates constraint programming (CP) and mixed integer programming (MIP) modeling and solving techniques. It is supplemented by the software SCIP, which is a solver and framework for constraint integer programming that also features SAT solving techniques. SCIP is freely available in source code for academic and non-commercial purposes. Our constraint integer programming approach is a generalization of MIP that allows for the inclusion of arbitrary constraints, as long as they turn into linear constraints on the continuous variables after all integer variables have been fixed. The constraints, may they be linear or more complex, are treated by any combination of CP and MIP techniques: the propagation of the domains by constraint specific algorithms, the generation of a linear relaxation and its solving by LP methods, and the strengthening of the LP by cutting plane separation. The current version of SCIP comes with all of the necessary components to solve mixed integer programs. In the thesis, we cover most of these ingredients and present extensive computational results to compare different variants for the individual building blocks of a MIP solver. We focus on the algorithms and their impact on the overall performance of the solver. In addition to mixed integer programming, the thesis deals with chip design verification, which is an important topic of electronic design automation. Chip manufacturers have to make sure that the logic design of a circuit conforms to the specification of the chip. Otherwise, the chip would show an erroneous behavior that may cause failures in the device where it is employed. An important subproblem of chip design verification is the property checking problem, which is to verify whether a circuit satisfies a specified property. We show how this problem can be modeled as constraint integer program and provide a number of problem-specific algorithms that exploit the structure of the individual constraints and the circuit as a whole. Another set of extensive computational benchmarks compares our CIP approach to the current state-of-the-art SAT methodology and documents the success of our method.</abstract>
    <abstract language="deu">Diese Arbeit stellt einen integrierten Ansatz aus "Constraint Programming" (CP) und Gemischt-Ganzzahliger Programmierung ("Mixed Integer Programming", MIP) vor, den wir "Constraint Integer Programming" (CIP) nennen. Sowohl Modellierungs- als auch Lösungstechniken beider Felder fließen in den neuen integrierten Ansatz ein, um die unterschiedlichen Stärken der beiden Gebiete zu kombinieren. Als weiteren Beitrag stellen wir der wissenschaftlichen Gemeinschaft die Software SCIP zur Verfügung, die ein Framework für Constraint Integer Programming darstellt und zusätzlich Techniken des SAT-Lösens beinhaltet. SCIP ist im Source Code für akademische und nicht-kommerzielle Zwecke frei erhältlich. Unser Ansatz des Constraint Integer Programming ist eine Verallgemeinerung von MIP, die zusätzlich die Verwendung beliebiger Constraints erlaubt, solange sich diese durch lineare Bedingungen ausdrücken lassen falls alle ganzzahligen Variablen auf feste Werte eingestellt sind. Die Constraints werden von einer beliebigen Kombination aus CP- und MIP-Techniken behandelt. Dies beinhaltet insbesondere die "Domain Propagation", die Relaxierung der Constraints durch lineare Ungleichungen, sowie die Verstärkung der Relaxierung durch dynamisch generierte Schnittebenen. Die derzeitige Version von SCIP enthält alle Komponenten, die für das effiziente Lösen von Gemischt-Ganzzahligen Programmen benötigt werden. Die vorliegende Arbeit liefert eine ausführliche Beschreibung dieser Komponenten und bewertet verschiedene Varianten in Hinblick auf ihren Einfluß auf das Gesamt-Lösungsverhalten anhand von aufwendigen praktischen Experimenten. Dabei wird besonders auf die algorithmischen Aspekte eingegangen. Ein weiterer Hauptteil der Arbeit befasst sich mit der Chip-Design-Verifikation, die ein wichtiges Thema innerhalb des Fachgebiets der "Electronic Design Automation" darstellt. Chip-Hersteller müssen sicherstellen, dass der logische Entwurf einer Schaltung der gegebenen Spezifikation entspricht. Andernfalls würde der Chip fehlerhaftes Verhalten aufweisen, dass zu Fehlfunktionen innerhalb des Gerätes führen kann, in dem der Chip verwendet wird. Ein wichtiges Teilproblem in diesem Feld ist das Eigenschafts-Verifikations-Problem, bei dem geprüft wird, ob der gegebene Schaltkreisentwurf eine gewünschte Eigenschaft aufweist. Wir zeigen, wie dieses Problem als Constraint Integer Program modelliert werden kann und geben eine Reihe von problemspezifischen Algorithmen an, die die Struktur der einzelnen Constraints und der Gesamtschaltung ausnutzen. Testrechnungen auf Industrie-Beispielen vergleichen unseren Ansatz mit den bisher verwendeten SAT-Techniken und belegen den Erfolg unserer Methode.</abstract>
    <identifier type="opus3-id">1153</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11129</identifier>
    <enrichment key="SourceTitle">Buchveröffentlichung: Tobias Achterberg: Constraint Integer Programming. Dr. Hut Verl. 2008. ISBN 978-3-89963-892-9</enrichment>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <advisor>Martin Grötschel</advisor>
    <advisor>Robert E. Bixby</advisor>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Chip-Verifikation</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mathematische Programmierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Constraint Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SAT</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Chip Verification</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mathematical Programming</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1112/Achterberg_Constraint_Integer_Programming.pdf</file>
  </doc>
</export-example>
