This is the second of two special issues focusing on the integration of artificial intelligence (AI) and operations research (OR) techniques for solving hard computational problems, with an emphasis on planning and scheduling. Both the AI and the OR community have developed sophisticated techniques to tackle such challenging problems. OR has relied heavily on mathematical programming formulations such as integer and linear programming, while AI has developed constraint-based search techniques and inference methods. Recently, we have seen a convergence of ideas, drawing on the individual strengths of these paradigms.

Maths programming (MP) and constraint programming (CP) are two techniques that are able to solve difficult industrial optimisation problems. The purpose of this paper is to compare them from an algorithmic and a modelling point of view. Algorithmic principles of each approach are described and contrasted. Some ways of combining both techniques are also introduced.

Many optimisation problems involve combinatorial constraints on continuous variables. An example of a combinatorial constraint is that at most one variable in a group of nonnegative variables may be positive. Traditionally, in the mathematical programming community, such problems have been modeled as mixed-integer programs by introducing auxiliary binary variables and additional constraints. Because the number of variables and constraints becomes larger and the combinatorial structure is not used to advantage, these mixed-integer programming models may not be solved satisfactorily, except for small instances. Traditionally, constraint programming approaches to such problems keep and use the combinatorial structure, but do not use linear programming bounds in the search for an optimal solution. Here we present a branch-and-cut approach that considers the combinatorial constraints without the introduction of binary variables. We review the development of this approach and show how strong constraints can be derived using ideas from polyhedral combinatorics. To illustrate the ideas, we present a production scheduling model that arises in the manufacture of fibre optic cables.

This paper presents several case studies which illustrate how constraint programming can benefit from the combination of global and local search techniques, offering a flexible and efficient platform for the design of combinatorial optimisation applications. For job-shop scheduling, we relate experiments with local search procedures that use global search to intensively explore a given neighbourhood, in the spirit of “shuffle” methods. For preemptive job-shop scheduling, two basic search strategies, Depth-First Search and Limited Discrepancy Search, are compared. For Vehicle Routing we report an Incremental Local Optimisation heuristic, combined with Limited Discrepancy Search. Finally, we show how ad hoc algebras can considerably enhance the design of heuristics based on local and global search within a constraint-programming environment. Experiments on vehicle routing will enlighten how such a language for “search and insert” control can enable automated tuning and discovery of new strategies adapted to the instances typology of the problem at stake.

In this paper we describe the framework we have developed in KIDS (Kestrel Interactive Development System) for generating efficient constraint satisfaction programs. We have used KIDS to synthesise global search scheduling programs that have proved to be dramatically faster than other programs running the same data. We focus on the underlying ideas that lead to this efficiency. The key to the efficiency is the reduction of the size of the search space by an effective representation of sets of possible solutions (solution spaces) that allows efficient constraint propagation and pruning at the level of solution spaces. Moving to a solution space representation involves a problem reformulation. Having found a solution to the reformulated problem, an extraction phase extracts solutions to the original problem. We show how constraints from the original problem can be automatically reformulated and specialised in order to derive efficient propagation code automatically. Our solution methods exploit the semi-lattice structure of our solution spaces.

Compilation to Boolean satisfiability has become a powerful paradigm for solving artificial intelligence problems. However, domains that require metric reasoning cannot be compiled efficiently to satisfiability even if they would otherwise benefit from compilation. We address this problem by combining techniques from the artificial intelligence and operations research communities. In particular, we introduce the LCNF (Linear Conjunctive Normal Form) representation that combines propositional logic with metric constraints. We present LPSAT (Linear Programming plus SATisfiability), an engine that solves LCNF problems by interleaving calls to an incremental Simplex algorithm with systematic satisfaction methods. We explore several techniques for enhancing LPSAT's efficiency and expressive power by adjusting the interaction between the satisfiability and linear programming components of LPSAT. Next, we describe a compiler that converts metric resource planning problems into LCNF for processing by LPSAT. Finally, the experimental section of the paper explores several optimisations to LPSAT, including learning from constraint failure and randomised cutoffs.