Previous Up Next

10.2  Eplex Instances

In this chapter, the problem passed to the external solver will be referred to as an eplex problem. An eplex problem consists of a set of linear arithmetic constraints, whose variables have bounds and may possibly have integrality constraints. The external solver will solve such a problem by optimising these constraints with respect to an objective function.

With the eplex library, it is possible to have more than one eplex problem within one program. The simplest way to write such programs with the library is through Eplex Instances. An eplex instance is an instance of the eplex solver, to which an eplex problem can be sent. An external solver state can be associated with each eplex instance, which can be invoked to solve the eplex problem. Declaratively, an eplex instance can be seen as a compound constraint consisting of all the variables, their bounds, and constraints of the eplex problem.

Like other solvers, each eplex instance has its own module. To use an eplex instance, it must first be declared, so that the module can be created. This is done by:

eplex_instance(+Name)

This predicate will initialise an eplex instance Name. Once initialised, a Name module will exist, to which the user can post the constraints for the eplex problem and setup and use the external solver state to solve the eplex problem. Normally, this predicate should be issued as a directive in the user’s program, so that the program code can refer to the instance directly in their code. For example:

   :- eplex_instance(instance).

For convenience, the eplex library declares eplex as an eplex instance when the library is loaded.

10.2.1  Linear Constraints

The constraints provided are equalities and inequalities over linear expressions. Their operational behaviour is as follows:

As with all predicates defined for an eplex instance, these constraints should be module-qualified with the name of the eplex instance. In the following they are shown qualified with the eplex instance, and with brackets around the constraints when needed. Other instances can be used if they have been declared using eplex_instance/1.

EplexInstance: (X $= Y)

X is equal to Y. X and Y are linear expressions.

EplexInstance: (X $>= Y)

X is greater or equal to Y. X and Y are linear expressions.

EplexInstance: (X $=< Y)

X is less or equal to Y. X and Y are linear expressions.

10.2.2  Linear Expressions

The following arithmetic expression can be used inside the constraints:

X
Variables. If X is not yet a problem variable, it is turned into one via an implicit declaration X $:: -1.0Inf..1.0Inf.
123, 3.4
Integer or floating point constants.
+Expr
Identity.
-Expr
Sign change.
E1+E2
Addition.
sum(ListOfExpr)
Equivalent to the sum of all list elements.
E1-E2
Subtraction.
E1*E2
Multiplication.
sum(ListOfExpr1*ListOfExpr2)
Scalar product: The sum of the products of the corresponding elements in the two lists. The lists must be of equal length.

10.2.3  Bounds

Bounds for variables can be given to an eplex instance via the $::/2 constraint:

EplexIntance: Vars $:: Lo..Hi
Restrict the external solver to assign solution values for the eplex problem within the bounds specified by Lo..Hi. Passes to the external solver the bounds for the variables in Vars. Lo, Hi are the lower and upper bounds, respectively. Note that the bounds are only passed to the external solver if they would narrow the current bounds, and failure will occur if the resulting interval is empty. Note also that the external solver does not do any bound propagation and will thus not change the bounds on its own. The default bounds for variables are notionally -1.0Inf..1.0Inf (where infinity is actually defined as the solver’s notion of infinity).

10.2.4  Integrality

The difference between using an LP vs. an MIP solver is made by declaring integrality to the solver via the integers/1 constraint:

EplexInstance:integers(Vars)
Inform the external solver to treat the variables Vars as integral. It does not impose the integer type on Vars. However, when a typed_solution is retrieved (via lp_get/3 or lp_var_get/3), this will be rounded to the nearest integer.

Note that unless eplex:integers/1 (or lp_add/3, see section 10.4.2) is invoked, any invocation of the eplex external solver (via lp_solve/2, lp_probe/3 or lp_demon_setup/5) will only solve a continuous relaxation, even when problem variables have been declared as integers in other solvers (e.g. ic).

Note that all the above constraints are local to the eplex instance; they do not place any restrictions on the variables for other eplex instances or solvers. Failure will occur only when inconsistency is detected within the same eplex instance, unless the user explicitly try to merge the constraints from different solvers/eplex instance.

A counterpart, reals/1 ‘constraint’ also exists – this simply declares the variables specified are problem variables, and does not actually place any other constraint on the variables.

10.2.5  Solving Simple Eplex Problems

In order to solve an eplex problem, the eplex instance must be set up for an external solver state. The solver state can then be invoked to solve the problem. The simplest way to do this is to use:

EplexInstance:eplex_solver_setup(+Objective)
This predicate creates a new external solver state and associates it with the eplex instance. Any arithmetic, integrality and bound constraints posted for this eplex instance are collected to create the external solver state. After this, the solver state can be invoked to solve the eplex problem.

Objective is either min(Expr) or max(Expr) where Expr is a linear expression (or quadratic, if supported by the external solver).

EplexInstance:eplex_solve(-Cost)
Explicitly invokes the external solver state. Any new constraints posted are taken into account. If the external solver can find an optimal solution to the eplex problem, then the predicate succeeds and Cost is instantiated to the optimal value. If the problem is infeasible (has no solution), then the predicate fails (by default). If the problem is unbounded (Cost is not bounded by the constraints), then the predicate succeeds without producing any solution values for the variables.

10.2.6  Examples

Here is a simple linear program, handled by the predefined eplex instance ’eplex’:

:- lib(eplex).

lp_example(Cost) :-
     eplex: eplex_solver_setup(min(X)),
     eplex: (X+Y $>= 3),
     eplex: (X-Y $= 0),
     eplex: eplex_solve(Cost).

The same example using a user-defined eplex instance:

:- lib(eplex).
:- eplex_instance(my_instance).

lp_example(Cost) :-
     my_instance: eplex_solver_setup(min(X)),
     my_instance: (X+Y $>= 3),
     my_instance: (X-Y $= 0),
     my_instance: eplex_solve(Cost).

Running the program gives the optimal value for Cost:

[eclipse 2]: lp_example(Cost).

Cost = 1.5

Note that if the eplex eplex instance is used instead of my_instance, then the eplex_instance/1 declaration is not necessary.

By declaring one variable as integer, we obtain a Mixed Integer Problem:

:- lib(eplex).
:- eplex_instance(my_instance).

mip_example(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).

....
[eclipse 2]: mip_example(Cost).

Cost = 2.0

The cost is now higher because X is constrained to be an integer. Note also that in this example, we posted the constraints before setting up the external solver, whereas in the previous example we set up the solver first. The solver set up and constraint posting can be done in any order. If integers/1 constraints are only posted after problem setup, the problem will be automatically converted from an LP to a MIP problem.

This section has introduced the most basic ways to use the eplex library. We will discuss more advanced methods of using the eplex instances in section 10.3.


Previous Up Next