17.2  Reasons for Combining Solvers

The ic solver library implements two kinds of constraints

• finite domain constraints
• interval constraints

Each constraint is handled separately and individually, and the only communication between them is via the bounds on their shared variables.

The benefits of the ic solvers are

1. the repeated tightening of guaranteed upper and lower bounds on the variables
2. the application of tailored algorithms to standard subproblems (encapsulated as global constraints)
3. the implementation of a very wide class of constraints

The eplex solver library implements two kinds of constraints

• linear numeric constraints
• integrality constraints

The linear constraints are handled by a very powerful solver that enforces global consistency on all the constraints. The integrality constraints are handled via a built-in search mechanism.

The benefits of the eplex solvers are

1. the enforcement of global consistency for linear constraints
2. the production of an optimal solution satisfying the linear constraints

For some years researchers have sought to characterise the classes of problems for which the different solvers are best suited. Problems involving only linear constraints are very well handled by eplex. Problems involving disjunctions of constraints are often best handled by ic. Often set covering problems are best handled by eplex and scheduling problems by ic. However in general there is no method to recognise for a new problem which solver is best.

Luckily in ECLⁱPS^e there is no need to choose a specific solver for each problem, since it is possible to apply both solvers. Moreover the solvers communicate with each other, thus further speeding up constraint solving. The ic solver communicates new tightened bounds to the eplex solver. These tightened bounds have typically been deduced from non-linear constraints and thus the linear solver benefits from information which would not otherwise have been available to it. On the other hand the eplex solver often detects inconsistencies which would not have been detected by the ic solvers. Moreover it returns a bound on the optimisation function which can be used by the ic constraints. Finally the optimal solution returned by eplex to the “relaxed” problem comprising just the linear constraints, can be used as a search heuristic that can focus the ic solver on the most promising parts of the search space.

---

There are two main reasons for combining eplex and ic in a hybrid algorithm ic handles a wider class of constraints than eplex The solvers extract different kinds of information from the constraints

Figure 17.1: Motivation

---