The simplest way to model an eplex problem is through an eplex instance. Abstractly, it can be viewed as a solver module that is dedicated to one MP problem. MP constraints can be posted to the instance and the problem solved with respect to an objective function by the external solver.
Declaratively, an eplex instance can be seen as a compound constraint consisting of all the variables and constraints of its eplex problem. Like normal constraints, different eplex instances can share variables, although the individual MP constraints in an eplex instance do not necessarily have to be consistent with those in another.
An eplex instance represents a single MP problem in a module. Constraints for the problem are posted to the module. The problem is solved with respect to an objective function.
Figure 16.3: Eplex Instance
The following code models (and solves) the transportation problem of Figure 16.2, using an eplex instance:
|
To use an eplex instance, it must first be declared with eplex_instance/1.
This is usually done with a directive, as in line a.
Once
declared, an eplex instance can be referred to using its name like a module
qualifier.
We first create the problem
variables and set their range to be non-negative, as is conventional in MP.
Note that the bounds are posted to our eplex instance, using $::/2.
|
Next, we set up the MP constraints for the
problem by posting them to the eplex instance.
The MP constraints accepted by eplex are the arithmetic equalities and
inequalities:
$=/2, $=</2 and $>=/2.
|
We need to setup the external solver with the eplex instance, so
that the problem can be solved by the external solver. This is done by
eplex_solver_setup/1, with the objective
function given as the argument, enclosed by either min(...) or max(...). In this case, we are minimising.
Note that
generally the setup of the solver and the posting of the MP constraints can be
done in any order.
Having set up the problem, we can solve it
by calling eplex_solve/1 in line e.
When an instance gets solved, the external solver takes into account all constraints posted to that instance, the current variable bounds for the problem variables, and the objective specified during setup.
In this case, there is an optimal solution of 710.0:
?- main1(Cost, Vars).
Cost = 710.0
Vars = [A1{0.0 .. 1e+20 @ 0.0}, A2{0.0 .. 1e+20 @ 21.0}, ....]
Note that the problem variables are not
instantiated by the solver. However, the ‘solution’ values, i.e. the
values that the variable are given by the solver, are available in the
eplex attribute. The eplex attribute is shown as Lo..Hi @ Sol where
Lo is the lower bound, Hi the upper bound, and Sol the
solution value for the variable (e.g., A2 has the solution value of
21.0 in the example above). Note also that the external solver may not
allow very large floats, hence 1e+20, this external solver’s
representation of infinity, is the upper bound of the
variables, even though we specified 1.0Inf in our code.
One reason the problem variables are not assigned their solution values is so that the eplex problem can be solved again, after it has been modified. A problem can be modified by the addition of more constraints, and/or changes in the bounds of the problem variables.
The solution values of the problem variables can be obtained by
eplex_var_get/3. The example program in the
previous section can be modified to return the solution values:
|
In line f, eplex_var_get/3 is used to obtain the solution
value for a problem variable. The second argument, set to typed_solution,
specifies that we want the solution value for the variable to be returned.
Here, we instantiate the problem variable itself to the solution value
with the third argument:
?- main2(Cost, Vars). Cost = 710.0 Vars = [0.0, 21.0, 0.0, 16.0, 9.0, 15.0, 34.0, 0.0, 0.0, 0.0, 0.0, 10.0]
Note that, in general, an MP problem can have many optimal solutions, i.e.
different solutions which give the optimal value for the objective function.
As a result, the above
instantiations for Vars might not be what is returned by the solver
used.
In general, a problem variable is not restricted to taking integer
values. However, for some problems, there may be a requirement that some or
all of the variable values be strictly integral (for example, in the previous
transportation problem, it may be that only whole units of the
products can be transported; also variables may often be used to model
booleans by allowing them to take on the values of 0 or 1 only).
This can be specified by
posting an additional integers/1 constraint on the
variables.
Consider the example problem again, where it so happens that the optimal value for the objective function can be satisfied with integral values for the variables. To show the differences that imposing integer constraints might make, we add the constraint that client A must receive an equal amount of products from plants 1 and 2. Now the problem (without the integer constraints) can be written as:
|
In this example, the new constraint in line g is imposed after the
solver setup. In fact it can be imposed anytime before
eplex_solve(Cost) is called.
This problem also has an optimal Cost of 710, the same as the original
problem. However, the solution values are not integral:
?- main3(Cost, Vars). Cost = 710.0 Vars = [10.5, 10.5, 0.0, 5.5, 19.5, 15.0, 34.0, 0.0, 0.0, 0.0, 0.0, 10.0]
Now, to impose the constraints that only whole units of the products can be transported, we modify the program as follows:
|
In line h, we added the integers/1 constraint. This imposes
the integrality constraint on Vars for the eplex instance
prob. Now,
the external solver will only assign integer solution values to the
variables in the list.
|
Running this program, we get:
?- main4(Cost,Vars). Cost = 898.0 Vars = [10, 10, 1, 6, 20, 14, 34, 0, 0, 0, 0, 10]
In this case, A1 and A2 are now integers. In fact, notice
that all the values returned are now integers rather than floats. This is
because the typed_solution option of eplex_var_get/3
returns the solution values taking into account if the variables have been
declared as integers for the eplex instance.
|
- Declare an eplex instance using eplex_instance(+Instance).
- Post the constraints ($=/2, $>=/2, $=</2, integers/1, $::/2) for the problem to the eplex instance.
- Setup the solver with the objective function using
Instance: eplex_solver_setup(+ObjFunc).
Figure 16.4: Modelling an MP Problem