Implementation Notes for lib(eplex),  in ECLiPSe 5.6

Author: Joachim, Kish
Date: July 2003
Revision history: July 2001 (original), May 2002 (modified for 5.4), Dec 2002 (modified for 5.5)
Contents:
 #Global structure
 #Eclipse Code Level
 #C Code Level

Global structure

These notes applies to the original eplex only. From ECLiPSe version 5.6, the standalone version of eplex, which does not require an ECLiPSe bounds keeper (ic or range) to keep the bounds of the variables, was introduced. This is described separately.

Files

Components: Related:

Modules

eplex.pl contains two modules eplex and eplex_. Most of the code is in eplex_ and reexported through eplex. The reason to have eplex_ at all is that eplex redefines the arithmetic predicates (>, >=, ...) which would be inconvenient to have in the actual implementation module.

There are four dummy modules, eplex_cplex and eplex_xpress ,  ic_eplex and range_eplex (defined in the corresponding files). They don't contain anything.  In addition, to avoid the confusion of apparently being able to post arithematic constraints to these module, they only reexport the small subset of eclipse_language built-ins needed by the small amount of code in these modules.The only effect is that eplex.pl loads eplex_with_range.ecl when range_eplex exists, and the ic_with_range.ecl when ic_eplex exists; and simularily, eplex_.ecl attempts to load the Cplex version when the module eplex_cplex exists, and the Xpress version when module eplex_xpress exists. If none of them exists, the loaded solver is solely determined by the eplex_lic_info file.

Debugging

The C code is littered (and made even more unreadable) by macros which can be used to produce a trace of all XPRESS/CPLEX functions that get called. This trace can be turned into a pure C bug report, so that any external solver bugs can be isolated from ECLiPSe.  See section on logging.

Eclipse Code Level

Licences and versions

Quite a bit of code at the beginning of eplex_.ecl deals with finding the right version of the C code to load and obtaining a licence (because the underlying solver is usually licence-protected). We use a little database file that tells the library which solver and version to use on a particular host, and where to find the licence for this solver. The information is held in the file eplex_lic_info.ecl in the Eclipse lib directory. If both Cplex and Xpress are available on a particular host, the selected solver is It is not possible to have two different external solvers in the same Eclipse session.
The pair of predicates lp_get_licence/0 and lp_release_licence/0 obtain or release a licence. lp_get_licence/0 fails if no licence is availble, but it can be called again until one becomes available. On loading, the library tries to grab a licence, and prints a warning if this is not possible.

We also have OEM versions of Xpress that can be used with ECLiPSe which the user can use without obtaining an Xpress license from Dash. This checking is done at the C level (in p_cpx_init()) if the macro XPRESS_OEM_ICPARC_2002 is defined. It is done in C to avoid checking for 32 bit overflow: the formular used by Dash requires 32 bit integers to work correctly, whereas in ECLiPSe, integers > 32 bits will become bignums. Different keys are needed for the different versions of Xpress, and this is hard-coded into the C code via macros.

Attribute

Eplex variables have the following attribute: 
:- export struct(
        eplex(
            solver,     % A solver that this variable occurs in
            idx,        % The column number in that solver's matrix
            intol_inst, % Suspension list to be woken on intolerable
            next        % can point to a different eplex attribute for another
                        % handler, or the atom 'end'

        )
    ).
The eplex attribute  consists of a chain of one or more attribute structures. Each attribute structure belongs to  a specific solver state. Together they represent the eplex problems the particular variable occurs in.

The solver field contains one of the problem handles where the variable occurs, and the corresponding column index idx. This information is mainly needed in lp_var_get/4 to retrieve variable-related information such as the lp solution. This link is the main problem when we consider dealing with multiple solver handles simultaneously.
The intol_inst waking list is only used for a very special purpose, namely waking when the variable gets instantiated to a value that is outside of a certain tolerance from the lp solution. The tolerances can be set by using lp_set/3 on the solver handle and are different for continuous and integer variables.

The next field points to the next attribute structure, or the atom end if there are none.  An atom instead of a variable is used to terminate the chain to avoid potential problems with using setarg (setarg needs to be used as the chain needs to be modified in cases like when an attribute is discarded (see unification of attribute chains below)). Each attribute structure in a chain must refer to a different solver state.  This assumption is made in many of the routines that handle the attribute chains. 

:- meta_attribute(eplex, [
        print:lp_var_print/2,
        unify:unify_eplex/2,
        suspensions:suspensions_eplex/3
    ]).
In general, the attribute handlers have to handle every single attribute structure in the chain. The attribute print handler prints the lp solutions  of all the attribute structures in the chain(using the solver/idx fields in the attribute). The unify handler is responsible for:

Problem Handle

What we call a problem in the following consists of Multiple problems are supported by eplex, each problem having its own handles.We have problem handles on several levels:
  1. Eclipse level: this is an Eclipse structure (struct prob ), its fields are backtracked, the first field refers to the C level descriptor
  2. C level: this is a C structure (struct lp_desc), its fields are non-backtracked, it refers among others to the solver state descriptor
  3. CPLEX/XPRESS level: this is the solver's problem handle (if any) which is a black box for us. We refer to this as the solver state.
The Eclipse handle contains all the information we want to hold on the Eclipse level, for whatever reason (because it it more convenient, because it is logical storage, etc). Among the fields are: 
:- export struct(
        prob(
            cplex_handle,       % int: pointer to C data structure
...
            vars,               % ''(X1,...,Xn): struct of problem variables
            ints,               % [Xi1,...Xik]: list of integer variables
...
            method,             % atom: solving method (primal, dual, ...)
            demon_tol_int,      % float: tolerable deviation of instantiation
            demon_tol_real,     % float:  ... to simplex solution.
...
            presolve,           % 1 for yes, 0 for no
            use_copy,           % 1 for yes, 0 for no
...
            status,             % return status of last successful invocation
            cost,               % float: cost of the current solution
            sols,               % array[n] of raw solutions (or [] or _)
            pis,                % array[m] of dual values (or [] or _)
            slacks,             % array[m] of slacks (or [] or _)
            djs,                % array[n] of reduced costs (or [] or _)
            base                % iarray[n+m] of basis status (or [] or _)
        )
    ).
The vars array keeps a reference to all the variables involved in the problem. The array index corresponds to the column number on the solver level (except that Eclipse array indixes run from 1..N and column number from 0..N-1). The variables that are treated as integers by the solver are stored in an additional list ints. If this list is empty, we only solve LP problems!
The presolve field  specifies the presolve setting for this problem. If the solver supports only global parameter, then this local setting for presolve is simulated at the C-level by changing the parameter whenever it is needed for the problem. In addition, some solvers may have more than a simple binary setting for the presolve, and indeed different parameters for the MIP and LP presolves (Xpress). In this case, the presolve setting maps to all problem types with some default values when presolve is on.
The use_copy field specifies if a copy of the problem at the C-level should be used when a MIP problem is solved. Using a copy allows a MIP problem to be modified when Xpress  is used; as otherwise Xpress does not allow a MIP problem to be modified (beyond changing bounds) once the MIP search has started.
The method and demon_tol fields store control parameters for the solver (others are stored on a lower level).
The remaining group are solver results: status is an integer that contains the underlying solver's last return status (not normally needed by the programmer). cost is the cost of the last solution that was computed.
The subsequent arrays contain the result values belonging to that solution. Note that not all these arrays need to be in use. When they are initialised to free variables, they remain unused. When they are initialised to nil, they will be setarg'd to new arrays after every successful run of the solver. This initialisation is done by the corresponding solver options (in lp_setup/3 or later via lp_set/3):
 

Result option name Default setting Array name in prob
solution yes sols
dual_solution no pis
slack no slacks
reduced_cost no djs
keep_basis no base

Note again that this is logical storage which is properly reset on backtracking, while everything that is stored at the C level is not. Where reset is needed at the C level, explcit "undo functions" needs to be trailed.

Support for column generation

The column generation library uses  the eplex library.  The main support provided by eplex for column generation are:

Support for multiple problems

As disccused under the attribute section, multiple problems are supported in the ECLiPSe level with chains of eplex attributes. A variable can be involved in multiple eplex problems,  each with a different solver state, and each attribute structure within the eplex attribute for the variable represents one solver state.

Each ECLiPSe problem handle is given a unique integer id, the solver id . Each time a solver state is created, it is assigned a new solver id maintained within a global reference, whose value is incremented for the next solver id. The solver id is stored into the solver_id field of the problem handle for the solver state, and is used to identify the solver state within the ECLiPSe code for the library, for example,  in predicates which needs to access a specific eplex attribute structure in a chain.

The concept of eplex instances is used to represent multiple eplex problems at a high-level. This allows constraints for an eplex problem to be posted before a solver state is set up for it.  Note that the eplex attribute structure is not created until the solver state is set up.

Managing solver parameters

With Xpress 13+, the solver parameters are specific to each problem and there are no global parameters. With Cplex and older Xpresses, the parameters are global (i.e. applies to all problems). This difference unfortunately cannot be hidden from the user. An additional complication is that currently a ECLiPSe level problem may not yet have a C-level solver handle (e.g. if the problem was empty). This is an issue if the solver parameters are problem specific.

We allow access (get/set) to these parameters via the problem handle (or eplex instance)[local access], or `globally', without specifying any handle/instance. The exact meaning of `global' parameter depends on if the solver has global parameters or not:

  1. solver has global parameters: acess to global parameters in eplex directly accesses the corresponding solver parameter.
  2. solver has no global parameters: `global' parameters are the default settings for the parameters, i.e. the values that would be given to a new problem when it is set up (at the C level). It does not affect any existing problem's parameter.
Thus, the two cases of the global parameters behaves in the same way only if the parameters are accessed before any problem setup.

The following table shows the value that is returned for various types of accesses. There are three types of access: global access (no handle), local access, no C handle (with a problem handle that does not yet have a low level handle), local access, with C handle (with a problem handle with a low level handle):

access type solver has local params solver has global params
global  default value global value
local, no C handle default value global value
local, with C handle problem's value global value

We plan to remove the complication of wheather there is a C level handle or not by always setting up a low level solver for a problem during problem setup.

We do not allow the user to set a solver parameter locally if the solver has global parameters only, because this would have the `side effect' of changing this parameter globally.

Also, note that the presolve parameter is treated specially. This does not correspond directly to the low level presolve parameter of the solver. Instead it always behaves as if this parameter is local, i.e. it is specific to each problem, and if set globally, it sets the default value. With solvers that only has global parameters, the local behaviour is simulated as discussed  here.

The default values for parameters in Xpress 13+ is stored in a dummy problem which is created on initialisation. The values of these parameters is copied into each new problem that are created.

When used from ECLiPSe, these parameters needed to be wrapped in a optimizer_param/1 structure, to clearly show that they are optimizer (and version) specific. We also provide two special aliases that do not need the optimizer_param/1 wrapping: presolve, as discussed above, and timeout. This allow the user to avoid version specific code for these common cases, and also not needing to worry about the differences in the actual solver parameter (different names, different argument type, different semantics).

Normalised expressions and constraints

All expressions occurring in eplex constraints are turned into normalised linear form using lib(linearize): 
        [C0*1, C1*X1, C2*X2, ...]
where Ci are numbers and Xi are distinct variables. The first (constant) term is always present, Ci (i>=1) are nonzero.
Constraints are normalized by bringing all terms to one side of the relational symbol and then storing just the relational symbol and the non-zero side as a normalised expression: 
        Sense:NormExpr
where Sense is one of the atoms =:=, >= or =< and NormExpr is a normalised expression as above. E.g. 
        (>=):[-5*1,3*X]
could encode the source constraint 
        5 =< X*3
There is also a quadratic normal form being used for quadratic objectives, see lib(linearize) for details.

Eplex instances

For ease of programming multiple eplex problems, the abstraction of eplex instances is introduced. Conceptually, an eplex instance is an instance of the eplex solver for one eplex problem.   Each eplex instance is a module, and from a user's point of view, it works like any other solver module: predicates are defined in the module which allows the user to post linear arithmetic and intergrality constraints, and to set up and invoke an external solver to solve the problem. There are three components:
  1. storage for constraints
  2. predicates to set up and trigger solver state
  3. associated external solver state (if one has been setup)

Storage for constraints

This is implemented using lib(constraint_pools). The posted constraints are buffered on the ECLiPSe level in constraint pools, one pool per eplex instance.

When an eplex instance is declared using eplex_instance/1, an eplex instance is either created (if it does not already exist) or checked to see if it is empty (no posted constraints in the constraint pool, no associated solver). An eplex instance is created by creating the constraint pool for it.

The constraints are divided into two types, defined in the structure constraint_type in eplex_.ecl:

:- local struct(constraint_type(integers,linear)).

integers are the intergrality constraints (integers/1), and linear are the linear arithmetic constraints (=:=/2, >=/2, =</2).

When a linear constraint is posted, the following happens:

   1. the constraint gets normalised
   2. if ground, solve it now, i.e. check if satisfied
   3. if it has only one variable, turn it into a (range- or ic-) bound update
   4. otherwise, add the normalised form to the linear constraint type of the constraint pool.

integers/1 is handled by

  1. imposing ic:integers/1 or range:integers/1 on the variables
  2. eliminating ground integers from the list
  3. add the remaining variables to the integers constraint type of the constraint pool. For efficiency, when the integers list is traversed to eliminate ground integers, a unbounded tail is created to allow the existing integers to be added to this tail
Thus the constraints are not actually maintained as suspensions, but logically they are still part of the resolvent. Any constraints that remain in any of the eplex instances' constraint pools are thus printed out at the end of an execution. This is done by calling set_lp_pending/0 whenever a constraint is added to an eplex instance. set_lp_pending/0 will create an lp_pending/0 suspension if one does not already exist, so the presence of this suspended goal indicates that there are possibly some constraints posted to some eplex instance. A portray macro for lp_pending/0 is defined to print out the outstanding constraints in all the eplex instances, so that when the delay goals are printed at the end of an execution, the eplex constraints would be printed instead of lp_pending/0. Note that constraints collected by an external solver will not be printed, even if the external solver was not invoked to solve the problem.

The suspended lp_pending goal is stored in the global reference lp_info in the module eplex_. lp_info is a structure with two fields:

:- local struct(lp_info(newid,     % int: next handler id
                               pending   % suspension: lp_pending's suspension
     )).

newid is the next solver id.

Predicates for the eplex instance

Predicates defined in the eplex instances simply call their counter-parts in the module eplex_ with the eplex instance name as an argument. All the real work is done by the predicates in the eplex_ module. This is specified in the create_constraint_pool/3 call
when the constraint pool is created.

Except for the constraint predicates, all other predicate names defined for an eplex instance start with eplex_.  The predicates (in the eplex instance) are:
 

constraints:              integers/1, =:=/2, >=/2, =</2
solver setup:            eplex_solver_setup/1, eplex_solver_setup/5
solver invocation:    eplex_solve/1, eplex_probe/2
solver state:             eplex_get/2, eplex_var_get/3
destroy solver:         eplex_cleanup/0
read/write problem:  eplex_read/2, eplex_write/2
In turn, the eplex_* predicates in eplex_.ecl calls the low-level predicate that uses solver state handles. The solver handle is for the solver state that is associated with the particular eplex instance.

Associating external solver state

A new external solver state can be associated with an eplex instance by the solver setup predicates of the eplex instance. The solver state is first created and then associated with the eplex instance.

Associating with an eplex instance is done using the pool item facility of lib(constraint_pools). The ECLiPSe handle for a solver state is stored in the eplex instance's pool item if the eplex instance has an associated solver, otherwise 0 is stored as the pool item.
 

lp_setup

This is really the core of the library. It takes as input
  1. a list of already normalised constraints (equalities and inequalities)
  2. an objective expression (linear or quadratic)
  3. a list of integer variables (within the option list)
  4. a list of solver options
This data is used to set up a linear, quadratic or mixed integer problem with the external solver, and a handle to it is returned. There are a few interdependencies
Pseudocode: 
lp_setup:
    assign a new solver id
    renormalise constraints (possibly do some simplification)
    normalise the objective (and determine whether it's linear)
    create array of problem variables
    create list of integer variables if required
    assign column numbers to the variables and store them in the attributes
    convert constraints into column-wise lists of row:coefficient pairs
    transfer data into the C-level descriptor (including transfer of all variable
        bounds from bounds keeper to solver)
    call the C-level problem setup function cplex_loadprob()
Note that special treatment is needed for extreme cases (no variables, no constraints), because the low-level code cannot cope with degenerate cases.

Each solver state is assigned an unique integer solver id. The next id to assign is maintained in a global reference.

lp_solve

Takes a problem handle and invokes the actual optimizer. Because it can be called repeatedly on the same problem handle, it takes care of first transferring possibly updated variable bounds to the solver,and optionally loading a basis that might have been saved from a previous solver run. It may alsoPseudocode: 
lp_solve:
    setup problem if not already setup
    if not a freshly set up problem:
        transfer current variable bounds to the solver (all or some)
    if a previous basis is available:
        transfer basis to the solver
    invoke the solver
    interpret the result
    if successful:
        retrieve the cost
        retrieve the required result arrays (solutions, basis, etc)
You can see that the updating of variable bounds is not very well optimized: we normally assume that every variable could have changed bounds and traverse the whole variable array and transfer all the current bounds to the solver in case they have changed. Any better strategy would require to monitor variables individually, and it is not clear whether this is worthwhile.
About handling the basis: storing the basis at the logical Eclipse-level is optional. If it is done, then the solver can restart from the basis of the logical ancestor in the search tree. If it is not done, it will just use the basis from the chronologically last solver invocation. The latter is less predicatable, but has less overhead.
Cplex and Xpress can return lots of different result codes. We classify them into the following groups:
 

Result description action default handler
DESCR_SOLVED_SOL an optimal solution was found success success
DESCR_SOLVED_NOSOL no solution was found, infeasible fail fail
DESCR_ABORTED_SOL  a possibly suboptimal solution was found (mip) event(eplex_suboptimal) success
DESCR_ABORTED_NOSOL  no solution was found, but there may be one (mip) event(eplex_abort) abort
DESCR_UNBOUNDED_NOSOL problem unbounded, no solution values event(eplex_unbounded) success
DESCR_UNKNOWN_NOSOL unknown whether infeasible or unbounded event(eplex_unknown) fail

The infeasible or unbounded result can arise from the use of presolving or the dual simplex method (because infeasibility of the dual indicates infeasibility or unboundedness of the primal). The events have been introduced to enable the library user to tailor the behaviour of the solver for the doubtful results.

optimize

Optimize (the black-box solver) is a simple sequence of
  1. collecting the pending constraints (equalities, inequalities and eplex:integers/1)
  2. setting up a solver
  3. run the solver
  4. unifying the resulting cost
  5. retrieving the solutions and unifying them with the variables
  6. cleaning up the solver

lp_demon

For the demon solver, the setup and initial solving is like for the black-box solver. The differerences are that a demon with appropriate waking conditions is set up as well, the Cost variable is only bounded by the solution (rather than unified), and the problem variables are not touched after solving:
  1. collecting the pending constraints (equalities, inequalities and integers/1) from the eplex instance that the demon is associated with (if any), specified by the collect_from option.
  2. setting up a solver
  3. create the lp_demon suspension
  4. insert the suspension into the suspend field of the handle
  5. run the solver once if initial_solve option is yes
  6. calling the post-goal (see user documentation)
  7. bounding the Cost variable
When the lp_demon is woken subsequently, it performs:
  1. collecting new pending constraints (equalities, inequalities and eplex:integers/1) if the solver state is associated with an eplex instance.
  2. adding them to the existing handle
  3. in case new variables have been introduced, let the lp_demon suspend on them as well
  4. calling the pre-goal
  5. run the solver again
  6. calling the post-goal
  7. bounding the Cost variable
Triggering the demon:

Trigger condition Implementation
inst insert in all variable's (inst of suspend) lists
bounds insert in all variable's (wake_lo/wake_hi of range) lists
deviating_inst insert in all variable's (intol_inst of eplex) lists
deviating_bounds like deviating_inst, additionally set up a deviating_bounds_demon on every variable which wakes on bound changes and schedules the intol_inst list when the new bounds exclude the lp-solution
Attribute:Index insert in all variables' suspension list found in attribute Attribute in the index'th position 
new_constraint the nc_trigger field of the solver state's handle is set to yes (it defaults to no). When constraints are added to the solver state (see lp_add below), the nc_trigger filed is checked, and if it is yes, then the demon is triggered (by scheduling the suspension for the demon in the suspension field for the handle)
trigger(atom) attach to a global trigger

lp_add

lp_add add constraints and variables to a previously set up problem handle. The handles on all levels must be adjusted accordingly. In general, the problem type can change from lp to mip (if interger constraints are added to an lp problem). Both linear and integers constraints can be added (if allowed by the problem type).  Currently we do not support the changing of a qp problem to qmip problem.

lp_add can be called in several ways, either explicitly (e.g. via lp_add_constraints), or implicitly (when a demon solver is invoked), with various steps, which are carried out by three predicates:

  1. renormalise_and_check_simple: Renormalise any new linear constraints
  2. lp_add_normalised: Add the new (normalised) constraints/variables to the problem
  3. var_triggers: Add the new variables to the triggers
Not all calls to adding constraints/variables to the problem perform all three steps. For example, adding columns for column generation does not normalise the constraint (because simple constraints has to be added to the problem).

renormalise_and_check_simple

Renormalised and any ground linear constraints (all variables in constraint instantiated) are checked for satisfaction and filtered out (not passed to external solver). Note that unlike when linear constraints are posted, single variable constraints are not turned into bound updates.

lp_add_normalised

This predicate returns the row indicies of the added constraints. This is needed by the column geneation library. In other cases, these indcies are ignored.

Variables occurs in both the new linear and integers constraints being added. They can be classified as:

The steps performed by lp_add are:

  1. If problem not yet initialised (no variables/constraints set up yet), initialise it
  2. Classify the variables that occur in the new constraints (both linear and integers) into old integers, other old variables, new integers, non-problem variables and new non-integer variables. These need to be treated differently:
  3. The C level code are called to possibly add new rows (if there are new linear constraints) and columns (if there are new problem variables) with the correct type. (cplex_flush_new_rows)
  4. If var_names option is set, pass any variable names for the new varaibles to the solver state.

var_triggers

If there are variable trigger conditions, add the variable trigger condition(s) to the new variables. This same code is used here as during the demon solver's setup.

lp_add_constraints

This basically calls lp_add after normalising the constraints, and then filter out simple one variable linear constraints as done when linear constraints are posted to an eplex instance.
After calling lp_add, the solver is invoked if the nc_trigger field of the handle is set to yes.

lp_eq, lp_ge, lp_le

These are called when the linear constraints (=:=, >=, =< and their  $ equivalents, respectively) are posted to an eplex instance.  The actiions performed are described here.

lp_probe

lp_probe is simply a wrapper around lp_solve: 
lp_probe:
    change Handle's objective function to temporary one
    invoke lp_solve on Handle
    change Handle's objective function back to the original one
if a variable occurs in the new objective, but not in the problem, it is added to the problem if it has bounds of the bounds keeper (i.e. range for range_eplex, ic for ic_eplex). This is to get around the problem where the user post only simple bounds constraints for such variable, which are then not added to the problem. This is not a problem for stand-alone eplex, as such variables are added to the problem.
 

lp_add_columns

adds new columns to the external solver matrix. Unlike lp_add, these new columns may be non-empty, i.e. there may be non-zero values for the existing rows, and objective coefficient.
This is used by the column generation library to add the generated columns. The column information is specified by a list [Var, Obj, Col], where Var is the variable representing the new column, Obj is its objective coefficient, and Col is a list of RowIdx-Value pair representing the non-zero column coefficients.

The steps performed by lp_add_columns are (code is based on the lp_add code, with column-wise C-level buffer arrays for the column coefficients (cmatbeg, cmatind,cmatval) in the problem descriptor:

reduced_cost_pruning

reduced _cost_pruning implements an optional functionality that the programmer can invoke on a solved handle (see for example Michela Manela's work). If we are solving the lp-relaxation of a more complex global problem, and we have a maximum (minimum) of the relaxation, and a lower (upper) bound on the global problem, then we can use the reduced cost information of the relaxed solution to prune variable values that cannot possibly yield a better solution to the global problem.
reduced cost pruning
For those variables whose solution value is at one of their bounds, the reduced cost gives a gradient which says how much the objective deteriorates (at least) when the value moves away from the bound. Values that are so far away that the relaxed cost gets worse than the known bound on the global cost, are useless and so the opposite bound may be pruned to that value.

C Code Level

Versions

The C code needs to be compiled separately for every version of the Cplex or Xpress solver that we want to support. The makefile builds differently named shared libraries from the single eplex.c source file, e.g. One Eclipse distribution can contain several versions of the compiled C code for different solvers and different solver versions. At runtime however, when lib(eplex) is loaded, it can only load one of them. Which one gets loaded depends on the information in the eplex_lic_info.ecl file, see the loader code at the beginning of eplex.pl.

The C code links in the external solver library code statically if possible, and is itself dynamically loaded when lib(eplex) is loaded. However, static linking is not possible with Xpress 14, and in addition two dynamic libraries: the solver itself, and the licensing code, have to be loaded. In addition, the files must be loaded with their full name, including the minor version numbers at the end (e.g. libxprl.so.1.0.3), as this is checked in some systems. To make our code as generic as possible, we ensure that only one copy of each dynamic library is copied into the right subdirectory and preload (in ECLiPSe code) the library by specifying the file name partially (e.g. libxprl.so.* ).

Problem descriptor

We maintain a C-level problem descriptor (which is itself referred to by the Prolog level problem handle) This descriptor stores: The descriptor has a state which is either one of the solution states described under lp_solve/2, or

Initialization and finalization

Two C externals are provided for initialise and finalise the whole subsystem, essentially this means dealing with the licences:

Problem name

Xpress requires a problem name when initialising. Moreover, the problem name is used to generate various intermediate results files (mostly during MIP search). If more than one Xpress is running at the same time within the same file space, then name clashes are possible which might lead to incorrect behaviour. In order to avoid this, the problem name is generated from the machine's host id and the current process's id.

For Xpress, the problem name can contain directory paths, so that the intermediate files can be written in other directory than the current directory.  To allow for this, we allow the user to specifiy a "tem_dir" option for the path. This can have a large impact on performance (elasped time), because the accessing the current directory can be slow (e.g. a NFS file store, like our local file space), and in addition this will allow the user to run their program in a directory they do not have write permission for.

Problem setup and cleanup

Problem setup requires calling many small C externals from the Eclipse code. It is done is three steps. First, cplex_prob_init/8 allocates a C level descriptor including sufficiently large arrays. These arrays are the filled successively using the cplex_set_xxx or cplex_loadxxx functions. When this is finished, cplex_loadprob calls the actual Cplex/Xpress setup routine, passing the previously prepared arrays. In the following, CPH stands for the C level handle, I stands for row numbers, J for column numbers:

Problem modification

Most of the modification functions are split into the transfer of the information into growable arrays (hidden on the C level), and a flush-function which conveys the array contents to the actual solver: For Xpress, only the bounds for a MIP problem can be modified once the MIP search is started. To get round this restriction, we make a copy of the problem, which is pointed to by lpcopy, and solve the problem using the copy so that the original can still be modified. This produces the problem of :
 
The copystatus is used to determine if information is extracted from lp or lpcopy in procedures that are called independently from ECLiPSe. Currently this applies only to p_cpx_lpwrite(). Other accesses to lpcopy are done in code that occurs in p_cpx_optimise(), after the call to optimise. Here, lpcopy is either valid and pointing to the problem copy with the result of the optimisation, or to lp, if copying is not needed (Cplex, or LP/QP in Xpress).
An LP problem can change into a MIP problem if integers constraints are added. This may happen after the problem is initially loaded. This is not a problem for Cplex, which loads all problems with the same routine. Xpress however, has different routines for loading different problem types. We get around this by always using the `global' loading routine (XPRSloadglobal()) for both LP and MIP problems. If the problem is an LP problem, it is simply solved as an LP problem in XPRSminim/maxim. This apparently has no implications in performance for an LP problem. An LP problem can thus be changed to a MIP problem. On backtracking, this change is undone by _cpx_reset_mip_to_lp() undo function.

Unfortunately, when Xpress's solving of an LP problem is aborted, the problem is left in a pre-solved state instead of the original state. The problem can therefore not be modified correctly subsequently. No solution to this problem is implemented currently, but one possible solution is to make copy of an LP problem as well as a MIP problem.

Problem solving and result retrieval

Running the solver is always done with cplex_optimise, regardless of the problem type or the solver method used. There is one function to return the objective value: A darray is actually an Eclipse string, but it contains doubles rather than characters. We use these as the most efficient way of saving large floating point result arrays to the Eclipse global stack.

The various results arrays (solution, dual, slacks, reduced costs and basis) are retrieved inside p_cpx_optimise(). This is done either by setting up a callback function (Xpress 13+, MIP problems), or directly after a (successful) optimisation. In Xpress 13+, setting the callback function avoids Xpress writing solution files during MIP. Note that some files are still created during the MIP search, however. The cleanup routines (p_cpx_cleanup()) will delete any such file for the current session, but if it is not called (e.g. because of some crash), then extra files may be left behind.

Retrieving problem data

These are non-essential functions, used to retrieve information from the C level handle:

Other functions

 
Eclipse level name ChannelNr Cplex Xpress msg type Default Eclipse stream
result_channel 0 result 2 -
error_channel 1 error 4 error
warning_channel 2 warning 3 warning_output
log_channel 3 log 1 -

 

Undo functions

These functions are setup using ec_trail_undo, which places the function on the trail such that it is called when untrailed. Additionally, ec_trail_undo allows a time-stamped trailing so that the function will only be trailed if the time-stamp is `old' (older than the most recent choicepoint).
calls p_cpx_cleanup, and then free the problem descriptor. Trailed during p_cpx_prob_init so problem space can be freed upon backtracking
reset a problem type from MIP to LP.  CPLEX has to be informed of the changed as well (but not XPRESS). Trailed when problem is changed from LP to MIP. In future versions, this function may be extended to change a QPMIP problem back to a QP problem
change a column back to its original type. Trailed when a column type is changed in p_cpx_change_type. The untrail data contains the column's number and the original type. This function is not time-stamped because  each column can only change type at most twice (C -> I ->  B).
delete added rows (and any added columns) from a problem matrix. Rows are always added incrementally, so only one delete is needed per choice-point even if there were many row additions. The same time-stamp as _cpx_reset_col_type is used, as there is no need to reset the types of columns that are deleted. Trailed during p_cpx_flush_new_rows or p_cpx_flush_new_cols. Untrail data contains the old column and row sizes.

 

Multiple handles

While Cplex has always had problem handles, these need to be simulated for  older (pres-13) versions of Xpress.  We will not disucss this further as more recent versions of Xpress also have problem handles.

Memory allocation

Memory in eplex.c is allocated through the macros Malloc(), Realloc() and Free(), which are normally set to the standard C library's allocation functions, but can be redefined for debugging purposes. Note that we have no control over the memory allocation of the actual solver library!

Global Parameters

Cplex and Xpress have a large number of parameters that affect their behaviour. Only a few of them coincide with their meaning. We have therefore decided to map the parameter access one-to-one from the C level to the Eclipse level. While the rest of eplex tries hard to hide all the differences between Cplex and Xpress, the parameter setting is the exception.
To make things worse, every new release of Cplex or Xpress comes with a modified set of parameters. We have therefore introduced a fixed mapping from the parameter names in the solver's C interface to the (atomic) parameter name that is used on the Eclipse level, e.g.
Cplex's CPX_PARAM_NODELIM becomes nodelim
Xpress's MAXNOD or N_MAXNOD becomes maxnod
The mapping is defined in the file eplex_params.h, which unfortunately must be updated for every new solver release. The comment at the beginning of the file explains how to do the job semi-automatically using editor commands.

Solver Numerical Differences

The external solver  may give different results depending on the FPU control settings. One example that affects XPRESS 13.26 under i386_linux is that the floats are normally in `extended precision' of 80 bits in the hardware registers. This is the default used when ECLiPSe is started. However, if embedded Java is used, Java sets the float precision to double, i.e. 64 bits. With XPRESS 13.26, this can result in different behaviours of the solver, e.g. Retimer can give different alternative answers.

Debugging the External Solver

When an error occurs in using eplex (program crash, unexpected abort, or incorrect result returned), the error can be due to  ECLiPSe (either C or Prolog level), or the external solver. In the case of the external solver, we cannot fix the bug, but we can report it so that it can be fixed (and perhaps workaround the problem in our own code).

In order to report a problem to Dash or ILOG, we need to show that the problem
is due to their external solver. Several methods are available to do this:
Other useful methods to aid in debugging is to run the whole ECLiPSe session under a memory debugger like valgrind. This can show up problems both in ECLiPSe and the external solver.

Logging External Solver Calls

There are extra code at the C level which are used to generate a log of the calls made to the external solver. These code are only compiled if the macro LOG_CALLS is defined. The log consists of the calls, plus extra support code, so that only a header file and the toplevel procedure need to be added to generate a pure C program, which can then be used to make bug reports to Dash or ILOG.
 

Structure of the log code

The log code consists of a number of step_N procedures, where N is an integer. Each such procedure makes a call to the appropriate optimise function of the external procedure, after setting up the data and making the other supporting calls to the solver. After the optimise call, a new step_N procedure, with N incremented by 1.

The data needed for the calls is stored in the same C level problem descriptor lp_desc that the eplex code used. This is defined in an include file, along with some procedures and variables that the log code use. There are three include files, for the three versions of log code generated:
 

Xpress 13+ bugxprs.h
Xpress 12 bugxprs12.h
CPlex (6.5+) bugcpx.h

The include file has the following support variables:

struct lp_desc *lpd;
struct lp_desc *lpdmat[20];  /* change size if more lpd used */
double objval;
int res,err;

lpdmat[] is an array to support multiple handles. The generated log code loads the appropriate lp_desc from lpdmat into lpd at the start of a step_N procedure, and at any time the handle changes. Note that the size of lpdmat may need to be adjusted upwards if the logged program uses more handles than is defined. objval is used to store the objective value if required (getting the objective value is not automatically generated in the log code), and res and err are used to store any return codes from function calls.

Finally, a main procedure needs to be added to call all the step_N procedures in sequence,  e.g. if there are three steps, and the solver is Xpress 13+:

 main() {
    XPRSinit(NULL);
    XPRScreateprob(&cpx_env);
    step_0();
    step_1();
    step_2();
}

In this case, the cpx_env is the dummy problem where all the default parameter values are stored.
 

Logging macros

Several macros are defined to minimise the amount of special logging code needed: In addition, logging code is also given between #ifdef LOG_CALLS, e.g. for loading the various data structures.

The logged call is generated by printfs, to the log_output stream. In order to allow macro transformation for the logged code to be performed, the call is wrapped in a Transform_Quoted macro, which performs the transformation even though the logged call occurs inside the printf quotes.