Global propagation of side constraints for solving over-constrained problems

Global propagation of side constraints for solving over-constrained problems,10.1007/s10479-010-0683-4,Annals of Operations Research,Thierry Petit,Emm

Global propagation of side constraints for solving over-constrained problems   (Citations: 2)
BibTex | RIS | RefWorks Download
This article deals with the resolution of over-constrained problems us- ing constraint programming, which often imposes to add to the constraint network new side constraints. These side constraints control how the ini- tial constraints of the model should be satised or violated, to obtain solutions that have a practical interest. They are specic to each ap- plication. In our experiments, we show the superiority of a framework where side constraints are encoded by global constraints on new domain variables, which are directly included into the model. The case-study is a cumulative scheduling problem with over-loads. The objective is to minimize the total amount of over-loads. We augment the Cumulative global constraint of the constraint programming solver Choco with sweep and task interval violation-based algorithms. We provide a theoretical and experimental comparison of the two main approaches for encoding over-constrained problems with side constraints.
Journal: Annals of Operations Research - Annals OR , vol. 184, no. 1, pp. 295-314, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...– The fact that some sub-objective variables may be involved in several constraints (different from the objective constraint) is ignored while it is important [3,4]...

    Jean-Charles Réginet al. The Objective Sum Constraint

    • ...Fig. 1. Example of SOFTCUMULATIVESUM with a ground schedule with 3 fixed activities: a1 starts at 0 and ends at 3, and res[a1 ]=2 . a2 starts at 2 and ends at 7, and res[a2 ]=2 . a3 starts at 5 and ends at 8, and res[a3 ]=3 . There is 3 over-loads: cost [2] =1 , cost [5] =2 , cost [6] =2 ...
    • ...In [5], authors introduced a relaxed version of CUMULATIVE devoted to this class of problems...
    • ...1 In [5], each variable cost[t] can correspond to an interval of consecutive points in time, not only one point in time...
    • ...We experimented our global constraint on instances of the problem described in Example 1, which is derived from [5], using the Java-based constraint programming engine CHOCO 3 ...

    Thierry Petitet al. The Ordered Distribute Constraint

Sort by: