4 présentations

• 
  15h30 - 15h55

  A High Level Language for Solver Independent Model Manipulation and Generation of Hybrid Solvers

  • Laurent Michel, University of Connecticut
  • Daniel Fontaine, prés., University of Connecticut

  This paper introduces a high level language that allows for the specification and manipulation of solver independent models and al- lows for easily generating complex solvers in the Comet language. As Constraint Programming (CP) techniques have increased in complexity, it has become more difficult and time consuming to implement models that take advantage of state-of-the-art modeling techniques and search heuristics. This is particularly problematic for problems that have not been well studied as it is often unclear a priori which modeling technologies and search
  strategies will be effective. This work builds on previous solver independent languages by introducing a more general framework based on abstract models and model operators. Model operators
  represent complex model transformations that can be applied in various combinations to yield a wide array of concrete solvers, including hybrid solvers. Furthermore, Local Search (LS) is fully supported allowing for sequential and parallel bounds-passing hybrids that have not been possible in previous solver independent languages. Large Neighborhood Search (LNS) and column generation based models are also demonstrated.

• 
  15h55 - 16h20

  Pseudo-Boolean Nogood Learning

  • Meinolf Sellmann, prés., IBM Research

  A no-good learning approach for multi-valued satisfaction (SAT) problems is presented which is shown to infer significantly stronger no-goods than those inferred by a mechanism that is based on a Boolean representation. Like earlier methods, the learning approach is based on an implication graph where nodes represent domain events and edges are implications drawn by the clauses in the given problem. The approach focusses on variable inequalities to infer the minimal reasons for a failure. We investigate why this particular use of inequalities results in stronger no-goods and we formulate a general framework for multi-valued nogood-learning that can handle more general constraints, and also different domain representations, such as interval domains, which are commonly used for bounds consistency in constraint programming (CP).

• 
  16h20 - 16h45

  CP-Net and C-Seminring for Online Shopping Applications under Preferences

  • Bandar Mohammed, prés., University of Regina
  • Malek Mouhoub, University of Regina

  Online shopping has significantly increased in the past decade. It is still however challenging for internet shoppers to select the product meeting their requirements and preferences. Indeed,
  many shopping websites constrain the customers to choose among their alternatives and not necessarily the options that meet their needs and satisfaction. This motivated us to develop an
  expressive model handling both constraints (requirements) and preferences. These latter can be qualitative or quantitative and are represented respectively using CP-nets and the C-semiring
  structure. An online shopping application based on our model has been implemented.

• 
  16h45 - 17h10

  Filtering Algorithms Based on the Word-RAM Model

  • Claude-Guy Quimper, prés., Université Laval
  • Philippe Van Kessel, Université Laval

  The Word-RAM is a model of computation that takes into account the capacity of a computer to manipulate a word of w bits with a single instruction. Many modern constraint solvers use a bitset data structure to encode the values contained in the variable domains. Using the algorithmic techniques developed for the Word-RAM, we propose new filtering algorithms that can prune O(w) values from a domain in a single instruction. Experiments show that on a processor with w=64, the new filtering algorithms that enforce domain consistency on the constraints A+B=C, |A-B|=C and All-Different can offer a speed up of a factor 10.