4 présentations

• 
  10h30 - 10h55

  Counting Spanning Trees to Guide Search in Constrained Spanning Tree Problems

  • Simon Brockbank, prés., Polytechnique Montréal
  • Gilles Pesant, Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montréal

  Counting-based 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

  Solution-Density Branching for Precedence Constrained Disjunctive Scheduling Problems

  • Rachid Cherkaoui, prés., Polytechnique Montréal
  • Gilles Pesant, Polytechnique Montréal

  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 variable-value 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 CP-Nets

  • Malek Mouhoub, prés., University of Regina
  • Eisa Alanazi, University of Regina

  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 CP-Net) where preferences and constraints are represented through CP-Nets and Constraint Satisfaction Problems (CSPs) respectively. A CP-Net 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 CP-Net consists then in finding a scenario satisfying all the constraints of the related CSP while maximizing all the CP-Net preferences. Constrained CP-Nets 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 CP-Net instances randomly generated using the RB model.

• 
  11h45 - 12h10

  Achieving Domain Consistency and Counting Solutions for Balance Constraints

  • Gilles Pesant, prés., Polytechnique Montréal

  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 counting-based search, a generic and effective family of branching heuristics that free the user from having to write problem-specific 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.