Journées de l'optimisation 2014
Incluant une Journée industrielle de l'optimisation
HEC Montréal, 5  7 mai 2014
JOPT2014
HEC Montréal, 5 — 7 mai 2014
MB8 Programmation par contraintes 1 / Constraint Programming 1
5 mai 2014 10h30 – 12h10
Salle: TD Assurance Meloche Monnex
Présidée par Gilles Pesant
4 présentations

10h30  10h55
Counting Spanning Trees to Guide Search in Constrained Spanning Tree Problems
Countingbased branching heuristics such as maxSD were shown to be effective on a variety of constraint satisfaction problems.
These heuristics require that we equip each family of constraints with a dedicated algorithm to compute the local solution density of variable assignments, much as what has been done with filtering algorithms to apply local inference.
This paper derives an exact polytime algorithm to compute solution densities for a spanning tree constraint,
starting from a known result about the number of spanning trees in a graph.
We then empirically compare branching heuristics based on that result with other generic heuristics. 
10h55  11h20
SolutionDensity Branching for Precedence Constrained Disjunctive Scheduling Problems
Designing robust generic branching heuristics is an important step in making constraint programming competitive with other approaches to combinatorial problem solving. Among such heuristics those based on counting solutions, such as maxSD, exploit the structure of a model by querying each constraint about how frequently a given variablevalue assignment appears in solutions. They require that we equip each family of constraints with a dedicated algorithm to compute the local solution density of variable assignments, much as what has been done with filtering algorithms to apply local inference. The area of scheduling has been an excellent proving ground for constraint programming. In this talk we propose exact and heuristic algorithms that compute solution densities for a disjunctive resource constraint with some precedences between tasks. We then show how branching heuristics derived from such information can be effective on scheduling problems such as the Jump Number Problem.

11h20  11h45
Constraint Propagation for Constrained CPNets
Managing both constraints and preferences is often required when tackling a wide variety of real world applications such as scheduling, planning and configuration. The goal here is to satisfy all the constraints while maximizing a given utility function. We model these types of problems using the Constrained Conditional Preference Network (Constrained CPNet) where preferences and constraints are represented through CPNets and Constraint Satisfaction Problems (CSPs) respectively. A CPNet is a graphical model for managing qualitative preference statements including conditional preferences of the form: "If A is true then I prefer X over Y". A CSP involves a list of variables, each defined on a set of discrete values, and a list of constraints restricting the values that each variable can take. The aim here is to find a complete assignment of values to variables such that all the constraints are satisfied. Solving a constrained CPNet consists then in finding a scenario satisfying all the constraints of the related CSP while maximizing all the CPNet preferences. Constrained CPNets have gained a considerable attention recently and have been tackled using backtrack search. However, a little study has been dedicated to the effect of variable ordering heuristics as well as constraint propagation techniques on the performance of the backtrack search. We experimentally investigate several constraint propagation strategies while adopting well known variable ordering heuristics. This is done by conducting an experimental study on several constrained CPNet instances randomly generated using the RB model.

11h45  12h10
Achieving Domain Consistency and Counting Solutions for Balance Constraints
Many combinatorial problems require of their solutions that they achieve a certain balance of given features. For this important aspect of modeling, the spread and deviation constraints have been proposed in Constraint Programming to express balance among a set of variables by constraining their mean and their overall deviation from the mean. Currently the only practical filtering algorithms known for these constraints achieve bounds consistency. In this presentation we improve that filtering by presenting an efficient domain consistency algorithm that applies to both constraints. We also extend it to count solutions so that it can be used in countingbased search, a generic and effective family of branching heuristics that free the user from having to write problemspecific search heuristics. We provide a time complexity analysis of our contributions and also evaluate them empirically on the Balanced Academic Curriculum Problem and the Nurse to Patient Assignment Problem.