TY - GEN
T1 - Generalizing global constraints based on network flows
AU - Razgon, Igor
AU - O'Sullivan, Barry
AU - Provan, Gregory
PY - 2008
Y1 - 2008
N2 - Global constraints are used in constraint programming to help users specify patterns that occur frequently in the real world. In addition, global constraints facilitate the use of efficient constraint propagation algorithms for problem solving. Many of the most common global constraints used in constraint programming use filtering algorithms based on network flow theory. We show how we can formulate global constraints such as GCC, Among, and their combinations, in terms of a tractable set-intersection problem called Two Families Of Sets (TFOS). We demonstrate that the TFOS problem allows us to represent tasks that are often difficult to model in terms of a classical constraint satisfaction paradigm. In the final part of the paper we specify some tractable and intractable extensions of the TFOS problem. The contribution of this paper is the characterisation of a general framework that helps us to study the tractability of global constraints that rely on filtering algorithms based on network flow theory.
AB - Global constraints are used in constraint programming to help users specify patterns that occur frequently in the real world. In addition, global constraints facilitate the use of efficient constraint propagation algorithms for problem solving. Many of the most common global constraints used in constraint programming use filtering algorithms based on network flow theory. We show how we can formulate global constraints such as GCC, Among, and their combinations, in terms of a tractable set-intersection problem called Two Families Of Sets (TFOS). We demonstrate that the TFOS problem allows us to represent tasks that are often difficult to model in terms of a classical constraint satisfaction paradigm. In the final part of the paper we specify some tractable and intractable extensions of the TFOS problem. The contribution of this paper is the characterisation of a general framework that helps us to study the tractability of global constraints that rely on filtering algorithms based on network flow theory.
UR - https://www.scopus.com/pages/publications/70349871531
U2 - 10.1007/978-3-540-89812-2_9
DO - 10.1007/978-3-540-89812-2_9
M3 - Conference proceeding
AN - SCOPUS:70349871531
SN - 3540898115
SN - 9783540898115
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 127
EP - 141
BT - Recent Advances in Constraints - 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007, Revised Selected Papers
PB - Springer Verlag
T2 - 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007
Y2 - 7 June 2007 through 8 June 2007
ER -