Previous Up Next

17.4  Sending Constraints to Multiple Solvers

17.4.1  Syntax and Motivation

Because of the cooperation between solvers, it is often useful to send constraints to multiple solvers. A linear constraint, such as X+2 ≥ Y, can be posted to eplex by the code eplex: (X+2 $>= Y). The same constraint can be posted to ic by the code ic: (X+2 $>= Y). The constraint can be sent to both solvers by the code 

   [ic,eplex]: (X+2 $>= Y)

By sending constraints to both solvers, where possible, we can improve search algorithms for solving constraint problems. Through enhanced constraint reasoning at each node of the search tree we can:

The second advantage is a particular benefit of combining different solvers, as opposed to enhancing the reasoning power of a single solver. See [22] and [23] for experimental results and application examples using multiple solvers in this way.

17.4.2  Handling Booleans with Linear Constraints

The overlap constraint example above is disjunctive and therefore non-linear, and is only handled by ic. However as soon as the boolean variable is labelled to 1, during search, the constraint becomes linear.

The cooperation between the eplex and ic solvers could therefore be improved by passing the resulting linear constraint to eplex as soon as the boolean is labelled to 1. This could be achieved using a constraint handling rule (see CHR) or a suspended goal (see chapter 14).

However the same improved cooperation can be achieved by a well known mathematical programming technique (see e.g. [30]) that builds the boolean variable into a linear constraint that can be sent to eplex even before the boolean is instantiated. This linear constraint effectively enforces the overlap constraint if the boolean is instantiated to 1, but does not enforce it if the boolean is instantiated to 0.

To achieve this we introduce sufficiently big multipliers, that when the boolean is set to 0 the constraint is satisfied for all values within the variables’ bounds. This method is known as the bigM transformation.

It is illustrated in the following encoding of pos_overlap: 

pos_overlap(Start,Duration,Time,Bool) :-
        % if Bool is 1 then the task with start time Start and
        % duration Duration overlaps time point Time
        Max1 is maxdiff(Start,Time),
        Max2 is maxdiff(Time,Start+Duration-1),      
        eplex: (Time+(1-Bool)*Max1 $>= Start),              % lin1
        eplex: (Time $=< Start+Duration-1+(1-Bool)*Max2).   % lin2

maxdiff(Expr1,Expr2,MaxDiff) :-
        % the maximum diffrence between Expr1 and Expr2 is the max val
        % of (Expr1 - Expr2)
        MaxDiff is max_val(Expr1 - Expr2).

max_val(Expr, Max) :-
        % the maximum value of a variable is its upper bound
        var(Expr),!,
        get_var_bounds(Expr, _, Max).
max_val(Expr, Max) :-
        % the maximum value of a number is itself
        number(Expr),!,
        Max = Expr.
max_val(Expr1 + Expr2, Max) :-
        % the maximum value of (Exrp1 + Expr2) is the maximum value of
        % Expr1 plus the maximum value of Expr2
        Max is max_val(Expr1) + max_val(Expr2).
max_val(Expr1 - Expr2, Max) :-
        % the maximum value of (Exrp1 - Expr2) is the maximum value of
        % Expr1 minus the minimum value of Expr2
        Max is max_val(Expr1) - min_val(Expr2).

min_val(Expr, Min) :-
        % the minimum value of a variable is its lower bound
        var(Expr),!,
        get_var_bounds(Expr, Min, _).
min_val(Expr, Min) :-
        % the minimum value of a number is itself
        number(Expr),!,
        Min = Expr.
min_val(Expr1 + Expr2, Max) :-
        % the minimum value of (Exrp1 + Expr2) is the minimum value of
        % Expr1 plus the minimum value of Expr2
        Max is min_val(Expr1) + min_val(Expr2).
min_val(Expr1 - Expr2, Max) :-
        % the minimum value of (Exrp1 - Expr2) is the minimum value of
        % Expr1 minus the maximum value of Expr2
        Max is min_val(Expr1) - max_val(Expr2).

The linear constraints, which will enforce the overlap condition when the variable Bool is set to 1, are labelled lin1 and lin2. If the variable Bool is instantiated to 0, then the variables (or values) Start, Time and Duration are free to take any value in their respective domains.

Notice that pos_overlap is logically weaker than overlap because

The tighter cooperation is achieved simply by adding the pos_overlap constraint to the original encoding: 

eplex_constraints_2(Time,S1,S2,S3,B1,B2) :-
        % 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),
        % task 1 with duration 3 overlaps time point Time if B1 = 1
        pos_overlap(S1,3,Time,B1),
        % task 2 with duration 5 overlaps time point Time if B2 = 1
        pos_overlap(S2,5,Time,B2).

hybrid3(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(Time,S1,S2,S3,B1,B2),
        % perform the optimisation
        both_opt(labeling([B1,B2,S1,S2]),min(S3),End).

Although it may at first glance seem better to enforce the integerality of all variables in the linear solver as well, this is in fact counter-productive for variables that will be explicitly labelled during search in hybrid algorithms. The external solver would then perform its own branch-and-bound search in addition to the branch-and-bound search being performed within the ECLiPSe program.

17.4.3  Handling Disjunctions

The same technique, of introducing boolean variables and sufficiently large multipliers, can be used to translate any disjunction of linear constraints into linear constraints (and integrality constraints on the booleans) which can be handled by eplex.

Consider the negation of the overlap constraints above: if a task does not overlap a time point then it is either completed before the time point or starts after the timepoint. This disjunction can be expressed in eplex using two further boolean variables: 

neg_overlap(Start,Duration,Time,Bool1,Bool2) :-
        % if Bool1 is 1 then the task with start time Start and duration
        % Duration starts after time point Time
        Max1 is maxdiff(Time,Start-1),
        eplex:(Time $=< Start-1+(1-Bool1)*Max1),
        % if Bool2 is 1 then the task with start time Start and duration
        % Duration is completed before time point Time
        Max2 is maxdiff(Start+Duration,Time),
        eplex:(Time+(1-Bool2)*Max2 $>= Start+Duration).

eplex_constraints_3(T,S1,S2,S3,B1,N1B1,N2B1,B2,N1B2,N2B2) :-
        % 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),
        % task 1 with duration 3 either overlaps time point Time,
        % starts after it or is completed before it
        pos_overlap(S1,3,T,B1),
        neg_overlap(S1,3,T,N1B1,N2B1),
        eplex:(N1B1+N2B1 $= 1-B1),
        % task 2 with duration 5 either overlaps time point Time,
        % starts after it or is completed before it
        pos_overlap(S2,5,T,B2),
        neg_overlap(S2,5,T,N1B2,N2B2),
        eplex:(N1B2+N2B2 $= 1-B2),
        % exactly one of task 1 with duration 3 and task 2 with
        % duration 5 overlaps time point Time
        eplex:(B1+B2 $= 1).

hybrid4(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 and the non-overlap
        % booleans ic bounds in order to suspend on changes to them
        ic:(S3::1..20),
        ic:([N1B1,N2B1,N1B2,N2B2]::0..1),
        % setup the problem constraints
        ic_constraints(Time,S1,S2,B1,B2),
        eplex_constraints_3(Time,S1,S2,S3,B1,N1B1,N2B1,B2,N1B2,N2B2),
        % perform the optimisation
        both_opt(labeling([B1,N1B1,N2B1,B2,N1B2,N2B2,S1,S2]),min(S3),End).

Now the negation of the overlap will be enforced whenever either of the non-overlap booleans is set to 1. Note that it is not strictly necessary to label the non-overlap booleans: whenever the start time of a task is labelled in such a way that the task falls to one side of the time point, the other non-overlap boolean will be forced to 0 by its linear non-overlap constraint. The constraint requiring a task to either overlap or fall to one side of the time point will then force the remaining non-overlap boolean to be 1.

In fact in this simple example we gain nothing by including the neg_overlap constraints on the “direction” of non-overlap. As soon as a labeling decision has been made as to whether one task overlaps the time point, the earliest possible start time of both tasks is updated in the linear solver. Since the problem cost is minimized by starting all tasks as early as possible, the relaxed eplex solution will conicide with the integer solution.

As another simple example consider a naive program to choose values for the elements of a finite list (of length Length) such that each pair of values differs by at least 2. The diff2 constraint on each pair X and Y of elements can be expressed as a disjunction in ic: 

diff2ic(X,Y) :-
        % X and Y must differ by at least 2
        ic: ((X+2 $=< Y) or (Y+2 $=< X)).

list_diff2ic(List) :-
        % each pair must differ by at least 2
        (
            fromto(List, [X|Rest], Rest, [])
        do
            (
                foreach(Y, Rest),
                param(X)
            do
                diff2ic(X,Y)
            )
        ).

Alternatively it can be expressed in eplex using a boolean variable: 

diff2eplex(X,Y,Length,B) :-
        % if B is 1 then Y is at least 2 greater than X
        eplex: (X+2+B*Length $=< Y+Length),
        % if B is 0 then X is at least 2 greater than Y
        eplex: (X+Length $>= Y+2+(1-B)*Length).

list_diff2eplex(List, Length, Bools) :-
        % each pair must differ by at least 2
        (
            fromto(List, [X|Rest], Rest, []),
            fromto(Bools, Out, In, []),
            param(Length)
        do
            (
                foreach(Y, Rest),
                fromto(Out, [B|Bs], Bs, In),
                param(X, Length)
            do
                diff2eplex(X,Y,Length,B)
            )
        ).

Suppose each element E of the list must take a value between 1 and 2*(Length−1), then any attempted labelling of the elements must fail. Sending the constraints to ic and labelling the elements of the list is inefficient. 

ic_list(List) :-
        length(List, Length),
        Max is 2*(Length-1),
        % each element must take a value between 1 and 2*(Length-1)
        ic: (List::1..Max),
        list_diff2ic(List),
        labeling(List).

Sending the constraints to eplex and enforcing integrality of the booleans is more efficient. 

eplex_list(List) :-
        length(List, Length),
        Max is 2*(Length-1),
        % each element must take a value between 1 and 2*(Length-1)
        eplex: (List::1..Max),
        list_diff2eplex(List, Length, Bools),
        % enforce Bools to be 0..1 and integer
        eplex: integers(Bools),
        eplex: (Bools::0..1),
        % setup the eplex solver with a dummy objective function
        eplex:eplex_solver_setup(min(0),Cost,[],[]),
        % solve by linear solver
        eplex:eplex_solve(Cost).

Better still is to post the constraints to both ic and eplex, and label the booleans. 

hybrid_list(List) :-
        % give the eplex cost variable some default bounds
        ic:(Cost $:: -1.0Inf..1.0Inf),
        length(List, Length),
        Max is 2*(Length-1),
        % each element must take a value between 1 and 2*(Length-1)
        ic: (List::1..Max),
        list_diff2ic(List),
        list_diff2eplex(List, Length, Bools),
        % enforce Bools to be 0..1 (but not integer in eplex)
        ic: (Bools::0..1),
        % setup the eplex solver with a dummy objective function
        eplex:eplex_solver_setup(min(0),Cost,[sync_bounds(yes)],[ic:min,ic:max]),
        % minimize Cost by branch-and-bound
        minimize((labeling(Bools),eplex_get(cost,Cost)),Cost).

17.4.4  A More Realistic Example

For more complex applications, sending all “linearisable” constraints to both ic and eplex is rarely the best method. Sending too many constraints to ic can result in many wakings but little useful propagation. Sending too many constraints to eplex can cause a big growth in the size of the constraint store, which slows down constraint solving with little improvement in the relaxed optimum. If the extra variables are constrained to be integer, then the (MIP) solver may enter a deep search tree with disastrous consequences for efficiency. In this example we briefly illustrate the point, though there is no space to include the whole program, and complete supporting results.

Consider the problem of generating test networks for IP (internet protocol). To generate such networks, it is necessary to assign capacities to each line. We assume a routing algorithm that sends each message along a “cheapest” path, where the cost is dependent on the bandwidth. Messages from a particular start to end node are divided equally amongst all cheapest paths.


Path Flows

Given a total quantity Qty of messages, between a particular start and end node, it is necessary to compute the quantity of messages QtyP along each path P between the two nodes. The variable CostP represents the cost of this path, and the variable MinCost represents the cost of the cheapest path. The variable Count represents the number of cheapest paths (between which the messages were equally divided). A boolean variable BP records whether the current path is a cheapest path, and therefore whether QtyP is non-zero. The encoding in ic is as follows: 

ic: '$>='(MinCost + 1, CostP,BP),    % con3
ic: (QtyP*Count $= BP*Qty)         % con4

Note that it is not possible to test for equality between MinCost and CostP because they are not integers but real number variables.

These constraints are very precise but propagate little until the variables MinCost and CostP have tight bounds.

The challenge is to find a combination of ic and eplex constraint handling that efficiently extract the maximum information from the constraints. Linearising con3 so it can be handled by eplex does not help prune the search tree. Worse, it may significantly increase the size of the linear constraint store and the number of integer (boolean) variables, which impacts solver performance.

Once all the boolean variables are instantiated, the sum of QtyP for all the paths equals the total quantity Qty (because precisely Count paths have a non-zero PQty = Qty / Count). We therefore introduce a variable Qties constrained to be the sum of all the path quantities. If QtyList is a list of the path quantities, we can express the constraint thus Qties $= sum(QtyList). We can now add a redundant constraint Qty $= Qties. The above constraints are both linear and can be handled by eplex.

In practice this encoding dramatically enhances the efficiency of the test network generation. Experimentation with this program revealed that posting the redundant constraints to eplex yields a much more significant improvement than just posting them to ic.

It is easy to send a constraint to more than one solver. Even disjunctive constraints can be encoded in a form that enables them to be sent to both solvers. However for large applications it is best to send constraints only to those solvers that can extract useful information from them. This requires experimentation.
Figure 17.3: Sending Constraints to Multiple Solvers
Previous Up Next