Previous Up Next

16.3  Modelling MP problems in ECLiPSe

16.3.1  Eplex instance

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



16.3.2  Example modelling of an MP problem in ECLiPSe

The following code models (and solves) the transportation problem of Figure 16.2, using an eplex instance:


:- lib(eplex).

:- eplex_instance(prob).  % a. declare an eplex instance

main1(Cost, Vars) :-
        % b. create the problem variables and set their range
        Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], 
        prob: (Vars $:: 0.0..1.0Inf),

        % c. post the constraints for the problem to the eplex instance
        prob: (A1 + A2 + A3 $= 21),
        prob: (B1 + B2 + B3 $= 40),
        prob: (C1 + C2 + C3 $= 34),
        prob: (D1 + D2 + D3 $= 10),

        prob: (A1 + B1 + C1 + D1 $=< 50),
        prob: (A2 + B2 + C2 + D2 $=< 30),
        prob: (A3 + B3 + C3 + D3 $=< 40),

        % d. set up the external solver with the objective function
        prob: eplex_solver_setup(min(
                10*A1 + 7*A2 + 200*A3 + 
                 8*B1 + 5*B2 + 10*B3 +
                 5*C1 + 5*C2 +  8*C3 + 
                 9*D1 + 3*D2 +  7*D3)),

        %——————————- End of Modelling code

        prob: eplex_solve(Cost).  % e. Solve problem using external solver


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.
The default bounds for variables is -1.0Inf..1.0Inf. Bounds posted to an eplex instance are specific to that eplex instance.

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.
The arithmetic constraints can be linear expressions on both sides. The restriction to linear expressions originates from the external solver.

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.


16.3.3  Getting more solution information from the solver

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:


main2(Cost, Vars) :-
        ....  % same as previous example up to line e
        prob: eplex_solve(Cost),  % e. Solve problem using external solver
        (foreach(V, Vars) do
            % f. set the problem variables to their solution values
            prob: eplex_var_get(V, typed_solution, V) 
        ).

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.

16.3.4  Adding integrality constraints

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:


:- lib(eplex).

:- eplex_instance(prob).  

main3(Cost, Vars) :-
        Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], 
        prob: (Vars $:: 0.0..1.0Inf),
        prob: (A1 + A2 + A3 $= 21),
        prob: (B1 + B2 + B3 $= 40),
        prob: (C1 + C2 + C3 $= 34),
        prob: (D1 + D2 + D3 $= 10),

        prob: (A1 + B1 + C1 + D1 $=< 50),
        prob: (A2 + B2 + C2 + D2 $=< 30),
        prob: (A3 + B3 + C3 + D3 $=< 40),

        prob: eplex_solver_setup(min(
                10*A1 + 7*A2 + 200*A3 + 
                 8*B1 + 5*B2 + 10*B3 +
                 5*C1 + 5*C2 +  8*C3 + 
                 9*D1 + 3*D2 +  7*D3)),

        prob: (A1 $= A2), % g. the new constraint, added after setup

        %——————————- End of Modelling code

        prob: eplex_solve(Cost),  
        (foreach(V, Vars) do
            prob: eplex_var_get(V, typed_solution, V) 
        ).

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:


main4(Cost, Vars) :-
        Vars = [A1,A2,A3,B1,B2,B3,C1,C2,C3,D1,D2,D3], 
        prob: (Vars $:: 0.0..1.0Inf),
        prob: integers(Vars),  % h. impose the integrality constraint
        ....% Rest is the same as main3

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.
In fact, with the integer constraints, the problem is solved as a MIP problem rather than an LP problem, which involves different (and generally computationally more expensive) techniques. This difference is hidden from the eplex user.

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.
Posting an integers/1 constraint to an eplex instance only inform the external solver to treat those variables as integers (in fact the external solver will still represent the variables as floats, but will only assign intergral solution values to them), but does not constrain the variable itself to be of type integer.


  • 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




Previous Up Next