TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Lübbecke, Marco A1 - Möhring, Rolf A1 - Schulz, Jens T1 - A Constraint Integer Programming Approach for Resource-Constrained Project Scheduling N2 - 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. T3 - ZIB-Report - 10-03 KW - constraint integer programming KW - cumulative constraint KW - scheduling KW - conflict analysis KW - resource-constrained project Scheduling Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11180 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Schulz, Jens T1 - An approximative Criterion for the Potential of Energetic Reasoning N2 - 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. 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. T3 - ZIB-Report - 11-12 KW - conflict analysis KW - constraint integer programming KW - cumulative constraint KW - resource-constrained project scheduling KW - energetic reasoning Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12655 ER - TY - GEN A1 - Heinz, Stefan A1 - Schulz, Jens T1 - Explanations for the Cumulative Constraint: an Experimental Study N2 - 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. 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. T3 - ZIB-Report - 11-13 KW - conflict analysis KW - constraint integer programming KW - cumulative constraint KW - resource-constrained project scheduling KW - propagation algorithms Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12668 ER -