The black-box interface binds both the objective value (Cost) and the problem variables by bindings these variables. On the other hand, eplex_solve/1 binds the objective value, but does not bind the problem variables. These values can be obtained by:
Retrieve information about the solver state associated with the eplex instance for the variable Var. If What is solution or typed_solution, then the value assigned to this variable by the solver state to obtain the optimal solution is returned in Value. solution returns the value as a float, and typed_solution returns the value as either a float or a rounded integer, depending on if the variable was constrained to an integer in the eplex problem.
Retrieve information about solver state associated with the eplex instance. This returns information such as the problem type, the constraints for the eplex problem. See the reference manual for more details.
So for the simple MIP example:
:- lib(eplex).
:- eplex_instance(my_instance).
mip_example2([X,Y], Cost) :-
my_instance: (X+Y $>= 3),
my_instance: (X-Y $= 0),
my_instance: integers([X]),
my_instance: eplex_solver_setup(min(X)),
my_instance: eplex_solve(Cost),
my_instance: eplex_var_get(X, typed_solution, X),
my_instance: eplex_var_get(Y, typed_solution, Y).
....
[eclipse 2]: mip_example2([X,Y],C).
X = 2
Y = 2.0
C = 2.0
In the example, only X is returned as an integer, as Y was not explicitly constrained to be an integer.
Note that if there are multiple eplex instances, and a variable is shared between the instances, then the solver state for each instance can have a different optimal value to the variable.
So far, we have shown the use of eplex_instance/1 as a directive to declare an eplex instance. For some applications, it might be necessary to create eplex instances dynamically at run-time. The can be done by calling eplex_instance/1 at run-time. In this case, the instance name should not be used to module-qualify any predicates in the code, since this will raise a compiler warning complaining about an unknown module.
new_pool(X,Y) :- % INCORRECT
eplex_instance(pool),
pool: (X $>= Y), % will generate a warning
...
Of course, in the above code, the instance name pool is already known at compile time, so it can always be declared by a directive.
If the name is truly generated dynamically, this can be done as follows:
new_pool(Pool,X,Y) :-
eplex_instance(Pool),
Pool: (X $>= Y),
....
The external solver does not always return the optimal objective value, for example when the optimisation was aborted. However, even when the solver returns an optimal solution, it may actually not be the exact optimal, because of solver settings (e.g. for MIP problems, the MIP search will terminate when the solution found is within certain tolerance of the best possible solution value). In these cases, it may be useful to obtain some bounds on the optimal objective value. The best and worst bounds on the optimal objective can be obtained using the best_bound and worst_bound options of eplex_get/2, respectively.
To implement hybrid algorithms where a run of a simplex/MIP solver is only a part of the global solving process, the black-box model presented above is not appropriate anymore. With eplex instances, we can call eplex_solve/1 repeatedly to re-solve the problem, perhaps after adding more constraints to the problem or after changes in the variable bounds. However, the solver must be invoked explicitly. We require more sophisticated methods of invoking the solver. This can be done by setting up a solver demon, and specifying the conditions in which the demon is to wake up and invoke the external solver.
This is a more sophisticated set up for a new solver state than eplex_solver_setup/1 (in fact eplex_solver_setup/1 is a special case of eplex_solver_setup/4). The main idea is that a list of trigger conditions are specified in TriggerModes, and along with setting up the solver state, a demon goal is created which is woken up when one of the specified trigger condition is met. This demon goal will then invoke the solver, with any constraints posted to the eplex instance since the solver was last invoked taken into account, to re-solve the problem.
The ListOfOptions is a list of solver options for setting up the solver state. Some of these affect the way the external solver solves the problem, such as if presolve should be applied before solving the problem. See the reference manual for eplex_solver_setup/4 for details on the available options and trigger modes.
As the solver is designed to be invoked repeatedly, it is inappropriate to directly bind Cost to the objective value. Instead, the objective value is exported as a bound to Cost: For a minimisation problem, each solution’s cost becomes a lower bound, for maximisation an upper bound on Cost. This technique allows for repeated re-solving with reduced variable bounds or added constraints. Note that the bound update is done only if the solution is optimal. Note also that Cost is not automatically made a problem variable, and thus may not have bounds associated with in. In order for the bounds information not to be lost, some bounds should be given to Cost (e.g. making it a problem variable (but this might introduce unnecessarily self-waking on bounds change), or via another solver with bounds (e.g. ic)).
Note that when a solver demon runs frequently on relatively small problems, it can be important for efficiency to switch the external solver’s presolving off for this demon as part of the ListOfOptions during the setup of the problem to reduce overheads.
The simplest case of having a simplex solver automatically cooperating with a CLP program, is to set up a solver demon which will repeatedly check whether the continuous relaxation of a set of constraints is still feasible. The code could look as follows (we use the eplex instance in this example):
simplex :-
eplex:eplex_solver_setup(min(0), C,
[solution(no)], [bounds]).
First, the constraints are normalised and checked for linearity. Then a solver with a dummy objective function is set up. The option solution(no) indicates that we are not interested in solution values. Then we start a solver demon which will re-examine the problem whenever a change of variable bounds occurs. The demon can be regarded as a compound constraint implementing the conjunction of the individual constraints. It is able to detect some infeasibilities that for instance could not be detected by a finite domains solver, e.g.
[eclipse 2]: eplex:(X+Y+Z >= K), eplex:(X+Y+Z =< 1),
eplex:eplex_solver_setup(min(0), C,
[solution(no)], [bounds]),
K = 2.
No (0.00s cpu)
In the example, the initial simplex is successful, but instantiating K wakes the demon again, and the simplex fails this time.
A further step is to take advantage of the cost bound that the simplex procedure provides. To do this, we need to give the objective The setup is similar to above, but we accept an objective function and add a cost variable. The bounds of the cost variable will be updated whenever a simplex invocation finds a better cost bound on the problem. In the example below, an upper bound for the cost of 1.5 is found initially:
[eclipse 5]: ic: (Cost $:: -1.0Inf..1.0Inf),
eplex:(X+Y $=< 1), eplex:(Y+Z $=< 1), eplex:(X+Z $=< 1),
eplex:eplex_solver_setup(max(X+Y+Z), Cost,
[solution(no)], [bounds]).
X = X{-1e+20 .. 1e+20}
Y = Y{-1e+20 .. 1e+20}
Z = Z{-1e+20 .. 1e+20}
Cost = Cost{-1.0Inf .. 1.500001}
Delayed goals:
lp_demon(prob(...), ...)
Yes (0.00s cpu)
(Note that the ranges for X, Y and Z is -1e+20 .. 1e+20 as 1e+20 is this external solver’s notion of infinity).
If the variable bounds change subsequently, the solver will be re-triggered, improving the cost bound to 1.3:
[eclipse 6]: ic: (Cost $:: -1.0Inf..1.0Inf),
eplex:(X+Y $=< 1), eplex:(Y+Z $=< 1), eplex:(X+Z $=< 1),
eplex:eplex_solver_setup(max(X+Y+Z), Cost,
[solution(no)], [bounds]),
eplex:(Y =< 0.3).
X = X{-1e+20 .. 1e+20}
Z = Z{-1e+20 .. 1e+20}
Cost = Cost{-1.0Inf .. 1.300001}
Y = Y{-1e+20 .. 0.3}
Delayed goals:
lp_demon(prob(...), ...)
Yes (0.00s cpu)
A further example is the implementation of a MIP-style branch-and-bound procedure. Source code is provided in the library file mip.pl.
The external mathematical programming solvers often provides the facility for the user to change the problem being solved. This includes the addition or removal of constraints, and the changing of the objective function. We have already seen how extra constraints can be added. As ECLiPSe is a logic programming language, removal of constraints is automatically achieved by backtracking. We do not allow the user to explicitly remove constraints that have been collected by the external solver, as this makes the problem non-monotonic. For the same reason, we do not allow the objective function to be changed.1 However, we do allow the problem (including the objective function) to be temporarily changed in certain specified ways. This allows the problem to be ‘probed’ with these changes:
Similar to eplex_solve/1, but the problem is first temporarily modified as specified in Probes before the optimisation. The Cost value is instantiated to the objective value for this new modified problem, and any solution state requested are also updated.
Destroy the specified solver, free all memory, etc. Note that ECLiPSe will normally do the cleanup automatically, for instance when execution fails across the solver setup, or when a solver handle gets garbage collected. The solver is disassociated with the eplex instance, and any outstanding constraints not yet collected by the solver are removed, with a warning to the user. In effect, the eplex instance is reinitialised.
Note that this is a non-logical operation. Backtracking into code before eplex_cleanup/0 will not restore the solver state, and any attempt to reuse the solver state will not be possible (the execution will abort with an error). Normally, it is recommended to let ECLiPSe perform the cleanup automatically, for instance when execution fails across the solver setup, or when an unused solver state handle gets garbage collected. However, calling eplex_cleanup/0 may cause resources (memory and licence) to be freed earlier.
A black-box setup-and-solve predicate optimize/2 can be defined as:
optimize(OptExpr, ObjVal) :-
eplex:eplex_solver_setup(OptExpr),
eplex:eplex_solve(ObjVal),
eplex:eplex_get(vars, VArr),
eplex:eplex_get(typed_solution, SolutionVector),
VArr = SolutionVector, % do the bindings
eplex:eplex_cleanup.
A solver state is set up for the eplex instance eplex, to allow constraints that were previously posted to eplex to be collected. This happens once the solver is invoked by eplex_solve/1. If there is a solution, the solution vector is obtained, and the variables are instantiated to those solutions.