Inference

Like many other computational methods in the area of combinatorial problem solving, Constraint Programming expresses the problem at hand through formal mathematical modelling. Unlike them, the language in which the model is formulated features high-level primitives that explicitly expose much of the combinatorial structure of the problem. We sacrice the simple syntax that creates an opportunity for highly-optimized monolithic solvers, but gain the rich semantics that can, and has been, exploited for both inference and search. The distinctive driving force of CP has been this direct access to structure.

Most structure is captured in individual constraints. Each on its own may represent an important characteristic of the problem such as building a Hamiltonian cycle on a graph, packing items into bins, or scheduling tasks on a cumulative resource. In CP it is not unusual that a few constraints suffice to model a complex combinatorial problem. Each type of constraint encapsulates a dedicated filtering algorithm that acts on the domains of variables by filtering out inconsistent values, thereby reducing the search space.

Related publications are identified by #filtering

Search

The search space is explored by problem decomposition, building a search tree whose branches at a node correspond to decisions that partition the current search space. These decisions can be arbitrary constraints added to the model for that subtree but typically they fix a variable to a value in its domain in the left branch and remove that value from the domain in the right branch. Branching heuristics guide how the search tree is built.

Designing a branching heuristic for CP that is reliable across problem domains has been an important research topic. Counting-Based Search (CBS) seeks to make branching decisions that preserve most of the solutions by determining what proportion of solutions to each individual constraint agree with that decision. Whereas most generic branching heuristics in constraint programming rely on local information at the level of the individual variable, CBS is based on more global information at the constraint level. This approach is also applied to solve optimization problems: here we look at the proportion of near-optimal solutions.

Related publications are identified by #CBS

The coordination problem between autonomous agents in a supply chain environment can be formulated as adaptive distributed tree search.

Related publications are identified by #distrib

Soft Constraints

Many real-life problems are over-constrained. In CP we seek feasible solutions to a given problem. Hence we cannot apply constraint programming directly to over-constrained problems because it finds no solution. Allowing in our models a mix of hard and soft constraints, the latter possibly being violated, re-establishes feasibility but we still wish to use soft constraints in an active way to restrict the search space. Filtering algorithms parameterized by the amount of violation permitted for a constraint have been proposed.

Related publications are identified by #soft

Hybrid Methods

A growing number of applications of constraint programming hybridize it with some other combinatorial optimization approach. Over the years we have investigated combinations with such complementary approaches as local search, column generation, integer programming, and Benders' decomposition.

Related publications are identified by #hybrid

Workforce Scheduling

The planning of employee work schedules is a classic application area for constraint programming and we have worked on a number of aspects such as  building cyclic or personalized rosters over an horizon of several weeks or months, building daily work shifts, and balancing the workload among employees.

Related publications are identified by #rostering

Health Care

We have applied constraint programming to interesting problems in the management of health care, including nurse and physician rostering, operating room scheduling, and nurse workload balancing.

Related publications are identified by #health

Forestry

Forestry is a very important sector of the Canadian economy. We have worked on logging road construction, log-truck routing, and saw mill operations planning.

Related publications are identified by #forestry

Software and Hardware Systems Testing

Software and embedded systems are increasingly complex while their time-to-market is shrinking. Testing these systems is a potentially very time-consuming activity. We have worked on test-case generation for software and on the verification of performance metrics for multiprocessor systems on chip (MPSoC).

Related publications are identified by #verif