Flow-Based Propagators for the SEQUENCE and Related Global Constraints (2009)
Maher, Michael J., Narodytska, Nina, Quimper, Claude-Guy, Walsh, Toby
We propose new filtering algorithms for the SEQUENCE constraint and some extensions of the SEQUENCE constraint based on network flows. We enforce domain consistency on the SEQUENCE constraint in...
Decomposition of the NVALUE constraint (2009)
Bessiere, Christian, Katsirelos, George, Narodytska, Nina, Quimper, Claude-Guy, Walsh, Toby
We study decompositions of NVALUE, a global constraint that can be used to model a wide range of problems where values need to be counted. Whilst decomposition typically hinders propagation, we...
Decompositions of All Different, Global Cardinality and Related Constraints (2009)
Bessiere, Christian, Katsirelos, George, Narodytska, Nina, Quimper, Claude-Guy, Walsh, Toby
We show that some common and important global constraints like ALL-DIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some...
Decompositions of Grammar Constraints (2009)
Quimper, Claude-Guy, Walsh, Toby
A wide range of constraints can be compactly specified using automata or formal languages. In a sequence of recent papers, we have shown that an effective means to reason with such specifications is...
Bandwidth Reduction for Video-on-Demand Broadcasting Using Secondary Content Insertion (2008)
Er Golynski Alej, Guillaume Poirier, Claude-guy Quimper
Abstract An optimal broadcasting scheme under the presence of secondary content is proposed. The scheme proposed works both for movies encoded in a Constant Bit Rate (CBR) or a Variable Bit Rate...
Decomposing Global Grammar Constraints (2008)
Claude-guy Quimper, Toby Walsh, Omega Omptimization
Abstract. A wide range of constraints can be specified using automata or formal languages. The GRAMMAR constraint restricts the values taken by a sequence of variables to be a string from a given...
Decomposing Global Grammar Constraints (2008)
Claude-guy Quimper, Toby Walsh, Toby Walsh
Abstract. A wide range of constraints can be specified using automata or formal languages. The GRAMMAR constraint restricts the values taken by a sequence of variables to be a string from a given...
Optimal Dynamic Video-On-Demand using Adaptive Broadcasting (2008)
Therese Biedl, Erik D. Demaine, Er Golynski, Joseph D. Horton, Ro López-ortiz, Guillaume Poirier, ...
Abstract. We consider the transmission of a movie over a broadcast network to support several viewers who start watching at arbitrary times, after a wait of at most twait minutes. A recent approach...
Reformulating global constraints: the Slide and Regular constraints (2008)
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Claude-guy Quimper, Toby Walsh, ...
Abstract. Global constraints are useful for modelling and reasoning about real-world combinatorial problems. Unfortunately, developing propagation algorithms to reason about global constraints...
Timothy M. Chan, Alexander Golynski, Alejandro López-ortiz, Claude-guy Quimper
We consider two variants of the well-known “sailor in the fog ” puzzle. The first version (the “asteroid surveying” problem) is set in three dimensions and asks for the shortest curve that...
Efficient Propagators for Global Constraints (2008)
I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners. I understand that my thesis may be...
Claude-guy Quimper, John Tromp, Peter Van Beek
In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint...
An Ecient Bounds Consistency Algorithm for the Global Cardinality Constraint (2007)
Claude-guy Quimper, Peter Van Beek, Er Golynski, Sayyed Bashir Sadjad
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can signicantly improve the eciency of a constraint programming approach. In this paper we present...
Expressions Itérées en Programmation par Contraintes (2007)
Bordeaux, Lucas, Hamadi, Youssef, Quimper, Claude-Guy, Samulowitz, Horst
Pour exprimer certains problèmes avancés d'optimisation et de décision, il est u tile d'imposer des contraintes sur des expressions complexes mettant en oeuvre des opérations imbriquées comme...
Expressions Itérées en Programmation par Contraintes (2007)
Bordeaux, Lucas, Hamadi, Youssef, Quimper, Claude-Guy, Samulowitz, Horst
Pour exprimer certains problèmes avancés d'optimisation et de décision, il est u tile d'imposer des contraintes sur des expressions complexes mettant en oeuvre des opérations imbriquées comme...
Encodings of the SEQUENCE constraint (2007)
Sebastian Brand, Nina Narodytska, Claude-Guy Quimper, Peter Stuckey, Toby Walsh
The SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not...
Encodings of the SEQUENCE constraint (2007)
Sebastian Brand, Nina Narodytska, Claude-Guy Quimper, Peter Stuckey, Toby Walsh
The SEQUENCE constraint is useful in modelling car sequencing, rostering, scheduling and related problems. We introduce half a dozen new encodings of the SEQUENCE constraint, some of which do not...
Efficient Propagators for Global Constraints (2006)
We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The global cardinality constraint (GCC)...
Efficient Propagators for Global Constraints (2006)
We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The <em>global cardinality...
Efficient Propagators for Global Constraints (2006)
We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The global cardinality constraint (GCC)...
T.: Global grammar constraints (2006)
Claude-guy Quimper, Toby Walsh
Global constraints are an important tool in the constraint toolkit. Unfortunately, whilst it is usually easy to specify when a global constraint holds, it is often difficult to build a good...
T.: Global grammar constraints (2006)
Claude-guy Quimper, Toby Walsh
Abstract. We consider global constraints over a sequence of variables which restrict the values assigned to be a string within a given language defined by a grammar or automaton. Such constraints are...
A Quadratic Propagator for the Inter-Distance Constraint (2006)
We present a new propagator achieving bound consistency for the INTER-DISTANCE constraint. This constraint ensures that, among a set of variables X1,..., Xn, the difference between two variables is...
Efficient Propagators for Global Constraints (2006)
We study in this thesis three well known global constraints. The All-Different constraint restricts a set of variables to be assigned to distinct values. The global cardinality constraint (GCC)...
The all different and global cardinality constraints on set, multiset and tuple variables (2005)
Claude-guy Quimper, Toby Walsh
Abstract. We describe how the propagator for the All-Different constraint can be generalized to prune variables whose domains are not just simple finite domains. We show, for example, how it can be...
The all different and global cardinality constraints on set, multiset and tuple variables (2005)
Claude-guy Quimper, Toby Walsh
Abstract. We describe how the propagator for the All-Different constraint can be generalized to prune variables whose domains are not just simple finite domains. We show, for example, how it can be...
Beyond finite domains: The All Different and Global Cardinality constraints (2005)
Claude-guy Quimper, Toby Walsh
Abstract. We describe how the propagator for the All-Different constraint can be generalized to prune variables whose domains are not just simple finite integer domains. We show, for example, how it...
Improved algorithms for the global cardinality constraint (2004)
Claude-guy Quimper, Peter Van Beek, Alexander Golynski
Abstract. We study the global cardinality constraint (gcc) and propose an O(n
Improved algorithms for the global cardinality constraint (2004)
Claude-guy Quimper, Ro López-ortiz, Peter Van Beek, Alexander Golynski
Abstract. We study the global cardinality constraint (gcc) and propose an O(n 1.5 d) algorithm for domain consistency and an O(cn + dn) algorithm for range consistency, where n is the number of...
A fast and simple algorithm for bounds consistency of the alldifferent constraint (2003)
Ro López-ortiz, Claude-guy Quimper, John Tromp, Peter Van Beek
In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint...
An efficient bounds consistency algorithm for the global cardinality constraint (2003)
Claude-guy Quimper, Peter Van Beek, Ro Lopez-ortiz, Er Golynski, Sayyed Bashir Sadjad
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the e#ciency of a constraint programming approach. In this paper we...
The Asteroid Surveying Problem and Other Puzzles (2003)
Timothy M. Chan, Alexander Golynski, Alejandro Lopez-Ortiz, Claude-Guy Quimper
We consider two variants of the well-known "sailor in the fog" puzzle. The first version (the "asteroid surveying" problem) is set in three dimensions and asks for the shortest...
An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint (2003)
Claude-guy Quimper, Peter Van Beek, Alejandro Lopez-Ortiz, Alexander Golynski, Ro Lopez-ortiz, Er Golynski, ...
Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the e#ciency of a constraint programming approach. In this paper we present an...
An efficient bounds consistency algorithm for the global cardinality constraint (2003)
Claude-guy Quimper, Peter Van Beek, Ro López-ortiz, Er Golynski, Sayyed Bashir Sadjad
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we...
An efficient bounds consistency algorithm for the global cardinality constraint (2003)
Claude-guy Quimper, Er Golynski, Ro López-ortiz, Peter Van Beek
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we...
A fast and simple algorithm for bounds consistency of the alldifferent constraint (2003)
Ro Lopez-ortiz, Claude-guy Quimper, John Tromp, Peter Van Beek
In constraint programming one models a problem by stating constraints on acceptable solutions. The constraint model is then usually solved by interleaving backtracking search and constraint...
An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint (2003)
Claude-guy Quimper, Peter Van Beek, Ro López-ortiz, Er Golynski, Sayyed Bashir Sadjad
Abstract. Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we...