Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Case Study
Constraint Programming
cumulant
Global Constraint
Scheduling Problem
Subscribe
Academic
Publications
Global propagation of side constraints for solving overconstrained problems
Global propagation of side constraints for solving overconstrained problems,10.1007/s1047901006834,Annals of Operations Research,Thierry Petit,Emm
Edit
Global propagation of side constraints for solving overconstrained problems
(
Citations: 2
)
BibTex

RIS

RefWorks
Download
Thierry Petit
,
Emmanuel Poder
This article deals with the resolution of overconstrained 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 casestudy is a cumulative
scheduling problem
with overloads. The objective is to minimize the total amount of overloads. We augment the Cumulative
global constraint
of the
constraint programming
solver Choco with sweep and task interval violationbased algorithms. We provide a theoretical and experimental comparison of the two main approaches for encoding overconstrained problems with side constraints.
Journal:
Annals of Operations Research  Annals OR
, vol. 184, no. 1, pp. 295314, 2011
DOI:
10.1007/s1047901006834
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.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
www.emn.fr
)
(
dx.doi.org
)
More »
Citation Context
(2)
...– The fact that some subobjective variables may be involved in several constraints (different from the objective constraint) is ignored while it is important [3,
4
]...
JeanCharles Régin
,
et 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 overloads: 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 Javabased constraint programming engine CHOCO 3 ...
Thierry Petit
,
et al.
The Ordered Distribute Constraint
References
(31)
A New Multiresource cumulatives Constraint with Negative Heights
(
Citations: 18
)
Nicolas Beldiceanu
,
Mats Carlsson
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 6379, 2002
SemiringBased CSPs and Valued CSPs: Frameworks, Properties, and Comparison
(
Citations: 137
)
Stefano Bistarelli
,
Hélène Fargier
,
Ugo Montanari
,
Francesca Rossi
,
Thomas Schiex
,
Gérard Verfaillie
Published in 1996.
Satisfiability Tests and TimeBound Adjustments for Cumulative Scheduling Problems
(
Citations: 40
)
PHILIPPE BAPTISTE
,
WIM NUIJTEN
Journal:
Annals of Operations Research  Annals OR
, 1997
Partial Constraint Satisfaction
(
Citations: 262
)
Eugene C. Freuder
,
Richard J. Wallace
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 63110, 1995
Global Constraints for Partial CSPs: A CaseStudy of Resource and Due Date Constraints
(
Citations: 24
)
Philippe Baptiste
,
Claude Le Pape
,
Laurent Péridy
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 87101, 1998
Sort by:
Citations
(2)
The Objective Sum Constraint
JeanCharles Régin
,
Thierry Petit
Conference:
International Conference on Integration of AI and OR Techniques in Constraint Programming  CPAIOR
, pp. 190195, 2011
The Ordered Distribute Constraint
Thierry Petit
,
JeanCharles Régin
Conference:
International Conference on Tools with Artificial Intelligence  ICTAI
, vol. 1, pp. 431438, 2010