An approximative Criterion for the Potential of Energetic Reasoning
Please always quote using this URN:urn:nbn:de:0296-matheon-9765
- 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.
| Author: | Timo Berthold, Stefan Heinz, Jens Schulz |
|---|---|
| URN: | urn:nbn:de:0296-matheon-9765 |
| Referee: | Martin Grötschel |
| Document Type: | Preprint, Research Center Matheon |
| Language: | English |
| Date of first Publication: | 2012/01/15 |
| Release Date: | 2012/01/15 |
| Tag: | conflict analysis; constraint integer programming; cumulative constraint; energetic reasoning; resource-constrained project scheduling |
| Institute: | Technische Universität Berlin |
| Zuse Institute Berlin (ZIB) | |
| MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming |
| Preprint Number: | 857 |
