<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5640</id>
    <completedYear/>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2015-10-27</completedDate>
    <publishedDate>2015-10-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores</title>
    <abstract language="eng">This paper describes how we solved 12 previously unsolved mixed-integer program-&#13;
ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we&#13;
used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP&#13;
computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper&#13;
we describe the basic parallelization mechanism of ParaSCIP, improvements of the&#13;
dynamic load balancing and novel techniques to exploit the power of parallelization&#13;
for MIP solving. We give a detailed overview of computing times and statistics for&#13;
solving open MIPLIB instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-56404</identifier>
    <identifier type="doi">10.1109/IPDPS.2016.56</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of 30th IEEE International Parallel &amp; Distributed Processing Symposium</enrichment>
    <submitter>Yuji Shinano</submitter>
    <author>Yuji Shinano</author>
    <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>15-53</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parallel processing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Node merging</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Racing ParaSCIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ubiquity Generator Framework</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIPLIB</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="ccs" number="I.">Computing Methodologies</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL 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="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</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/5640/ZR-15-53.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/5640/ZR-15-53-rev.pdf</file>
  </doc>
  <doc>
    <id>7171</id>
    <completedYear/>
    <publishedYear>2019</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>675</pageFirst>
    <pageLast>702</pageLast>
    <pageNumber/>
    <edition/>
    <issue>4</issue>
    <volume>11</volume>
    <type>article</type>
    <publisherName>Springer</publisherName>
    <publisherPlace>Berlin Heidelberg</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2019-04-06</completedDate>
    <publishedDate>--</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 and help to reduce the time needed to prove optimality. In this paper, we present a scheme for 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 first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. 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 60 % of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.</abstract>
    <parentTitle language="eng">Mathematical Programming Computation</parentTitle>
    <identifier type="doi">10.1007/s12532-019-00159-1</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2019-03-12</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-65387</enrichment>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Michael Winkler</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="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>
  </doc>
  <doc>
    <id>9057</id>
    <completedYear/>
    <publishedYear>2013</publishedYear>
    <thesisYearAccepted/>
    <language>jpn</language>
    <pageFirst>47</pageFirst>
    <pageLast>78</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>61</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="jpn">制約整数計画ソルバ SCIP の並列化</title>
    <abstract language="jpn">制約整数計画（CIP: Constraint Integer Programs）は，制約プログラミング（CP: Constraint Programming），混合整数計画（MIP: Mixed Integer Programming），充足可能性問題（SAT: Satisfability Problem）の研究分野におけるモデリング技術と解法を統合している．その結果，制約整数計画は，広いクラスの最適化問題を扱うことができる．SCIP（Solving Constraint Integer Programs）は，CIP を解くソルバとして実装され，Zuse Institute Berlin（ZIB）の研究者を中心として継続的に拡張が続けられている．本論文では，著者らによって開発された SCIP に対する2 種類の並列化拡張を紹介する．一つは，複数計算ノード間で大規模に並列動作する ParaSCIPである．もう一つは，複数コアと共有メモリを持つ 1 台の計算機上で（スレッド）並列で動作する 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　satisfability problem (SAT). This paradigm allows us to address a wide　range of optimization problems. SCIP is an implementation of the idea of CIP and is now being 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 a shared memory computing environment. ParaSCIP has been run successfully 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>
    <parentTitle language="jpn">統計数理</parentTitle>
    <identifier type="url">https://www.ism.ac.jp/editsec/toukei/pdf/61-1-047.pdf</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="SubmissionStatus">in press</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <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>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="institutes" number="aim">Applied Algorithmic Intelligence Methods</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7839</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2020-05-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Previously Unsolved MIP Instances with ParaSCIP on Supercomputers by using up to 80,000 Cores</title>
    <abstract language="deu">Mixed-integer programming (MIP) problem is arguably among the hardest classes of optimization problems. This paper describes how we solved 21 previously unsolved MIP instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper, we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-78393</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>20-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming, Parallel processing, Node merging, Racing, ParaSCIP,  Ubiquity Generator Framework, MIPLIB</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</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="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/7839/ZIB-Report_20-16.pdf</file>
  </doc>
  <doc>
    <id>5751</id>
    <completedYear/>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>37</pageFirst>
    <pageLast>53</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>13</volume>
    <type>bookpart</type>
    <publisherName>Springer Japan</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</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>
    <parentTitle language="eng">Optimization in the Real World</parentTitle>
    <identifier type="isbn">978-4-431-55419-6</identifier>
    <identifier type="doi">10.1007/978-4-431-55420-2_3</identifier>
    <enrichment key="Series">Mathematics for Industry</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <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>
    <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>
  </doc>
  <doc>
    <id>1408</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-09-29</completedDate>
    <publishedDate>2011-09-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving steel mill slab design problems</title>
    <abstract language="eng">The steel mill slab design problem from the CSPLIB is a combinatorial&#13;
optimization problem motivated by an application of the steel industry. It&#13;
has been widely studied in the constraint programming community.  Several&#13;
methods were proposed to solve this problem. A steel mill slab library was&#13;
created which contains 380 instances. A closely related binpacking problem&#13;
called the multiple knapsack problem with color constraints, originated&#13;
from the same industrial problem, was discussed in the integer programming&#13;
community. In particular, a simple integer program for this problem has&#13;
been given by Forrest et al. The aim of this paper is to bring these&#13;
different studies together. Moreover, we adapt the model of Forrest et&#13;
al. for the steel mill slab design problem. Using this model and a&#13;
state-of-the-art integer program solver all instances of the steel mill&#13;
slab library can be solved efficiently to optimality.  We improved,&#13;
thereby, the solution values of 76 instances compared to previous results.&#13;
Finally, we consider a recently introduced variant of the steel mill slab&#13;
design problem, where within all solutions which minimize the leftover one&#13;
is interested in a solution which requires a minimum number of slabs. For&#13;
that variant we introduce two approaches and solve all instances of the&#13;
steel mill slab library with this slightly changed objective function to&#13;
optimality.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">11-38</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14089</identifier>
    <identifier type="doi">10.1007/s10601-011-9113-8</identifier>
    <enrichment key="SourceTitle">Appeared in: Constraints 17 (2012) 39-50</enrichment>
    <author>Stefan Heinz</author>
    <submitter>Stefan Heinz</submitter>
    <author>Thomas Schlechte</author>
    <author>Rüdiger Stephan</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>steel mill slab design problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>multiple knapsack problem with color constraints</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>set partitioning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>binpacking with side constraints</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="msc" number="90Cxx">Mathematical programming [See also 49Mxx, 65Kxx]</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</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/1408/ZR-11-38.pdf</file>
  </doc>
  <doc>
    <id>4731</id>
    <completedYear/>
    <publishedYear>2012</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>39</pageFirst>
    <pageLast>50</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>17</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving steel mill slab design problems</title>
    <abstract language="eng">The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129–134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129–134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125–147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.</abstract>
    <parentTitle language="eng">Constraints</parentTitle>
    <identifier type="doi">10.1007/s10601-011-9113-8</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-14089</enrichment>
    <author>Stefan Heinz</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Thomas Schlechte</author>
    <author>Rüdiger Stephan</author>
    <author>Michael Winkler</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="michael.winkler">Winkler, Michael</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </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>4259</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2013-09-27</completedDate>
    <publishedDate>2013-09-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">FiberSCIP - A shared memory parallelization of SCIP</title>
    <abstract language="eng">Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-42595</identifier>
    <identifier type="doi">10.1287/ijoc.2017.0762</identifier>
    <enrichment key="SourceTitle">INFORMS Journal on Computing</enrichment>
    <author>Yuji Shinano</author>
    <submitter>Yuji Shinano</submitter>
    <author>Stefan Heinz</author>
    <author>Stefan Vigerske</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-55</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>parallel</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>deterministic parallelism</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer nonlinear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SCIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MINLP</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="msc" number="68-XX">COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</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="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</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/4259/fiberscip-zib.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/4259/fiberscip-zib-rev3.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>6739</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>11</pageFirst>
    <pageLast>30</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>30</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2017-11-01</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">FiberSCIP - A shared memory parallelization of SCIP</title>
    <abstract language="eng">Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a mixed-integer linear programming solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, we present the basic concept of having two parallel extensions, and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator), including an implementation of deterministic parallelization. Second, we discuss the difficulties in achieving a good performance that utilizes all resources on an actual computing environment, and the difficulties of performance evaluation of the parallel solvers. Third, we present a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions. Finally, we demonstrate the current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer nonlinear programs (MINLPs) in parallel.</abstract>
    <parentTitle language="eng">INFORMS Journal on Computing</parentTitle>
    <identifier type="doi">10.1287/ijoc.2017.0762</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-42595</enrichment>
    <author>Yuji Shinano</author>
    <submitter>Yuji Shinano</submitter>
    <author>Stefan Heinz</author>
    <author>Stefan Vigerske</author>
    <author>Michael Winkler</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</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>
  </doc>
  <doc>
    <id>5890</id>
    <completedYear/>
    <publishedYear>2016</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Open MIP Instances with ParaSCIP on Supercomputers using up to 80,000 Cores</title>
    <abstract language="eng">This paper describes how we solved 12 previously unsolved mixed-integer program- ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper we describe the basic parallelization mechanism of ParaSCIP, improvements of the dynamic load balancing and novel techniques to exploit the power of parallelization for MIP solving. We give a detailed overview of computing times and statistics for solving open MIPLIB instances.</abstract>
    <parentTitle language="eng">Proc. of 30th IEEE International Parallel &amp; Distributed Processing Symposium</parentTitle>
    <identifier type="doi">10.1109/IPDPS.2016.56</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-56404</enrichment>
    <author>Yuji Shinano</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Tobias Achterberg</author>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Michael Winkler</author>
    <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="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</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>
  </doc>
</export-example>
