eplex_solve/1instantiates its argument, we need to use a new variable for each call:
.... % setup the constraints for the original problem as before prob: (A3 + B3 + C3 + D3 =< 40), prob: eplex_solver_setup(min(....)), % as before prob: eplex_solve(Cost1), % h. solve original problem prob: (A1 $= A2), prob: eplex_solve(Cost2), % i. solve modified problem .....
:- eplex_instance(mip). main5(Cost, Vars) :- % set up variables and constraints, but no integers/1 constraints .... % assume minimise for simplicity mip: eplex_solver_setup(min(Obj)), mip: eplex_solve(RelaxedCost), mip: (Cost $>= RelaxedCost), % RelaxedCost is lower bound
In general, this initial LP solution contains non-integer assignments to integer variables. The objective value of this LP is a lower bound on the actual MIP objective value. The task of the search is to find integer assignments for the integer variables that optimises the objective function. Each node of the search-tree solves the problem with extra bound constraints on these variables. At each node, a particular variable is `labelled' as shown in Figure 16.5. The integer variable in this case has been assigned the non-integer value of 4.2. In the subsequent nodes of the tree, we consider two alternate problems, which creates two branches in the search. In one problem, we impose the bound constraint X ≤ 4, and in the other, X ≥ 5: these are the two nearest integer values to 4.2. In each branch, the problem is solved again as an LP problem with its new bound for the variable:
Figure 16.5: Labelling a variable at a MIP tree node
branching(IntVars) :- .... % for each integer variable X which violates the integer constraint mip: eplex_var_get(X, solution, XVal), ... Split is floor(XVal), % choice: branch on the two ranges for X (mip: (X $=< Split) ; mip: (X $>= Split + 1)), mip: eplex_solve(RelaxedCost), ...% repeat until there are no integer violations
X $=< Split). The program then proceeds to further labelling of the variables. The alternative branch is left to be tried on backtracking.
In the code, the external solver is invoked explicitly at every node. This however may not be necessary as the imposed bound may already be satisfied. As stated at the start of this section, the invocation of the solver could be done in a data-driven way, more like a normal constraint. This is done with
Remember that ECLiPSe provides libraries that make some programming tasks much easier. There is no need to write your own code when you can use what is provided by an ECLiPSe library.
Figure 16.6: Reminder: use ECLiPSe libraries!
eplex_solver_setup(+Obj,-ObjVal,+Options,+Trigs), a more powerful version of
eplex_solver_setup/1for setting up a solver. The
Trigsargument specifies a list of `trigger modes' for triggering the solver.
deviating_boundsin the trigger modes. The full code that implements a MIP solution for the example transportation problem is given below:
:- lib(eplex). :- lib(branch_and_bound). :- eplex_instance(mip). main6(Cost, Vars) :- % b. create the problem variables and set their range Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], mip: (Vars :: 0.0..1.0Inf), % c. post the constraints for the problem to the eplex instance mip: (A1 + A2 + A3 $= 21), mip: (B1 + B2 + B3 $= 40), mip: (C1 + C2 + C3 $= 34), mip: (D1 + D2 + D3 $= 10), mip: (A1 + B1 + C1 + D1 $=< 50), mip: (A2 + B2 + C2 + D2 $=< 30), mip: (A3 + B3 + C3 + D3 $=< 40), mip: (A1 $= A2), % j. post the objective function as a constraint ObjFunc = 10*A1 + 7*A2 + 200*A3 + 8*B1 + 5*B2 + 10*B3 + 5*C1 + 5*C2 + 8*C3 + 9*D1 + 3*D2 + 7*D3, mip: (ObjFunc $= Cost), % k. this is a more flexible method for setting up a solver. % [deviating_bounds] specifies that the external solver should be % invoked when any solution value is outside the variable bounds mip: eplex_solver_setup(min(ObjFunc), Cost, , [deviating_bounds]), % l. Use the branch_and_bound library to do the branch and bound bb_min(( branching(Vars), mip: eplex_get(cost, Cost) (foreach(V, Vars) do mip: eplex_var_get(V,solution,V)) ), Cost, _). branching(IntVars) :- % Find a variable X which does not have an integer solution value (integer_violation(IntVars, X, XVal) -> % m. try the closer integer range first Split is round(XVal), (Split > XVal -> (mip: (X $>= Split) ; mip: (X $=< Split - 1)) ; (mip: (X $=< Split) ; mip: (X $>= Split + 1)) ), branching(IntVars) ; % cannot find any integer violations; found a solution true ). % returns Var with solution value Val which violates the integer constraint integer_violation([X|Xs], Var, Val) :- mip: eplex_var_get(X, solution, RelaxedSol), % m. we are dealing with floats here, so need some `margin' for a % float value to be considered integer (1e-5 on either side) (abs( RelaxedSol - round(RelaxedSol) ) >= 1e-5 -> Var = X, Val = RelaxedSol ; integer_violation(Xs, Var, Val) ).
k, with the use of the
deviating_boundstrigger mode. There are no explicit calls to trigger the solver – it is triggered automatically. In addition, the first call to
eplex_solve/1for an initial solution is also not required, because when trigger modes are specified, then by default,
eplex_solver_setup/4will invoke the solver once the problem is setup.
deviating_boundstrigger condition, the other argument of interest in our use of
eplex_solver_setup/4is the second argument, the objective value of the problem (
Costin the example): recall that this was returned previously by
eplex_solve/1. Unlike in
eplex_solve/1, the variable is not instantiated when the solver returns. Instead, one of the bounds (lower bound in the case of minimise) is updated to the optimal value, reflecting the range the objective value can take, from suboptimal to the `best' value at optimal. The variable is therefore made a problem variable by posting of the objective as a constraint in line
j. This informs the external solver needs to be informed that the
Costvariable is the objective value.
m, the branch choice is created by the posting of the bound constraint, which may trigger the external solver. Here, we use a simple heuristic to decide which of the two branches to try first: the branch with the integer range closer to the relaxed solution value. For example, in the situation of Figure 16.5, the branch with
X $=< 4is tried first since the solution value of 4.2 is closer to 4 than 5.
m, there is no need to explicitly write our own branch-and-bound routine. However, this predicate requires the cost variable to be instantiated, so we call
eplex_get(cost, Cost)to instantiate
Costat the end of each labelling of the variables. We also get the solution values for the variables, so that the branch-and-bound routine will remember it. The final value returned in
Cost(and Vars for the solution values) is the optimal value after the branch-and-bound search, i.e. the optimal value for the MIP problem.
Of course, in practice, we do not write our own MIP solver, but use the MIP solver provided with the external solvers instead. These solvers are highly optimised and tightly coupled to their own LP solvers. The techniques of solving relaxed subproblems described here are however very useful for combining the external solver with other solvers in a hybrid fashion.
- Use Instance:eplex_solver_setup(+Obj,-ObjVal,+Opts,+Trigs) to set up an external solver state for instance Instance. Trigs specifies a list of trigger conditions to automatically trigger the external solver.
- Instance:eplex_var_get(+Var,+What,-Value) can be used to obtain information for the variable Var in the eplex instance.
- Instance:eplex_get(+Item, -Value) can be used to retrieve information about the eplex instance's solver state.
Figure 16.7: More advanced modelling in eplex