Previous Up Next

17.3  A Simple Example

17.3.1  Problem Definition

We start with a simple example of linear constraints being posted to eplex and the other constraints being sent to ic.

The example problem involves three tasks (task1, task2, task3) and a time point time1. We enforce the following constraints:

17.3.2  Program to Determine Satisfiability

For this example we handle the first constraint using ic, because it is not expressible as a conjunction of linear constraints, and we handle the second pair of linear constraints using eplex.

⊗
Note that since we use both solvers eplex and ic we will explicitly module qualify all numeric constraints to avoid ambiguity.

Each task has a start time Start and a duration Duration. We encode the (non-linear) overlap constraint in ic thus: 

:- lib(ic).
overlap(Start,Duration,Time,Bool) :-
        % Bool is 1 if the task with start time Start and duration
        % Duration overlaps time point Time and 0 otherwise
       ic: (Bool #= ((Time $>= Start) and (Time $=< Start+Duration-1))).

The variable Bool takes the value 1 if the task overlaps the time point, and 0 otherwise. To enforce that only one task overlaps the time point, the associated boolean variables must sum to 1.

We encode the (linear) precedence constraint in eplex thus: 

:- lib(eplex).
before(Start,Duration,Time) :-
        % the task with start time Start and duration Duration is
        % completed before time point Time
        eplex: (Start+Duration $=< Time).

To complete the program, we can give durations of 3 and 5 to task1 and task2, and have the linear solver minimise the start time of task3: 

ic_constraints(Time,S1,S2,B1,B2) :-
        % exactly one of task 1 with duration 3 and task 2 with
        % duration 5 overlaps time point Time
        ic: ([S1,S2]::1..20),
        overlap(S1,3,Time,B1),
        overlap(S2,5,Time,B2),
        ic: (B1+B2 #= 1).

eplex_constraints(S1,S2,S3) :-
        % task 1 with duration 3 and task 2 with duration 5 are both
        % completed before the start time of task 3
        before(S1,3,S3),
        before(S2,5,S3).
 
hybrid1(Time, [S1,S2,S3], End) :-
        % give the eplex cost variable some default bounds
        ic:(End $:: -1.0Inf..1.0Inf),
        % we must give the start time of task 3 ic bounds in order to
        % suspend on changes to them
        ic: (S3::1..20),
        % setup the problem constraints
        ic_constraints(Time,S1,S2,B1,B2),
        % setup the eplex solver
        eplex_constraints(S1,S2,S3),
        eplex:eplex_solver_setup(min(S3),End,[sync_bounds(yes)],[ic:min,ic:max]),
        % label the variables occurring in ic constraints
        labeling([B1,B2,S1,S2]).

During the labeling of the boolean variables, the bounds on S1 and S2 are tightened as a result of ic propagation, which wakes the linear solver, which has been set to trigger on ic bound changes (ic:min, ic:max). Note that all variables occurring in the linear solver must then have ic attributes.

The ic bounds are passed to the linear solver before the problem is solved with the option sync_bounds(yes). The linear solver derives a new lower bound for End. In case this exceeds its upper bound, the search fails and backtracks.

Using this method of bound communication the bounds for all problem variables are retrieved from any bounds solvers before resolving the linear problem. If however only a small number of variable bounds have changed sufficiently to affect the relaxed solution this will be inefficient.

Instead bound updates for individual variables and bound solvers may be transferred to the linear solver separately. This may be achieved (using the eplex instance’s ::/2) either explicitly within the search code or through demons attached to the appropriate solver bound changes.

Note that the optimisation performed by the linear solver does not respect the ic constraints, so a correct answer can only be guaranteed once all the variables involved in ic constraints are instantiated.

Henceforth we will not explicitly show the loading of the ic and eplex libraries.

17.3.3  Program Performing Optimisation

When different constraints are sent to ic and to eplex, the optimisation built into the linear solver must be combined with the optimisation provided by the ECLiPSe branch_and_bound library.

The following program illustrates how to combine these optimisations: 

:- lib(branch_and_bound).

hybrid2(Time, [S1,S2,S3], End) :-
        % give the eplex cost variable some default bounds
        ic:(End $:: -1.0Inf..1.0Inf),
        % we must give the start time of task 3 ic bounds in order to
        % suspend on changes to them
        ic: (S3::1..20),
        % setup the problem constraints
        ic_constraints(Time,S1,S2,B1,B2),
        eplex_constraints(S1,S2,S3),
        % perform the optimisation
        both_opt(labeling([B1,B2,S1,S2]),min(S3),End).

both_opt(Search,Obj,Cost) :-
        % setup the eplex solver
        eplex:eplex_solver_setup(Obj,Cost,[sync_bounds(yes)],[ic:min,ic:max]),
        % minimize Cost by branch-and-bound
        minimize((Search,eplex_get(cost,Cost)),Cost).

A simple way to combine eplex and ic is to send the linear constraints to eplex and the other constraints to ic. The optimisation primitives must also be combined.
Figure 17.2: A Simple Example
Previous Up Next