Latest Research Papers
Learning the Parameters of Global Constraints Using Branch-and-Bound
Abstract. Precise constraint satisfaction modeling requires specific knowledge acquired from multiple past cases. We address this issue with a general branch-and-bound algorithm that learns the parameters of a given global constraint from a small set of positive solutions. The idea is to cleverly explore the possible combinations taken by the constraint’s parameters without explicitly enumerating all combinations. We apply our method to learn parameters of global constraints used in timetabling problems such as Sequence and SubsetFocus. The later constraint is our adaptation of the constraint Focus to timetabling problems.
​
Keywords: Constraint Acquisition, Timetabling, Machine Learning, CSP, Global Constraints, Brand-and-Bound
​
Authors: Émilie Picard-Cantin, Mathieu Bouchard, Claude-Guy Quimper and Jason Sweeney
​
Learning Parameters For the Sequence Constraint From Solutions
Abstract. This paper studies the problem of learning parameters for global constraints such as Sequence from a small set of positive examples. The proposed technique computes the probability of observing a given constraint in a random solution. This probability is used to select the more likely constraint in a list of candidates. The learning method can be applied to both soft and hard constraints.
​
Keywords: Constraint Acquisition, Timetabling, Machine Learning, CSP, Global Constraints, Solution Counting, Markov Chain, Soft Constraints
​
Authors: Émilie Picard-Cantin, Mathieu Bouchard, Claude-Guy Quimper and Jason Sweeney
​
The Balance Constraint Family
Abstract. The BALANCE constraint introduced by Beldiceanu ensures solutions are balanced. This is useful when, for example, there is a requirement for solutions to be fair. BALANCE bounds the difference B between the minimum and maximum number of occurrences of the values assigned to the variables. We show that achieving domain consistency on BALANCE is NP-hard. We therefore introduce a variant, ALLBALANCE with a similar semantics that is only polynomial to propagate. We consider various forms of ALLBALANCE and focus on ATMOSTALLBALANCE which achieves what is usually the main goal, namely constraining the upper bound on B. We provide a specialized propagation algorithm, and a powerful decomposition both of which run in low polynomial time. Experimental results demonstrate the promise of these new filtering methods.
​
Authors: Christian Bessiere, Emmanuel Hebrard, George Katsirelos, Zeynep Kiziltan, Émilie Picard-Cantin, Claude-Guy Quimper, and Toby Walsh
​
