Propagators for Constraint Programming Energetic Reasoning
Exploring the Effect of Explanations for Energetic Reasoning
K. Kamenov (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Emir Demirović – Mentor (TU Delft - Algorithmics)
I.C.W.M. Marijnissen – Mentor (TU Delft - Algorithmics)
Stephanie Wehner – Graduation committee member (TU Delft - QID/Wehner Group)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The cumulative constraint is often used when modeling constraint programming problems, frequently seen in scheduling and planning problems. Energetic reasoning is one of the propagators used to enforce this constraint. However, not much has been done to explore strategies for generating explanations, which are then used by the solver for conflict analysis. This paper addresses this gap by applying strategies used in time-table edge-finding to the energetic reasoning propagator. The strategies are initial bounds relaxations and reducing the overload. Furthermore the paper compares two old strategies (naive and greedy task removal) for reducing the overload and proposes two new ones: greedy task shift and a probabilistic heuristic utilizing the knapsack problem. Results on the MiniZinc RCPSP benchmarks show that the initial bounds adjustments provide great benefit, reducing the number of conflicts by at least twenty-five percent. Reducing the overload provided a small improvement (less than five percent) and results suggest there is not much of a difference between the different strategies.