Previous Up Next

9.4  Low-Level Solver Interface

For many applications, the facilities presented so far should be appropriate for using Simplex/MIP through ECLiPSe. However, sometimes it may be more convenient or efficient to directly access the solver state instead of going through the abstraction of the eplex instances. This section describes lower level operations like how to set up solvers manually. In fact, these lower level predicates are used to implement the predicates provided with eplex instances.

These predicates accesses the external solver state via a handle, which is returned when the solver state is set up, and subsequently used to access a particular solver state by the other predicates. The handle should be treated as a opaque data structure that is used by the eplex library to refer to a particular solver state.

9.4.1  Setting Up a Solver State

lp_demon_setup(+Objective, -Cost, +ListOfOptions, +TriggerModes, -Handle)

This is used to set up a demon solver, and eplex_solver_setup/4 calls this predicate. There is one extra argument compared to eplex_solver_setup/4: the solver state handle Handle, which is returned by this predicate when the new solver state is created. The other arguments are the same as in eplex_solver_setup/4, except that there is an additional option in ListOfOptions: collect_from/1. This is used to specify which, if any, eplex instance the solver state should be collecting constraints from. If an eplex instance is specified (as pool(Instance)), then the solver state is associated with that instance. If the eplex instance is not to be associated with an eplex instance, none should be given as the argument to collect_from. This allows a solver state to be set up without the overhead of an eplex instance. The solver state will not collect any constraints automatically when it is invoked; instead the constraints must be added explicitly via the handle (using lp_add_constraints/3).

By default, the external solver is invoked once after set up by lp_demon_setup, if any TriggerModes is specified. Otherwise, the solver is not invoked and the predicate returns after set up.

lp_setup(+NormConstraints, +Objective, +ListOfOptions, -Handle)

This is an even lower-level primitive, setting up a solver state without any automatic triggering. It creates a new solver state for the set of constraints NormConstraints (see below for how to obtain a set of normalised constraints). Apart from the explicitly listed constraints, the variable's ranges will be taken into account as the variable bounds for the simplex algorithm. Undeclared variables are implicitly declared as reals/1.

However, when variables have been declared integers in other solvers (e.g. using ic:integers/1), that is not taken into account by the solver by default. This means that the solver will only work on the relaxed problem (ie. ignoring the integrality constraints), unless specified otherwise in the options. Objective is either min(Expr) or max(Expr) where Expr is a linear (or quadratic) expression. ListOfOptions is a list of solver options, the same as for lp_demon_setup/5 and eplex_solver_setup/4, except for the collect_from and initial_solve options, which are specific for the demon solvers.

9.4.2  Adding Constraints to a Solver State

Constraints can be added directly to a solver state without posting them to an eplex instance. This is done by:

lp_add_constraints(+Handle, +Constraints, +NewIntegers)

Add new constraints (with possibly new variables) to the solver state represented by Handle The new constraints will be taken into account the next time the solver is run. The constraints will be removed on backtracking.

The constraints are first normalised, and simple constraints filtered out (as discussed in section 9.2.1) before they are added to the external solver (by calling lp_add/3 described below).

lp_add(+Handle, +NewNormConstraints, +NewIntegers)

This adds the constraints (both linear and integrality) to the external solver represented by Handle. The linear arithmetic constraints must be normalised. Note that it is possible to add trivial constraints, which would be filtered out by the higher level lp_add_constraints/3 using this predicate. Integrality constraints on non-problem variables are filtered out and a warning given.

lp_add_vars(+Handle, +Vars)

This adds the variables in Vars to the external solver state represented by Handle. The variables should not contain variables which are already problem variables. The variables are given the default bounds of -infinity..infinity.

lp_var_set_bounds(+Handle, +Var, ++Lo,++Hi)

This updates the bounds for the problem variable Var in the external solver state represented by Handle. Failure occurs if Var is not a problem variable.

9.4.3  Running a Solver State Explicitly

lp_solve(+Handle, -Cost)

Apply the external solver's LP or MIP solver to the problem represented by Handle. Precisely which method is used depends on the options given to lp_setup/4. lp_solve/2 fails (by default) if there is no solution or succeeds if an optimal solution is found, returning the solution's cost in Cost (unlike with lp_demon_setup/6, Cost gets instantiated to a number). After a success, various solution and status information can be retrieved using lp_get/3 and lp_var_get/4.

The set of constraints considered by the solver is the one given when the solver was created plus any new constraints that were added (e.g by lp_add_constraints/3) in the meantime.

If there was an error condition, or limits were exceeded, lp_solve/2 raises an event. See section 9.9 for details.

lp_probe(+Handle, +Probes, -Cost)

Similar to lp_solve/2, but optimize for a modified problem as specified by Probes. This is the predicate called by eplex_probe/2

9.4.4  Accessing the Solver State

In section 9.3.1, we discussed how solver state information can be accessed via the eplex instance. Here are the lower level predicates that directly access this information via the solver state's handle:

lp_get(+Handle, +What, -Value)

Retrieve information about solver state and results. See the reference manual description of lp_get/3 for a detailed description of the available values for What.

For example, it is possible to obtain the solution values from the last successful invocation of the external solver using the following:
    instantiate_solution(Handle) :-
        lp_get(Handle, vars, Vars),
        lp_get(Handle, typed_solution, Values),
        Vars = Values.
    

lp_var_get(+Handle,+Var, +What, -Value)

Retrieve information about solver state represented by Handle, related to a specific variable Var. Again, see the reference manual for the available parameters.

lp_var_get_bounds(+Handle, +Var, -Lo, -Hi)

Retrieve the bounds of the problem variable Var from the solver state represented by Handle.

reduced_cost_pruning(+Handle,?GlobalCost)

This predicate implements a technique to prune variable bounds based on a global cost bound and the reduced costs of some solution to a problem relaxation. The assumptions are that there is a global problem whose cost variable is GlobalCost, and that Handle refers to a linear relaxation of this global problem. The pruning potentially affects all variables involved in the relaxed problem.

9.4.5  Expandable Problem and Constraints

We provide low-level primitives to `expand' an eplex problem. Such a problem is considered to have as yet unspecified components in the objective function and posted constraints. These constraints are known as expandable constraints. The as yet unspecified component involve variables that have not yet been added to the problem. When these variables are added, coefficients for the variables can be added to the expandable constraints, as well as the objective function. These primitives are the basis for implementing column generation, and are used by the column generation library, lib(colgen).

These primitives modify an existing eplex problem non-monotonically, and can only be used on problems that are not represented by an eplex instance, and was not setup as a demon solver (i.e. no trigger conditions are specified).

lp_add_constraints(+Handle, +Constraints, +Ints, -Idxs)

This adds expandable constraints Constraints to the solver state represented by Handle. The predicate returns a list of indices for these constraints in Idxs. The indices are used to refer to the constraints when new variables are added to expand the problem.

lp_add_columns(+Handle, +Columns)

This expands the problem by adding new variables (columns) to the solver state represented by Handle. Columns is a list of variable:column-specification pair, where variable is the variable to be added as a new column, and column-specification the specification for the non-zero components of the column, i.e. coefficients for the expandable constraints (referred to using the index obtained from lp_add_constraints/4) and the objective for this variable.

9.4.6  Changing Solver State Settings

In addition to accessing information from the solver state, some options (a subset of those specified during solver set up) can be changed by:

lp_set(+Handle, +What, +Value)

This primitive can be used to change some of the initial options even after setup. Handle refers to an existing solver state. See the reference manual for details.

9.4.7  Destroying a Solver State

lp_cleanup(+Handle)

Destroy the specified solver state, free all memory, etc. If the solver state is associated with an eplex handle, the solver state is disassociated with the eplex instance. However, unlike eplex_cleanup/0, the outstanding constraints not yet collected by the solver is not removed.

As with eplex_cleanup/0, care should be taken before using this non-logical predicate.

9.4.8  Miscellaneous Predicates

lp_read(+File, +Format, -Handle)

Read a problem from a file and setup a solver for it. Format is lp or mps. The result is a handle similar to the one obtained by lp_setup/4.

lp_write(+Handle, +Format, +File)

Write out the problem in the solver state represented by Handle to the file File in format Format.

normalise_cstrs(+Constraints, -NormConstraints, -NonlinConstr)

where Constraints is a list of terms of the form X $= Y, X $>= Y or X $=< Y where X and Y are arithmetic expressions. The linear constraints are returned in normalised form in NormConstraints, the nonlinear ones are returned unchanged in NonlinConstr.


Previous Up Next