Explanations for the Cumulative Constraint: an Experimental Study
Please always quote using this URN: urn:nbn:de:0297-zib-12668
- 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.
Author: | Stefan Heinz, Jens Schulz |
---|---|
Document Type: | ZIB-Report |
Tag: | |
MSC-Classification: | 65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx] |
Date of first Publication: | 2011/04/18 |
Series (Serial Number): | ZIB-Report (11-13) |
ZIB-Reportnumber: | 11-13 |
Published in: | Experimental Algorithms, Panos M. Pardalos und Steffen Rebennack (eds.) Springer 2011, LNCS 6630, pp. 400-409 |