<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1767</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-01-17</completedDate>
    <publishedDate>2013-01-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Recent improvements using constraint integer programming for resource allocation and scheduling</title>
    <abstract language="eng">Recently, we compared the performance of mixed-integer programming (MIP), constraint programming (CP), and constraint integer programming (CIP) to a state-of-the-art logic-based Benders manual decomposition (LBBD) for a resource allocation/scheduling problem. For a simple linear relaxation, the LBBD and CIP models deliver comparable performance with MIP also performing well. &#13;
&#13;
Here we show that algorithmic developments in CIP plus the use of an existing tighter relaxation substantially improve one of the CIP approaches. Furthermore, the use of the same relaxation in LBBD and MIP models significantly improves their performance. While such a result is known for LBBD, to the best of our knowledge, the other results are novel. Our experiments show that both CIP and MIP approaches are competitive with LBBD in terms of the number of problems solved to proven optimality, though MIP is about three times slower on average. Further, unlike the LBBD and CIP approaches, the MIP model is able to obtain provably high-quality solutions for all problem instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-17676</identifier>
    <submitter>Stefan Heinz</submitter>
    <author>Stefan Heinz</author>
    <author>Wen-Yang Ku</author>
    <author>J. Christopher Beck</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-05</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cumulative constraint</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optional activities</value>
    </subject>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1767/ZR-13-05.pdf</file>
  </doc>
  <doc>
    <id>1269</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-04-19</completedDate>
    <publishedDate>2011-04-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Resource Allocation/Scheduling Problems with Constraint Integer Programming</title>
    <abstract language="eng">Constraint Integer Programming (CIP) is a generalization of mixed-integer programming (MIP) in the direction of constraint programming (CP) allowing the inference techniques that have traditionally been the core of \P to be integrated with the problem solving techniques that form the core of complete MIP solvers. In this paper, we investigate the application of CIP to scheduling problems that require resource and start-time assignments to satisfy resource capacities. The best current approach to such problems is logic-based Benders decomposition, a manual decomposition method.  We present a CIP model and demonstrate that it achieves performance competitive to the decomposition while out-performing the standard MIP and CP formulations.</abstract>
    <identifier type="serial">11-14</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-12691</identifier>
    <author>Stefan Heinz</author>
    <submitter>Stefan Heinz</submitter>
    <author>J. Christopher Beck</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-14</number>
    </series>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>cumulative constraint</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>optional resources</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1269/ZR-11-14.pdf</file>
  </doc>
  <doc>
    <id>1266</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-04-18</completedDate>
    <publishedDate>2011-04-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Explanations for the Cumulative Constraint: an Experimental Study</title>
    <abstract language="eng">In cumulative scheduling, conflict analysis seems to be one of the key ingredients to solve such problems efficiently. Thereby, the computational complexity of explanation algorithms plays an important role. Even more when we are faced with a backtracking system where explanations need to be constructed on the fly.&#13;
&#13;
In this paper we present extensive computational results to analyze the impact of explanation algorithms for the cumulative constraint in a backward checking system. The considered explanation algorithms differ in their quality and computational complexity. We present results for the domain propagation algorithms time-tabling, edge-finding, and energetic reasoning.</abstract>
    <identifier type="serial">11-13</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-12668</identifier>
    <enrichment key="SourceTitle">Experimental Algorithms, Panos M. Pardalos und Steffen Rebennack (eds.) Springer 2011, LNCS 6630, pp. 400-409</enrichment>
    <author>Stefan Heinz</author>
    <submitter>Stefan Heinz</submitter>
    <author>Jens Schulz</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-13</number>
    </series>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>conflict analysis</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>cumulative constraint</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>resource-constrained project scheduling</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>propagation algorithms</value>
    </subject>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1266/ZR-11-13.pdf</file>
  </doc>
  <doc>
    <id>1559</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>jpn</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-07-25</completedDate>
    <publishedDate>2012-07-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="jpn">SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法</title>
    <title language="eng">Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite</title>
    <abstract language="jpn">この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し，その３つの構成要素：モデリン&#13;
グ言語Zimpl, 線形計画（LP: linear programming) ソルバSoPlex, そして，制約整数計画(CIP: constraint&#13;
integer programming) に対するソフトウェア・フレームワークSCIP, について述べる．本論文では，この３つの&#13;
構成要素を利用して，どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization&#13;
problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化&#13;
し解くのかを説明する．SCIP は，現在，最も高速なMIP,MINLP ソルバの１つである．いくつかの例により，&#13;
Zimpl, SCIP, SoPlex の利用方法を示すとともに，利用可能なインタフェースの概要を示す．最後に，将来の開&#13;
発計画の概要について述べる．</abstract>
    <abstract language="eng">This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how in concert these can be used to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview over available interfaces, and outline plans for future development.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15598</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming. Masakazu Muramatsu (ed. ) 2012, pp. 165-192</enrichment>
    <author>Timo Berthold</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Ambros Gleixner</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Yuji Shinano</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-24</number>
    </series>
    <subject>
      <language>mul</language>
      <type>uncontrolled</type>
      <value>SCIP, MIP, MINLP, CIP, LP, modeling, optimization</value>
    </subject>
    <collection role="msc" number="90C05">Linear programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1559/ZR-12-24.pdf</file>
  </doc>
  <doc>
    <id>1083</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-14</completedDate>
    <publishedDate>2008-08-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Using Model Counting to Find Optimal Distinguishing Tests</title>
    <abstract language="eng">Testing is the process of stimulating a system with inputs in order to reveal hidden parts of the system state. In the case of non-deterministic systems, the difficulty arises that an input pattern can generate several possible outcomes. Some of these outcomes allow to distinguish between different hypotheses about the system state, while others do~not. In this paper, we present a novel approach to find, for non-deterministic systems modeled as constraints over variables, tests that allow to distinguish among the hypotheses as good as possible. The idea is to assess the quality of a test by determining the ratio of distinguishing (good) and not distinguishing (bad) outcomes. This measure refines previous notions proposed in the literature on model-based testing and can be computed using model counting techniques. We propose and analyze a greedy-type algorithm to solve this test optimization problem, using existing model counters as a building block. We give preliminary experimental results of our method, and discuss possible improvements.</abstract>
    <identifier type="serial">08-32</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1118</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10832</identifier>
    <enrichment key="SourceTitle">Appeared in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems : 6th International Conference, CPAIOR 2009, Lecture Notes in Computer Science 5547, pp. 117-131, 2009</enrichment>
    <author>Stefan Heinz</author>
    <submitter>unknown unknown</submitter>
    <author>Martin Sachenbacher</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-32</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>zählen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>automatische Test Generierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>counting</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>automated test generation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1083/ZR_08_32.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1083/ZR_08_32.ps</file>
  </doc>
  <doc>
    <id>1067</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-03-03</completedDate>
    <publishedDate>2008-03-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Pseudo-Boolean Problems with SCIP</title>
    <abstract language="eng">Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field. In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.</abstract>
    <identifier type="serial">08-12</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1095</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10671</identifier>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-12</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Pseudo-Boolean</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Branch-And-Cut</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierungssoftware</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Pseudo-Boolean</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization software</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.orig.Vers.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1067/ZR_08_12.orig.Vers.ps</file>
  </doc>
  <doc>
    <id>1063</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-02-26</completedDate>
    <publishedDate>2008-02-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Counting solutions of integer programs using unrestricted subtree detection</title>
    <abstract language="eng">In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection.</abstract>
    <identifier type="serial">08-09</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1092</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10632</identifier>
    <enrichment key="SourceTitle">App. in: Integration of AI and OR techniques in constraint programming for combinatorial optimization problems : 5th International Conference, CPAIOR 2008 Paris, France, 2008; proc.,  Laurent Perron ... (eds.), LNC 5015, Springer 2008, pp. 278-282</enrichment>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-09</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Zählen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>ganzzahlige Programme</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>IP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>counting</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>IP</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</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/1063/ZR_08_09.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1063/ZR_08_09.ps</file>
  </doc>
  <doc>
    <id>965</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-08-13</completedDate>
    <publishedDate>2007-08-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online Multicommodity Routing with Time Windows</title>
    <abstract language="eng">We consider a multicommodity routing problem, where demands are released \emph{online} and have to be routed in a network during specified time windows. The objective is to minimize a time and load dependent convex cost function of the aggregate arc flow. First, we study the fractional routing variant. We present two online algorithms, called Seq and Seq$^2$. Our first main result states that, for cost functions defined by polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of Seq and Seq$^2$ is at most $(d+1)^{d+1}$, which is tight. We also present lower bounds of $(0.265\,(d+1))^{d+1}$ for any online algorithm. In the case of a network with two nodes and parallel arcs, we prove a lower bound of $(2-\frac{1}{2} \sqrt{3})$ on the competitive ratio for Seq and Seq$^2$, even for affine linear price functions. Furthermore, we study resource augmentation, where the online algorithm has to route less demand than the offline adversary. Second, we consider unsplittable routings. For this setting, we present two online algorithms, called U-Seq and U-Seq$^2$. We prove that for polynomial price functions with nonnegative coefficients and maximum degree~$d$, the competitive ratio of U-Seq and U-Seq$^2$ is bounded by $O{1.77^d\,d^{d+1}}$. We present lower bounds of $(0.5307\,(d+1))^{d+1}$ for any online algorithm and $(d+1)^{d+1}$ for our algorithms. Third, we consider a special case of our framework: online load balancing in the $\ell_p$-norm. For the fractional and unsplittable variant of this problem, we show that our online algorithms are $p$ and $O{p}$ competitive, respectively. Such results where previously known only for scheduling jobs on restricted (un)related parallel machines.</abstract>
    <identifier type="serial">07-22</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">976</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9654</identifier>
    <author>Tobias Harks</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Marc Pfetsch</author>
    <author>Tjark Vredeveld</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-22</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Telecommunications</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68W40">Analysis of algorithms [See also 68Q25]</collection>
    <collection role="msc" number="90C25">Convex programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/965/ZR_07_22.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/965/ZR_07_22.ps</file>
  </doc>
  <doc>
    <id>1295</id>
    <completedYear>2010</completedYear>
    <publishedYear>2010</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">MIPLIB 2010</title>
    <abstract language="eng">This paper reports on the fifth version of the Mixed Integer Programming Library.  &#13;
The MIPLIB 2010 is the first MIPLIB release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups.&#13;
This includes the main benchmark test set of 87 instances, which&#13;
are all solvable by today's codes, and also the challenge test set with 164 instances, many of which are currently unsolved.&#13;
For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to&#13;
test the accuracy of provided solutions using exact arithmetic.</abstract>
    <identifier type="serial">10-31</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-12953</identifier>
    <identifier type="doi">10.1007/s12532-011-0025-9</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Programming Computation vol. 3 iss. 2 (2011), pp. 103-163</enrichment>
    <author>Thorsten Koch</author>
    <submitter>Timo Berthold</submitter>
    <author>Tobias Achterberg</author>
    <author>Erling Andersen</author>
    <author>Oliver Bastert</author>
    <author>Timo Berthold</author>
    <author>Robert E. Bixby</author>
    <author>Emilie Danna</author>
    <author>Gerald Gamrath</author>
    <author>Ambros Gleixner</author>
    <author>Stefan Heinz</author>
    <author>Andrea Lodi</author>
    <author>Hans Mittelmann</author>
    <author>Ted Ralphs</author>
    <author>Domenico Salvagnin</author>
    <author>Daniel Steffy</author>
    <author>Kati Wolter</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-31</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Problem Instances</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>IP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIPLIB</value>
    </subject>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="SPP1307-ExactIP">SPP1307-ExactIP</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1295/miplib5.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1295/miplib5.ps</file>
  </doc>
  <doc>
    <id>1298</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-05-31</completedDate>
    <publishedDate>2011-05-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Large Neighborhood Search beyond MIP</title>
    <abstract language="eng">Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation.&#13;
&#13;
In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics.</abstract>
    <identifier type="serial">11-21</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-12989</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 9th Metaheuristics International Conference (MIC 2011).  2011. Luca di Gaspar et al. eds. ISBN 978-88-900984-3-7, pp. 51-60</enrichment>
    <author>Timo Berthold</author>
    <submitter>Timo Berthold</submitter>
    <author>Stefan Heinz</author>
    <author>Marc Pfetsch</author>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-21</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Large Neighborhood Search</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Primal Heuristic</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>MIQCP</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Pseudo-Boolean</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1298/lns4cip.pdf</file>
  </doc>
  <doc>
    <id>1265</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-04-18</completedDate>
    <publishedDate>2011-04-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An approximative Criterion for the Potential of Energetic Reasoning</title>
    <abstract language="eng">Energetic reasoning is one of the most powerful propagation algorithms in cumulative scheduling. In practice, however, it is not commonly used because it has a high running time and its success highly depends on the  tightness of the variable bounds. In order to speed up energetic reasoning, we provide an easy-to-check necessary condition for energetic reasoning to  detect infeasibilities.&#13;
&#13;
We present an implementation of energetic reasoning that employs this condition and that can be parametrically adjusted to handle the trade-off between solving time and propagation overhead. Computational results on instances from the PSPLIB are provided. These results show that using this condition decreases the running time by more than a half, although more search nodes need to be explored.</abstract>
    <identifier type="serial">11-12</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-12655</identifier>
    <enrichment key="SourceTitle">Appeared in: Theory and Practice of Algorithms in (Computer) Systems, Alberto Marchetti-Spaccamela and Michael Segal (eds.) Springer 2011, LNCS 6595, pp. 229-239</enrichment>
    <author>Timo Berthold</author>
    <submitter>Stefan Heinz</submitter>
    <author>Stefan Heinz</author>
    <author>Jens Schulz</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-12</number>
    </series>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>conflict analysis</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>cumulative constraint</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>resource-constrained project scheduling</value>
    </subject>
    <subject>
      <language/>
      <type>uncontrolled</type>
      <value>energetic reasoning</value>
    </subject>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1265/ZR-11-12.pdf</file>
  </doc>
  <doc>
    <id>1632</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-10-30</completedDate>
    <publishedDate>2012-10-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Using dual presolving reductions to reformulate cumulative constraints</title>
    <abstract language="eng">Dual presolving reductions are a class of reformulation techniques that remove feasible or even optimal solutions while guaranteeing that at least one optimal solution remains, as long as the original problem was feasible. Presolving and dual reductions are important components of state-of-the-art mixed-integer linear programming solvers. In this paper, we introduce them both as unified, practical concepts in constraint programming solvers. Building on the existing idea of variable locks, we formally define and justify the use of dual information for cumulative constraints during a presolving phase of a solver. In particular, variable locks are used to decompose cumulative constraints, detect irrelevant variables, and infer variable assignments and domain reductions.  Since the computational complexity of propagation algorithms typically depends on the number of variables and/or domain size, such dual reductions are a source of potential computational speed-up. Through experimental evidence on resource constrained project scheduling problems, we demonstrate that the conditions for dual reductions are present in well-known benchmark instances and that a substantial proportion of them can be solved to optimality in presolving -- without search. While we  consider this result very promising, we do not observe significant change in overall run-time from the use of our novel dual reductions.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-16321</identifier>
    <author>Stefan Heinz</author>
    <submitter>Stefan Heinz</submitter>
    <author>Jens Schulz</author>
    <author>J. Christopher Beck</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-37</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>dual reductions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cumulative constraints</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>presolving</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>variable locks</value>
    </subject>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C99">None of the above, but in this section</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1632/ZR-12-37.pdf</file>
  </doc>
  <doc>
    <id>1565</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-07-31</completedDate>
    <publishedDate>2012-07-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving mixed integer linear and nonlinear problems using the SCIP Optimization Suite</title>
    <abstract language="eng">This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how these can be used in concert to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview of available interfaces, and outline plans for future development.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15654</identifier>
    <author>Timo Berthold</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Gerald Gamrath</author>
    <author>Ambros Gleixner</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Yuji Shinano</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-27</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>LP, MIP, CIP, MINLP, modeling, optimization, SCIP, SoPlex, Zimpl</value>
    </subject>
    <collection role="msc" number="90C05">Linear programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="persons" number="shinano">Shinano, Yuji</collection>
    <collection role="projects" number="MATHEON-B20">MATHEON-B20</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1565/ZR-12-27.pdf</file>
  </doc>
  <doc>
    <id>1118</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>TU Berlin</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-03-15</completedDate>
    <publishedDate>2010-03-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling</title>
    <abstract language="eng">We propose a hybrid approach for solving the resource-constrained project scheduling problem which is an extremely hard to solve combinatorial optimization problem of practical relevance. Jobs have to be scheduled on (renewable) resources subject to precedence constraints such that the resource capacities are never exceeded and the latest completion time of all jobs is minimized. The problem has challenged researchers from different communities, such as integer programming (IP), constraint programming (CP), and satisfiability testing (SAT). Still, there are instances with 60 jobs which have not been solved for many years. The currently best known approach, lazyFD, is a hybrid between CP and SAT techniques. In this paper we propose an even stronger hybridization by integrating all the three areas, IP, CP, and SAT, into a single branch-and-bound scheme. We show that lower bounds from the linear relaxation of the IP formulation and conflict analysis are key ingredients for pruning the search tree. First computational experiments show very promising results. For five instances of the well-known PSPLIB we report an improvement of lower bounds. Our implementation is generic, thus it can be potentially applied to similar problems as well.</abstract>
    <identifier type="serial">10-03</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1226</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11180</identifier>
    <enrichment key="SourceTitle">App. in: CPAIOR 2010, Proceedings, Andrea Lodi et al. (eds.) Springer 2010, LNCS 6140, pp. 313-317</enrichment>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Marco Lübbecke</author>
    <author>Rolf Möhring</author>
    <author>Jens Schulz</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-03</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cumulative constraint</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>conflict analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>resource-constrained project Scheduling</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="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1118/ZR_10_03.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1118/ZR_10_03.ps</file>
  </doc>
  <doc>
    <id>1137</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-07-09</completedDate>
    <publishedDate>2009-07-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Extending a CIP framework to solve MIQCPs</title>
    <abstract language="eng">This paper discusses how to build a solver for mixed integer quadratically constrained programs (MIQCPs) by extending a framework for constraint integer programming (CIP). The advantage of this approach is that we can utilize the full power of advanced MIP and CP technologies. In particular, this addresses the linear relaxation and the discrete components of the problem. For relaxation, we use an outer approximation generated by linearization of convex constraints and linear underestimation of nonconvex constraints. Further, we give an overview of the reformulation, separation, and propagation techniques that are used to handle the quadratic constraints efficiently. We implemented these methods in the branch-cut-and-price framework SCIP. Computational experiments indicates the potential of the approach.</abstract>
    <identifier type="serial">09-23</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1186</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11371</identifier>
    <enrichment key="SourceTitle">App. in: Mixed Integer Nonlinear Programming. Jon Lee, Sven Leyffer (eds.) The IMA Volumes in Mathematics and its Applications, 154. Springer 2011, pp. 427-444</enrichment>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Stefan Vigerske</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-23</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer quadratically constrained programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>convex relaxation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>nonconvex</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C20">Quadratic programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="vigerske">Vigerske, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23rev.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23rev.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1137/ZR_09_23.ps</file>
  </doc>
  <doc>
    <id>1123</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-03-29</completedDate>
    <publishedDate>2009-03-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Nonlinear pseudo-Boolean optimization: relaxation or propagation?</title>
    <abstract language="eng">Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver.</abstract>
    <identifier type="serial">09-11</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1172</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11232</identifier>
    <enrichment key="SourceTitle">Appeared in: O. Kullmann (Ed.), Theory and Applications of Satisfiability Testing -- SAT 2009; Lecture Notes in Computer Science 5584, pp. 441-446, 2009</enrichment>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <author>Stefan Heinz</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-11</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Pseudo-Boolean</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>linear relaxation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>separation algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>domain propagation</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="90C09">Boolean programming</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C30">Nonlinear programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1123/ZR_09_11.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1123/ZR_09_11.ps</file>
  </doc>
  <doc>
    <id>1126</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-04-29</completedDate>
    <publishedDate>2009-04-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Steel Mill Slab Problems with Branch and Price</title>
    <abstract language="eng">The steel mill slab design problem from the CSPLib is a binpacking problem that is motivated by an application of the steel industry and that has been widely studied in the constraint programming community. Recently, several people proposed new models and methods to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called multiple knapsack problem with color constraints, originated from the same industrial problem, were discussed in the integer programming community. In particular, a simple integer programming for this problem has been given by Forrest et al. [3]. The aim of this paper is to bring these different studies together. Moreover, we adopt the model of [3] for the steel mill slab problem. Using a state of the art integer program solver, this model is capable to solve all instances of the steel mill slab library, mostly in less than one second, to optimality. We improved, thereby, the solution value of 76 instances.</abstract>
    <identifier type="serial">09-14</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1175</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11260</identifier>
    <author>Stefan Heinz</author>
    <submitter>unknown unknown</submitter>
    <author>Rüdiger Stephan</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-14</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>steel mill slab problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-price</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C10">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="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1126/ZR_09_14.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1126/ZR_09_14.ps</file>
  </doc>
  <doc>
    <id>1095</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-10-31</completedDate>
    <publishedDate>2008-10-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming: Techniques and Applications</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 for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three 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 demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear 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 nonlinear constraints by employing constraint programming techniques.</abstract>
    <identifier type="serial">08-43</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1132</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10950</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Kati Wolter</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-43</number>
    </series>
    <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="000">Informatik, Informationswissenschaft, allgemeine Werke</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="projects" number="MATHEON-B12:IPSym">MATHEON-B12:IPSym</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1095/ZR_08_43.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1095/ZR_08_43.ps</file>
  </doc>
  <doc>
    <id>5551</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2015-07-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Structure-based primal heuristics for mixed integer programming</title>
    <abstract language="eng">Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-55518</identifier>
    <identifier type="doi">http://dx.doi.org/10.1007/978-4-431-55420-2_3</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-55518</enrichment>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-26</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming, large neighborhood search, primal heuristics, domain propagation</value>
    </subject>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="michael.winkler">Winkler, Michael</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5551/ZR-15-26.pdf</file>
  </doc>
  <doc>
    <id>6538</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-10-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Structure-driven fix-and-propagate heuristics for mixed integer programming</title>
    <abstract language="eng">Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-65387</identifier>
    <identifier type="doi">10.1007/s12532-019-00159-1</identifier>
    <author>Gerald Gamrath</author>
    <submitter>Gerald Gamrath</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Michael Winkler</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-56</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>primal heuristics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>fix-and-propagate</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>large neighborhood search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>domain propagation</value>
    </subject>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="mip">Mathematical Optimization Methods</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="gamrath">Gamrath, Gerald</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="michael.winkler">Winkler, Michael</collection>
    <collection role="projects" number="ASTfSCM">ASTfSCM</collection>
    <collection role="projects" number="MIP-ZIBOPT">MIP-ZIBOPT</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="Siemens">Siemens</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6538/ZR-17-56.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/6538/ZR-17-56-revised.pdf</file>
  </doc>
  <doc>
    <id>1466</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-02-11</completedDate>
    <publishedDate>2012-02-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling</title>
    <abstract language="eng">Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP)  technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade.&#13;
We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models,&#13;
  which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP&#13;
are technologies that should be considered along with CP for solving scheduling problems.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">12-05</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14660</identifier>
    <enrichment key="SourceTitle">App. in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012), Springer 2012. Lecture Notes in Computer Science, 7298, pp. 211-227</enrichment>
    <author>Stefan Heinz</author>
    <submitter>Stefan Heinz</submitter>
    <author>J. Christopher Beck</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-05</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cumulative constraint</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optional activities</value>
    </subject>
    <collection role="msc" number="60-XX">PROBABILITY THEORY AND STOCHASTIC PROCESSES (For additional applications, see 11Kxx, 62-XX, 90-XX, 91-XX, 92-XX, 93-XX, 94-XX)</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1466/ZR-12-05.pdf</file>
  </doc>
</export-example>
