<?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>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>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>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>
