03:30 PM - 03:55 PM
A High Level Language for Solver Independent Model Manipulation and Generation of Hybrid Solvers
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.
03:55 PM - 04:20 PM
Pseudo-Boolean Nogood Learning
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).
04:20 PM - 04:45 PM
CP-Net and C-Seminring for Online Shopping Applications under Preferences
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.
04:45 PM - 05:10 PM
Filtering Algorithms Based on the Word-RAM Model
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.