Previous Up Next

17.5  Using Values Returned from the Linear Optimum

In this section we explore ways of using the information returned from the optimum solution produced by the linear solver. We will cover two kinds of information. First we will show how reduced costs can be used to filter variable domains. Secondly we will show how solutions can be used as a search heuristic. We have termed this second technique probing.

17.5.1  Reduced Costs

The reduced cost of a variable is a safe estimate of how much the optimum will be changed by changing the value of that variable. For example when minimising, suppose a variable V takes a value of Val at the minimum Min found by the linear solver, and its reduced cost is RC. Then if the value of V was fixed to NewVal the following holds of the new minimum NewMin: NewMin-Min ≥ NewVal-Val × RC. Thus if the value of RC is −3.0 and the value of V is decreased by an amount Diff, then the minimum increases by at least 3.0 × Diff.

⊗
The definition of the reduce cost here is the one used by the eplex library. Be aware that in the literature, the reduced cost can be defined in at least two other ways: that it is a safe estimate of: 1) how much the optimal will be changed by reducing the value of the variable; 2) how much the optimal will be worsened by changing the value of the variable. The sign of the reduced cost in these various definitions can be different depending on if you are maximising or minimising, and the direction you are moving the value in.

Note that the reduced cost is not necessarily a good estimate: it is often just 0.0 which gives no information about the effect of changing the variable’s value.

Reduced cost pruning is a way of tightening the domains of variable in case we already have a worst case bound on the optimum (such as the previous best value, during a branch and bound search). The approach is described in [8].

This reasoning allows the eplex solver to integrate tightly with the ic solver because both solvers wake each other and communicate by tightening domains. In fact the eplex solver is performing domain propagation, just like any ic constraint.

Let us impose reduced cost pruning for a list of variables Vars. The variable being optimised is Opt. 

rc_prune_all(Vars,min,Opt) :-
        % get the current minimum value
        eplex_get(cost,Curr),
        (
	    foreach(Var,Vars), 
            param(Curr,Opt)
        do
	    % apply reduced cost pruning to each variable
            rc_prune(Var,min,Curr,Opt)
        ).

First we extract the current optimum Curr, and then we apply reduced cost pruning to each variable in the list. This is achieved as follows: 

rc_prune(Num,_,_,_) :- nonvar(Num), !.
rc_prune(Var,min,Curr,Opt) :-
      eplex_var_get(Var,reduced_cost,RC),
      ( RC =:=0.0 ->
	  true 
      ;
          % if the variable is still uninstantiated and has a
          % non-zero reduced cost restrict its domain
          eplex_var_get(Var,solution,Val),
          ic: ((Var-Val)*RC+Curr $=< Opt)   % cons5
      ).

If the variable is already instantiated, then no pruning takes place. If the reduced cost is zero, then again no pruning takes place. Otherwise the variable is constrained by cons5, which prevents it from changing so far that the optimum Opt exceeds its upper bound. For maximisation problems a different constraint would be imposed.

To use reduced costs it is necessary to switch on reduced cost recording during the solver setup. Reduced cost pruning can then be implemented as a post goal. This is a goal that is executed immediately after each waking of the linear solver.

Here is a toy program employing reduced cost pruning: 

test(X,Y,Z,Opt) :-
        % set up variable bounds
        ic: ([X,Y,Z]::1..10),
        ic: (Opt:: -1.0Inf..1.0Inf),
        % setup constraints
        eplex: (5*X+2*Y+  Z $>= 10),
        eplex: (3*X+4*Y+5*Z $>= 12),
        % setup the linear solver with reduced cost recording enabled
        % and a post goal to perform reduced cost pruning
        eplex:eplex_solver_setup(
                                 min(X+Y+Z),
                                 Opt,
                                 [sync_bounds(yes),reduced_cost(yes)],
                                 [new_constraint,inst,
                                  post(rc_prune_all([X,Y,Z],min,Opt))]
                                ),
        % label the variables
        labeling([X,Y,Z]).

(Note that a more precise and robust implementation of reduced cost pruning is available as an ECLiPSe predicate reduced_cost_pruning/2 available in the eplex library.)

17.5.2  Probing

Probing is a method which, during search, posts more and more constraints to the linear solver until the linear constraints are logically tighter than the original problem constraints. This is always possible in theory, since any solution can be precisely captured as a set of linear constraints, viz: X1 = val1 , X2 = val2 , …, Xn = valn

The idea is to take the solution produced by the linear solver (which only enforces the linear constraints of the problem), and to extend this solution to a “tentative” assignment of values to all the problem variables. If all the constraints are satisfied by the tentative assignments, then a solution has been found. Otherwise a violated constraint is selected, and a new linear constraint is posted that precludes this violation. The linear solver then wakes and generates a new solution.

If the set of constraints become unsatisfiable, the system backtracks to the choice of a linear constraint to fix a violated constraint. A different linear constraint is added to preclude the violation and the search continues.

Probing is complete and terminating if each problem constraint is equivalent to a finite disjunction of finite conjunctions of linear constraints. The conjunction must be finite to ensure each branch of the search tree is finite, and the disjunction must be finite to ensure that there are only finitely many different branches at each node of the search tree.

17.5.3  Probing for Scheduling

Probing can be applied to resource-constrained scheduling problems, and there is an ECLiPSe library called probing_for_scheduling supporting this. The method is described in detail in the paper [7]. In the following we briefly discuss the implementation of probing for scheduling.

The problem involves tasks with durations, start times and resources. Any set of linear constraints may be imposed on the task start times and durations. Assuming each task uses a single resource, and that there is a limited number MaxR of resources, the resource constraints state that only MaxR tasks can be in progress simultaneously.

The resource limit can be expressed by the same overlap constraints used in the first example above. All the constraints can therefore be handled by eplex alone. However the probing algorithm does not send the resource constraints to eplex. Instead it takes the start times returned from the optimal eplex solution, and computes the associated resource profile. The resource bottleneck is the set of tasks running at the time the profile is at its highest.

The probing algorithm selects two tasks at the bottleneck and constrains them not to overlap, by posting a before constraint (defined in the example above) between one task and the start time of another.

The resource constraint is indeed expressible as a finite disjunction of finite conjunctions of before constraints, and so the algorithm is complete and terminating.

The computation of the resource profile is performed automatically by encoding the overlap constraints in the repair library, annotating them as described in chapter 13.

To make this work, the solutions returned from the linear solver are copied to the tentative values of the variables. This is achieved using a post goal as follows: 

eplex_to_tent(Expr,Opt) :-
    eplex_solver_setup(
                       Expr,
                       Opt,
                       [sync_bounds(yes),solution(yes)],
                       [ new_constraint,post(set_ans_to_tent) ] 
                          ).

set_ans_to_tent :-
    eplex_get(vars,Vars),
    eplex_get(typed_solution,Solution),
    Vars tent_set Solution.

When conflicts are detected by the repair library further constraints repairing the violation are posted to the eplex solver, causing problem resolution and possibly further conflicts to be repaired.

Three kinds of information can be used
  • Reduced Costs
  • The solution (the value for each variable at the linear optimum)
  • Dual values
Reduced costs allow values to be pruned from variable domains. The solution can be checked for feasibility against the remaining constraints, and even if infeasible can be used to support search heuristics. Dual values are used in other hybridisation forms, devised by the mathematical programming community.
Figure 17.4: Using information returned from the linear optimum
Previous Up Next