An approximative Criterion for the Potential of Energetic Reasoning
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-12655
- 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.
Verfasserangaben: | Timo BertholdORCiD, Stefan Heinz, Jens Schulz |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | |
MSC-Klassifikation: | 65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming | |
Datum der Erstveröffentlichung: | 18.04.2011 |
Schriftenreihe (Bandnummer): | ZIB-Report (11-12) |
ZIB-Reportnummer: | 11-12 |
Verlagspublikation: | Appeared in: Theory and Practice of Algorithms in (Computer) Systems, Alberto Marchetti-Spaccamela and Michael Segal (eds.) Springer 2011, LNCS 6595, pp. 229-239 |