Name
Abstract | ||
|---|---|---|
This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum y = Σxi, and where variables xi are subject to difference constraints of the form xj - xi ≤ c. An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria. Classical approaches perform a local consistency filtering after each reduction of the bound of y. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global constraint that enables to tackle simultaneously the whole constraint system, and thus, yields a more effective pruning of the domains of the xi when the bounds of y are reduced. An efficient algorithm, derived from Dikjstra's shortest path algorithm, is introduced to achieve interval consistency on this global constraint. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/3-540-45349-0_28 | CP |
Keywords | Field | DocType |
global constraint,shortest path algorithm,whole constraint system,difference constraint,difference constraints,sum constraint,local consistency,interval consistency,sum y,efficient algorithm,deterministic scheduling,classical approach | Local consistency,Mathematical optimization,Scheduling (computing),Constraint (mathematics),Computer science,Algorithm,Combinatorial optimization,Constraint logic programming,Dijkstra's algorithm,Binary constraint,Constrained optimization | Conference |
ISBN | Citations | PageRank |
3-540-41053-8 | 13 | 0.97 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-charles Régin | 1 | 1312 | 96.59 |
| Michel Rueher | 2 | 613 | 59.81 |