Implementation Notes for lib(eplex),  in ECLiPSe 5.10

 #Introdcution
 #Global structure
 #Eclipse Code Level
 #C Code Level

Global structure

Files

• seplex.c: low level functions, lots of ifdefs for CPLEX and XPRESS and different versions of them (modified from eplex.c)
• eplex.pl: top-level wrapper for loading the eplex/seplex library
• eplex_standalone.ecl: provides the standalone specific  macros and support. This is loaded by eplex.pl if seplex is selected. In turn it loads eplex_s.ecl, where the bulk of the ECLiPSe code for seplex is. There are two modulles, eplex and eplex_s. This file was needed when there was standalone and ic/range eplexes.
  
• eplex_s.ecl: generic (independent of cplex/xpress) code implementing the library functionality. This code is loaded into the eplex_ module (modified from eplex_.ecl).
• s_eplex_xpress.pl and s_eplex_cplex.pl: trivial wrappers for eplex.pl to force loading of either solver with seplex
• s_eplex_comments.ecl: the comment directives documentation for seplex (modified from eplex_comments.eci).
• eplex_lic_info.pl: data file that can be edited by the user (which licence on which machine). Also determines the default solver.
• empty_language.ecl: contains the small set of predicates that are needed in the dummy modules used to select external solver/bounds keeper.
• eplex_params.h: contains a C table to map the CPLEX/XPRESS/OSI parameter value to symbolic names used on the Eclipse level. This is created semi-automatically from the xpresso.h or cplex.h respectively.
• seplex.h:  header file for eplex: used by seplex.c and coinplex.cpp, for common declarations used in both files. Also used for compiling loged cide,
  
• coinplex.cpp: C++ code interface to OSI solvers, provides the API that seplex.c calls for the OSI solvers.
  
• seplex_xpress.def and seplex_cplex.def: DLL export specification for the Windows build
• WinMSC/Standalone: the corresponding projects for the Windows build (no longer used with Windows cross-compiling)
  

• lib(linearize): used to linearize arithmetic expressions
• lib(var_name): provides stable variable name support
• lib(constraint_pools): support for eplex instances

Modules

There are several dummy modules, eplex_cplex, eplex_xpress, eplex_osi and eplex_osi_*, (defined in the corresponding files). They don't contain anything. The only effect is that eplex_s.ecl attempts to load the Cplex version when the module eplex_cplex exists, and the Xpress version when module eplex_xpress exists, etc.. If none of them exist, the loaded solver is solely determined by the eplex_lic_info file. More specific dummy modules can also be created by the user to specify the  exact solver version to load, in the form eplex_<solver>_<version>, e.g. eplex_xpress_1427icp for the OEM (`icp') version of Xpress 14.27.  Note that `version' for OSI indicates the actual solver (or combiation of solvers) used through the OSI interface. The available versions can be found by examining the binaries that are built, which has the same version information appended to the end of the file/directory names to allow binariies for more than one version of the same solver, e.g. express1417icp.so.

The dummy modules now reexports empty_language. This restricts the defined predicates in these modules to the very small subset of built-in predicates re-exported from  sepia_kernel by empty_language. This subset are the predicates that are actually used in these modules. This was done to avoid the confusion that these dummy modules might be eplex instances that the user can post constraints to. This will now raise an `undefined predicate' error.

Debugging

Eclipse Code Level

Licences and versions

• Solver given in * (where * is an available solver), if lib(eplex_*) was called
• the first one listed in eplex_lic_info.ecl if lib(eplex) was called
• if no solvers are listed in eplex_lic_info.ecl, then the first solver found in the directry listing.
  

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.

For OSI, lp_get_licence/0 is used only to determine the solver to load, and not obtain any
licenses. This is because OSI does not provide any provisions to obtain licenses: open-source solvers will not require licenses, and for commercial solvers, the license has
to be obtained using the normal mechanisms provided by the solver (e.g. by setting environment variables).

Attribute

:- export struct(
        eplex(
            stamp,      % time stamp for this variable in this solver. 
            solver,     % A solver that this variable occurs in
            idx,        % The column number(s) 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 solver field contains one of the problem handles where the variable occurs,  and the attribute represents the variable in that problem. This is normally one column in the problem matrix, but if  the variable has been unified with other problem variables, then it may represent multiple columns in the same problem. See #mergecol
idx is a list of the column numbers represented by the attribute. 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 stamp field is needed at the C level, it is used for timestamping in the undo functions that affects this variable in the solver (i.e. the column idx in the matrix), e.g, bounds and type for the column.

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,
        get_bounds:lp_attr_get_bounds/3,
        set_bounds:lp_attr_set_bounds/3,
        suspensions:suspensions_eplex/3
    ]).

• schedulting the intol_inst list if necessary
• when the variable is instantiated to a number, update the column bounds in all the external solver state(s) where the variable occurs. The upper and lower bounds are set to the numeric value of the number [This is done with seplex only as bounds are no longer synchronnised].  In addition, the demon solver (for the attribute) is triggered if bounds/deviating_bounds was specified as triggering conditions, and the condition is met. Note this is not implemented using the normal suspension list mechanism as we have access to the solver suspension directly from the attribute: we directly call schedule_suspensions/2 with the suspension in a dummy goal.
• merging the eplex attribute chains when two eplex variables are unified:
• transfer the attribute chain if necessary if only one variable is an eplex variable.
• if both are eplex variables, their chain is merged. The chain needs to be checked to see that the two chains do not contain attributes structures for the same solver state. If they do, one of the attribute structure is discarded, and an equality constraint send to the solver state. The event lp_unify_same_handle is also raised.

Problem Handle

• a set of constraints, including bounds constraints
• an objective function
• the variables that occur in these constraints or the objective function
• a (possibly empty) subset of these variables that are considered integers
• a number of option settings

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.

:- export struct(
        prob(
            cplex_handle,       % handle to C data structure
...
            vars,               % [Xn,...,X1]: list of problem variables
            ints,               % [Xi1,...Xik]: list of integer variables
...
            presolve,           % 1 for yes, 0 for no
            use_copy,           % 1 for yes, 0 for no
...

            method,             % atom: solving method (primal, dual, ...)
            demon_tol_int,      % float: tolerable deviation of instantiation
            demon_tol_real,     % float:  ... to simplex solution.
...
            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 _)
        )
    ).

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 cutpool constraints

Support for column generation

• returning row indicies for the added constraints (lp_add_constraints/4)
• adding columns with coefficients for existing rows, and also a non-zero objective coefficient (lp_add_columns/2)
• retreiving column data from the ECLiPSe level

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

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.

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.

OSI provides a small number (less than 10) of parameters, and the interface treats them as problem specific. Only the most basic and common parameters are provided, and not all of them useful in the eplex context. We provide access to those parameters that are useful, and in addition, to some solver specific parameters, and also some parameters to how eplex
itself behaves at the OSI interface level. For the eplex user, all these parameters
are seen uniformly as optimizer_param.

Note that the presolve  and timeout parameters are treated specially. They do not correspond directly to the low level parameters of the solver. Instead they alway behave as if the 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 are copied into each new problem that are created.

When used from ECLiPSe, these parameters are wrapped in an 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

        [C0*1, C1*X1, C2*X2, ...]

        Sense:NormExpr

        (>=):[-5*1,3*X]

        5 =< X*3

Bounds constraints

Treatment of these bounds constraint are different before and after the setup of a solver state. After setup, bounds for the variables are maintained in the external solver, and if the posted bounds constraint narrows the bound(s) for the variable, these are passed to the external solver (with an undo function to restore the original bound on backtracking). Before setup, the bounds are stored as single variable >=/=< constraints. During problem setup, single variable constraints are detected and converted to bounds updates for the external solver if the bounds are narrowed.

For a problem that has been set up, bound updates can also be done with lp_var_set_bounds/4, for existing problem variables. This is not considered as posting a constraint (i.e. it would not trigger wakeup with the new_constraint trigger option).

Bounds are treated like other constraints, and each solver state can have its own bounds, even if they are mutually inconsistent. In addtion, a variable is never instantiated by the posting of eplex bound constraints.
 

Unification of problem variables

• The column indecies are merged into one list. With the first index in list of the retained attribute remaining the first index in the merged list. This is required because the time-stamp in the attribute is used in updating the column's bound at the C-level, and this time-stamp must always be used for the same column for correct untrail behaviour.
• The bounds from the merged columns are merged, and if the merged bounds is different from the original bounds, the new bounds are posted to the column represented by the first index.  Only the bounds of this first column will be updated, and when user request the bounds of any of the merged columns, it is the first column's bound that will be returned. The other column bounds are no longer updated, as their original time-stamps are no longer available.  Note that for the external solver, the bounds need not be updated, as long as there is an equality constraint linking the merged columns. The update is done so that the user can see the correct bounds, and also for the bounds trigger mode to behave correctly. As this bounds merging is done every time two variables are merged, only the first column from the two merging variables needs to be examined.
• The column types are merged: if one of the merged column is of integer type and the other not, then this column(s) is also set to integer in the external solver.  This is done so that when obtaining the solution value via typed_solution, the correct type for the solution is always returned.
• an equality constraint between the first columns of the merged variables is added to the solver state, unless the post_equality_when_unified option is set to no. This option is available because there may already be other constraints in the solver state that constrains the two columns to be equal, and adding a redundant equality constraint may needlessly slow down the solving process.  If an equality constraint is posted, then the demon solver is scheduled if the new_constraint trigger mode is set.
• the intol_inst lists are merged

1. Retain the old state, with the definition that the state information is the information available from the (logically) last solve of  the problem
2. Clear the old state, with the definition that the state information is for the problem as it is currently defined. Any time the problem is altered, the state has to be cleared

Accessing the solution value through a merged variable will return the solution value from the first column: after the problem is resolved, the solution values in the merged column would be the same because of the equality constraints. Accessing the reduced cost, through a merged variable will return 0.0. It is not safe to simply return one of the reduced cost, because the user may be summing the reduced cost of all the variables. Returning a 0.0 is the safe and simple way of dealing with this.
 

Eplex instances

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

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_s.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. before solver setup:
• add the normalised form to the linear constraint type of the constraint pool.
4. after solver setup:

• if constraint has only one variable, turn it into a bound update (shared code with ::/2)
• otherwise, add the constraint to the solver state with lp_add_normalised. If the constraint involves new problem variables,  these are added to the vars list.

• before solver setup:

1. extract the variables into a list, eliminating ground integers
2. 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

• after solver setup:
1. extract the variables into a list, eliminating ground integers
2. for the remaining variables, if the variable is an existing problem variable, change its column type to integer in the external solver state, if it is not already integer or binary (with trailed undo function). If it is a new problem variable, create a column for it in the external solver (and add to vars list)
3. Note that the problem type might change from lp to mip. If the problem is a qp problem, this will raise an error currently, as we cannot yet change a qp to a qp mip problem.

1. fail if the the lower bound is greater than the upper bound
2. extract the variables into a list
3. if the solver state is not yet setup, post the upper and lower bounds as constreaints, for each variable on the LHS: V <= Upper and V >= Lower, Otherwise:
4. Determine which of the variables on the LHS are new (i.e. not already in the solver state).  New columns for these.
5. For each variable in the LHS: get the existing bounds for the variable from the solver state, check if new bound(s) are narrower. If so, impose the new bound(s).
6. if any new bounds were imposed, trigger the bd_trigger suspension list of 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

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

constraints:              integers/1, reals/1, =:=/2, >=/2, =</2, ::/2
solver setup:            eplex_solver_setup/1, eplex_solver_setup/4
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

Associating external solver state

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

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

•  A quadratic mix integer problem (qmip) is set up if the objective is not linear and if the list of integers is not empty
• A quadratic problem (qp) is set up if the objective is not linear and the list of integers is empty
• A mixed integer problem (mip) is set up if the list of integers is not empty. Note that the integrality-information in the range-attribute (range:integers/1) is completely ignored for this purpose. This allows lp_setup to set up a linear relaxation easily.
• A linear problem (lp) is set up otherwise

• a non-integer problem (lp, qp) can change into a mix integer problem (mip, qmip) with the posting of integer constraints. On backtracking, the original problem type is restored.
• a mixed integer problem (mip, qmip) can change to a non-integer problem (lp, qp) if the integer constraints are relaxed during an lp_probe. The original problem type is restored after the probe.
• a non-quadratic problem (lp, mip) can change into a quadratic problem (qp, qmip) and vise versa with lp_probe by the objective. The original problem type is restored after the probe.

lp_setup:
    assign a new solver id
    renormalise constraints (possibly do some simplification)
    normalise the objective (and determine whether it's linear)
    create list of problem variables
    create list of integer variables if required
    assign column numbers to the variables and store them in the attributes
    classify and convert constraints, depending on number of variables:
    pass problem data, including objective coefficients, rhs, matrix
    coefficients (in column-wise format) to the C-level handle

      0 : check for satisfibility immediately
      1 : convert into bound check/update for external solver
      >1: convert to column-wise lists of row:coefficient pairs
 
    call the C-level problem setup function cplex_loadprob()

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

Note that there may be restrictions on the problem types available depending on the solver:

• the problem type may be unavailable for the particular solver (for example qmip for older CPLEXes). This is checked for in the C level code and an error raised. An error is also raised for qmip for Xpress older than version 15, as qmip is `not recommended' for these older versions, even though the library calls are available (they certainly seem quite buggy)
• the problem type may be unlicensed in a particular solver. In this case, we rely on the external solver to raise the error.

lp_solve

lp_solve:
    synchronise bounds if requested to do so (option sync_bounds)
    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)

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. [Note CPlex 8 can properly handle infeasible/unbounded for primal/dual problems]

optimize

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

1. setting up a solver
2. create the lp_demon suspension
3. insert the suspension into the suspend field of the handle
4. run the solver once if initial_solve option is yes
5. calling the post-goal (see user documentation)
6. bounding the Cost variable (using the generic set_var_bounds/3)

1. calling the pre-goal
2. run the solver again
3. calling the post-goal
4. bounding the Cost variable

lp_add

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

renormalise_and_check_simple

lp_add_normalised

Variables occurs in both the new linear and integers constraints being added. For the integers variables, they can be classified as:

• old variables:  variables that are already in the solver state
• old integer variables:  old variables which occur in the new integers constraints. They may or may not already be constrained to be integer
• other old variables: old variables which  occurs in the new linear constraints only
• new variables: variables that are not yet in the solver state
• new integer variables: new variables which occur in the new integers constraints. (They may also occur in the new linear constraints)
• new non-integer variables: new variables which occur in the new linear constraints only

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, and the new non-integer variables. These need to be treated differently:
• old integers: the type of columns representing these variables in the external solver matrix need to be changed  if it was not already an integer (or boolean). The type changes are undone on backtracking at the C level.
• new integers: new column needs to be added to the external solver matrix, as type integer
• new non-integer variables: these are new variables that are not constrained to be integers. A new column needs to be added to the external solver matrix, as type continueous.
3. Pass the new column-wise problem data (for existing rows) to the C level buffer arrays (set_var_index + setup_new_cols + code to pass integer/bounds information)
4. Pass the data on the new rows to the C level buffer arrays (setup_new_rows)
5. Call the C level predicate to flush the new data in the buffer arrays to the external solver (cplex_flush_new_rowcols)
6. If var_names option is set, pass any variable names for the new varaibles to the solver state.

 

var_triggers

lp_add_constraints/3

lp_add_constraints/4

lp_add_columns/3

The steps performed are:

The initial setup of a matrix in lp_setup does not use setup_new_cols, because the processing of the constraints are done differently. However, it does use the same C calls to pass the column-wise data to the buffer arrays: cplex_set_obj_coeff(), cplex_set_matbeg(), cplex_set_obj_coeff().

lp_eq, lp_ge, lp_le

lp_impose_interval

integers

lp_read, lp_write

• creates a new problem handle
• calls cplex_lpread to read in the C level representation of the problem
• extract the problem variables and types for the problem handle
• retrieve the objective coeffs for the problem handle. Currently only the linear objective  is retrieved, as Xpress did not properly support the retrieval of the quadratic objective coeffs. [this has changed with Xpress 16, and retreival of the quadratic objective should be added]
  

lp_probe

The problem can be modified by multiple probes, but not all combinations are allowed. This is checked for when the probes are extracted: if an unknown probe or an illegal combination of probes are found, an error message is printed and lp_probe aborts.

The problem is modified by applying the probe changes to the problem individually.  After the problem is solved, the modified problem is restored by reversing the modifications done by the probes in the reverse order.  Both the modification and solving of the problem catches failure and exceptions (via block/3) so that the probes that have been applied so far can be undone before the failure or exception is allowed to continue.

For each probe, code must be written for:

• extract_one_probe(+ProbeSpec, +ProbeInfo, +ExtractedIn, -ExtractedOut): ProbSpec is the specification for one probe, and ProbeInfo is the probes data structure which is used to unify with the extracted probe information. This unification should fail if there has already been an incompatible probe specified. ExtractedIn/Out is a list of the extracted probes. ExtractedOut should add to ExtractedIn the probes extracted from ProbeSpec, and the priority the probe should run at, in the form <probe>-<prio>. At the end of extracting the probes, Extracted will be a list of the extracted probes, and this list will be sorted according to their priorities, so that the setting of the probes can then be done according to the sorted Extracted list.
• problem modification handler , wrapped inside a block_with_probes call in set_probes/4. This modifies the problem according to the appropriate entry in the probes strcture (and will probably involve C calls to perform the modification). The handler should add an entry to the head of the SetProbes list that contains the information needed for performing the correct problem restoration handler to undo the modifications. Note that any changes made by the current handler is not automatically undone. To avoid this problem, the handlers do not make incremental changes to the external solver state. Instead, each handler phould makeall the changes it is required in one go to the external solver.
• problem restoration handler, which undoes the modifications for the probe.  This should be added as a unset_one_probe(+Handle, +SetProbe) clause. SetProbe is the entry in the SetProbes list added by the problem modification handler for the probe, which is used to select (and supply the needed information for) the restoration handler to call.

For the `ints' probes (fixed and relaxed, which modifies a MIP problem and solves the modified problem as an LP problem) has a complication: during the problem modification, the problem type is set to the appropriate type (fixed or related) by a call to cplex_set_problem_type. This change the problem type at the C level. For  CPLEX, which maintains its own problem type, the CPLEX problem type is not changed, and this is specified by a 0 for the last argument in cplex_set_problem_type. The reason for this is that for these ints problem type (which CPLEX partially supports directly),  CPLEX cannot change to these problem types without having first solved the corresponding MIP problem. As we do not restrict the user to having first solved the MIP problem,  there may not be a solved MIP problem to permit the problem type change. The CPLEX problem type is only changed when the problem is solved in the C procedure p_cpx_optimise.  When undoing the change in the problem restoration handler, cplex_set_problem_typeis called with 1 for the last argument so that the CPLEX level problem type is also reset (the CPLEX problem type cannot be reset earlier as changing the problem type prevents CPLEX from accessing the information associated with the solution).

When column-related information is modified by the probe, the change must take into account that multiple columns may be represented by one variable, and that these merged columns must be considered as one. For example, the bounds probe,  which changes the bounds on columns, must apply the same bounds to all the merged columns. The perturb_obj probe works correctly because it changes the objective coefficients (rather than speciffying the new coefficients) and is cumulative (thus changing more than one merged variable will behave correctly); and the objective probe behaves correctly because eplex keeps a representation of the objective using the column numbers directly (rather than variables).

Note that unlike the other modifications done to the problem, modifications done by the probes does not need to be backtrackable, because modifications done when setting the probe are undone when unsetting. At the C level, it means that an untrail function is not needed.

reduced_cost_pruning

Cutpool constraints

• store constraints non-logically (i.e. they are not removed on backtracking), which can then be taken into account in all subsequent invocations of the solver.
• flexibility in how the constraints are taken into account when the solver is invoked. The constraints can be
• added to the problem matrix initially, just before the external solver is invoked (specified by add_initially status)
• added to the problem matrix only if the constraint is violated by a solution returned by the solver. The solver is then re-invoked until no constraints are violated.
  
• not considered for adding to the problem at all
• organise the constraints into named groups
  

The cutpool constraints are passed to the C level for non-logical storage. Conceptually they can be considered to be in a cutpool matrix with the same columns as the normal problem matrix, and the rows representing the cutpool constraints. The `raw' index for a cutpool constraint is the row number for this cutpool matrix. At the ECLiPSe level, the raw index is wrapped by a structure to distinguish it from the normal constraint index: 
          g(2,RawIdx).
2 indicates the constraint type -- cutpool constraints. This allows other constraints type to be added in the future. (it was also used to distinguish conditional and unconditional cutpool constraints in the first version of the cutpool constraints, but these have been combined into the single cutpool constraint type in the current implementation). The predicate rawidx_cstridx/3 is used for conversion (and indentification) between the `raw'  and full index of a constraint.

To setup/access the constraints, the same routines as for the normal constraints are generally used, with the constraint type and raw index used to identify the constraint. For these routines, 0 is the constraint type for normal constraints.

1. 'Normal' problem constraints
   
2. cutpool constraints - this consists of all the added cutpool constraints
   

               

           Normal         cutpool

      |------------------|--------------|

      <------- mr ------>

The row-wise data arrays for the solved problem (dual, slack values) are arranged as showned above, i.e. those rows beyond index mr are the cutpool constraints.  In order to map the cutpool constraints from the cutpool into the actual row for the problem matrix.

To map the raw index of the constraint into the row index in the solved problem matrix shown above, a `Map' is returned as part of the result state by cplex_optimise. This is stored in the cp_cond_map field of the Eclipse handle. This Map shows the status for each cutpool constraint in the last solve. The cutpool constraints are indexed by their `raw' cutpool index, and their value in the Map indicates:

• value >= 0 : the constraint was added to the matrix. Value is the row number displacement from the end of the normal constraints, i.e. the row index in the result arrays is mr + Map[rawidex]
  
• value < 0: the constraint was not added to the matrix. The actual value indicates
• satisfied   the constraint was satisfied but not binding, so it was not added to the problem matrix
  
• binding   the constraint was satisfied and binding, so it was not added to the problem mattrix
• inactive   the constraint was inactive, so it was not added to the problem matrix
• violated  the constraint was violated. This status should not be seen if problem was solved successfully [because the constraint would have been added to the problem and resolved]
• invalid  the constraint was invalid. Some problem occurred at the C level when trying to add the constraint to the problem matrix.  This status should not be seen normally.

Cut pool constraints can only involve variables that are present in the problem at set up. This is done to avoid the problem of backtracking pass the creation of the variables. While it is possible to relax this restriction to variables that exist at set up time rather than those that have been added to the problem, this condition is harder to enforce and understand. For this purpose, the number of columns after problem set up is remembered in the problem handle (in problem parameter 15, accessed via cplex_get_prob_param), and variables with larger column numbers are not allowed in the cut pool constraints. A subtlety arises with a problem variable that represents multiple columns -- we cannot reject a variable simply by looking at its first column number, we can only reject the variable as a new variable after going through all the column numbers.

User level predicate to add cutpool constraints:

lp_add_cutpool_constraints

     lp_add_cutpool_constraints
            normalise and check that the constraints are non-ground
            extract the options
            add constraints to cutpool  (using setup_newrows)
            add cutpool constraint information
            (named group, add_initially and active states)

note that the failure can occur while adding constraints. In this case, the cutpool will be restored to its original size before the constraints are added. It is assumed that once the constraints have been added, adding the cutpool information cannot fail.

It is a deliberate design decision not to provide an eplex_* version of lp_add_cutpool_constraints for eplex instances. One reason is that we don't have a good abstraction for constraint indexes for eplex instance. Secondly, other eplex_* family of predicates allow the predicate to be called before problem setup, and as cutpool constraints are implemented at the C level using the C problem handle, cutpool constraints cannot be added before problem setup without more infrastructure at the ECLiPSe level to do so.
However, note that it is possible to add cutpool constraints to eplex instances using lp_add_cutpool_constraints and the handle for the eplex instance.

lp_get, lp_set

lp_write

cplex_optimise

C Code Level

Versions

• secplex65.so for Cplex 6.5 (compiled with -DCPLEX=6 and -D CPLEXMINOR=5)
• sexpress1412.so for Xpress 14.12 (compiled with -DXPRESS=14)
• seosiclpcbc.so OSI with Clp (linear) and Cbc (MIP) (compiled with -DOSI for seplex.c, -DCOIN_USE_CLP for conplex.cpp)
  

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

• struct lp_desc {}

• the solver-specific problem descriptor (CPXLPptr for Cplex, XPRSprob for Xpress 13+, COINprob for OSI)
• additional data about the problem we want to maintain in non-backtracked storage (e.g. success and failure counters)
• all data (esp. arrays) that need to be built up incrementally during problem setup, and that are then used as input to the solver's own problem setup function. These are not maintained after the data is passed to the external solver.
• cutpool constraints (the constraints arrays, along with the status arrays, and the arrays for maintaining the name groups) are stored in the descriptor. Unlike the other data, this information is maintained in the descriptor, and is passed to the external solver before each invocation.
  
• some problem specific settings that are more convenient/efficient to maintain at the C level, e.g. the presolve state

• DESCR_LOADED during setup, no solve attempted yet
• DESCR_EMPTY after cleanup

Initialization and finalization

• cplex_init(LicenceLocation, SerialNum, SubDir), p_cpx_init

tries to obtain a solver licence, fails if this is not possible. The arguments come from the eplex_lic_info.ecl file. SerialNum is only relevant for Cplex runtime licences. SubDir is needed for Xpress 15: this is the directory where the license manager is stored, and is used to set  the PATH environment variable, as Xpress calls the license manager without any qualification during initialisation. For OSI, nothing is done.


• cplex_exit, p_cpx_exit

releases the solver licence (if required), and deallocation of some of the storage

Problem name

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

• cplex_prob_init(PreSolve,UseCopy,Rows,Cols,NonZeros,TempDir,Sense,-Handle), p_cpx_prob_init

allocates the C-level handle and stores it into the first argument of the Eclipse-level handle. Also allocates arrays for a complete column-wise representation of a problem of the given size (number of rows, columns, nonzeros). An undo-function is trailed which will deallocate the handle with all its arrays on backtracking or garbage collection. The Presolve argument is either 1 or 0, and the C level descriptor's presolve field is set to this value. Before calling any external solver library calls that may be affected by the presolve state, the presolve state is set according to the presolve field. This allows the presolve state to be set on a per-problem basis. TempDir is the path for a temporary working directory, which is needed by Xpress. For better performance, this directory should be on a local disk.

• cplex_set_rhs_coeff(CPH,I,SenseCode,Rhs), p_cpx_set_rhs_coeff

• cplex_set_obj_coeff(CPH,J,Val), p_cpx_set_obj_coeff

set objective coefficient for variable column J.
 
• cplex_set_qobj_coeff(CPH,J1,J2,Val), p_cpx_set_qobj_coeff

set quadratic objective coefficient for the product of variables column J1 and J2


• cplex_set_type(CPH,J,TypeCode), p_cpx_set_type

set type of variable column J.  TypeCode is a ASCII code for C, I or B. This is done only for a column that has not yet been passed to the solver, i.e. the type is set in the buffer array ctype, which is later passed to the external solver. For modifying  an existing column type, cplex_change_col_type/4 should be used.

• cplex_set_matbeg(CPH,J,K,K1), p_cpx_set_matbeg

coefficient array locations K to K1-1 contain entries for column J.
 
• cplex_set_matval(CPH,K,I,Cij), p_cpx_set_matval

set the matrix coefficient for row I and column J (implicit) in coefficient array location K.
 
• cplex_init_new_col_bound(CPH,Cj, Lo, Hi),p_cpx_init_new_col_bound

• cplex_new_col_bound(CPH,Cj,Bd,Which),p_cpx_new_col_bound

• cplex_set_var_name(CPH, Cj, Name), p_cpx_set_var_name

• cplex_loadbase(CPH,Basis), p_cpx_loadbase

load a basis (a string buffer, obtained by retrieving from the handle earlier)
 
• cplex_loadorder(CPH,Length,OrderList), p_cpx_loadorder

load MIP branching order preferences (undocumented feature)
 
• cplex_loadsos(CPH,SosType,Size,Js), p_cpx_loadsos

load definition of an SOS 1 or 2. Js is a list of length Size of the column numbers that make up the SOS.
 
• cplex_loadprob(CPH), p_cpx_loadprob

set up the actual solver problem using the (now filled) arrays in the C level handle.
 
• cplex_cleanup(CPH), p_cpx_cleanup

free the problem descriptor (this also happens on untrailing and garbage collection).

Problem modification

• cplex_new_obj_coeff(CPH,J,Val), p_cpx_new_obj_coeff

set new linear objective coefficients
 
• cplex_flush_obj(CPH), p_cpx_flush_obj

actually transfer new linear objective coefficients to the solver
 
• cplex_new_qobj_coeff(CPH,J1,J2,Val), p_cpx_new_qobj_coeff

set new quadratic objective coefficients
 
• cplex_set_new_cols(CPH, NAdded, NewObjCoeffs,NZeros), p_cpx_set_new_cols

prepare the column-wise buffer arrays for NAdded new columns, with NZeros non-zero coefficients in these columns. NewObjCoeffs is either an empty list if the new objective coefficients are all zero, or a list of length NAdded of the objective coefficients for the new columns.
 
• cplex_new_row(CPH,SenseCode,Rhs,CType,Idx), p_cpx_new_row

start adding a new row with given constraint sense and right hand side, for constraint type CType (normal or cutpool). Idx is returned with the row index of the row
 
•  cplex_add_coeff(CPH,J,Cij,CType), p_cpx_add_coeff

set coefficient for column J in currently added row (of type CType: normal or cutpool)
 
• cplex_flush_new_rowcols(Handle,HasObjs), p_cpx_flush_new_rowcols

actually transfer zero or more new rows and columns to the solver.
HasObjs is zero if the new columns have zero objective coefficients. If this is non-zero, then the objective coefficients for the new columns are also passed to the solver. The new columns can have non-zero values for the existing (pre-addition) rows; all the data should have been correctly transferred to the C level buffer arrays before this function is called. Note the Prolog handle is taken rather than CPH; the timestamp in the Prolog handle is for the undo function _cpx_del_rowcols to remove the added rows and columns.
 
• cplex_impose_col_bounds(Handle, Attr, J, Flag, Lo, Hi, Changed), p_cpx_impose_col_bounds

• cplex_impose_col_lwb(Handle, Attr, J, Lo, Changed), p_cpx_impose_col_lwb

• cplex_impose_col_upb(Handle, Attr, J, Hi, Changed), p_cpx_impose_col_upb

• cplex_change_col_type(Handle,  J, TypeCode), p_cpx_change_type

change the type of column J to TypeCode (the code for the type obtained from type_to_cplex_type/4).  Handle's timestamp is needed for the undo function _cpx_reset_col_type to reset the column type on backtracking. Attr is the eplex attribute for this solver state for the variable representing column J. This is needed to avoid warnings from Xpress 14 when a column is changed to integer type with bounds greater than representable with 32 bits (XPRS_MAXINT):  if a column bound originally has greater bounds, they are set to XPRS_MAXINT, and an undo function _cpx_restore_bounds is used to restore the bounds. No timestamp is used in this case because the column type can be changed for merged columns, which no longer have a unique Attr. This should happen at most once per forward execution per column, so it should not be too expensive.
 
• cplex_change_lp_to_mip(Handle), p_cpx_change_lp_to_mip

 changes a lp type probelm to a mip type problem. Change is undone on backtracking.


•  cplex_change_obj_sense(CPH, Sense), p_cpx_change_obj_sense



used for probing. Sets the sense of the objective to Sense.
 

• cplex_change_rhs(CPH, Size, RowIdxs, RhsCoeffs), p_cpx_change_rhs



used for probing,  Change the rhs coeffs in the rows specifiied in RowIdxs to RhsCoeffs. RowIdxs and RhsCoeffs are lists of the same length, Size is the length of these lists.
 

• cplex_change_column_bounds(CPH, Size, Idxs, Los, His), p_cpx_change_column_bounds



used for probing. Change the column bounds specified in Idxs to Los (lower bound) and His (upper bound). Idxs, Los and His are lists of length Size. The bounds are changed without an untrail function to undo the change on backtracking.
 

• cplex_set_problem_type(CPH, Type, SetSolverType), p_cpx_set_problem_type



used for probing. Sets the eplex problem type to Type. If SetSolverType is 1, then the solver's problem type is also set to Type.
 

• The problem pointers lp and lpcopy are always present, even when it is not needed. In these cases, lpcopy and lp points to the same problem.

• When copying is needed, the problem is copied from lp to lpcopy just before it is solved as a MIP problem, and any modifications to the problem is always done to lp, not lpcopy. Once solved, solution data is obtained from the copy until it becomes invalid when the problem is modified (either by forward execution or backtracking in ECLiPSe; the appropriate function must make the copy invalid by changing the copystatus, see next item).

• In XPRESS 13+, which needs the problem copy for MIP modification, an extra field in lp_desc, copystatus, is used to specify the status of the copy:

• XP_COPYOFF: we are not using a copy (MIP modification would not be possible, but solving single MIP problems will avoid the copying overhead)
• XP_COPYINVALID: the problem in lpcopy is invalid.
• XP_COPYCURRENT: the problem in lpcopy is current

Problem solving and result retrieval

• cplex_optimise(+Handle,+SolvingMethods,+TimeOut,+DumpOpt,+StateArrays-Result,-Status,-Best, -Worst), p_cpx_optimise

run the solver, using the given Method (primal,dual,barrier,...), with SolvingMethods specifying the solving methods to be used: m(Method,AuxMethod, NodeMethod,AuxNodeMethod), where AuxMethod specifying the auxiliary method if the method requires it (e.g. crossover for barrier). For mip problems.,Method specifies the method for solving the root node., while NodeMethod specifies the method for the other nodes in the MIP search-tree. If the `default' method is specified but not supported by the solver (e.g. older CPLEXes), this is translated to what the `default' method is, as specified in the solver's manual.  If the specified method is not supported by the solver, the default method is used instead (with a warning printed).

If TimeOut is non-zero, set the solver's timeout to TimeOut. Timeout should be in the correct type and value for the solver [this is ensured at the ECLiPSe level]. In the case of CPLEX, the timeout is always set - if it is zeo, it is set to the default value (a large number).


Result is the resulting descriptor state (DESCR_XXX) and Status is the underlying solver's own return code (the latter is never interpreted by the Eclipse level code, it is just printed or passed to a user error handler).

Best and Worst are the best and worst bounds on the optimal objective value. See this for more description.


DumpOpt specifies if the problem should be dumped before solving. If it is to be dumped, DumpOpt is a structure write_before_solve(Format,File) specifying the dump format and file name. The problem will then be dumped before the external solver is invoked. In particular, if the external solver is invoked multiple times because of cutpool constraints, the problem is dumped for each invocation.


If there are no cutpool constraints, the external solver is invoked once to solve the problem. If there are cutpool constraints, the external solver can be invoked multiple times.  See here for more description of cutpool constraint related code in cplex_optimise().

The solution state is passed back to the ECLiPSe level by binding the correct field in the ECLiPSe handle problem structure.  The argument position of the field in the structure is giving by StateArrays: out(Sols, Pis, Slacks,Djs,ColBase,RowBase,Map), corresponding to the solutions,  dual solutions,  slack variables, reduced costs, column basis, row basis and condtional mapping arrays in the ECLiPSe Handle problem structure.  The Map array is not really a result, but a mapping for the cutpool raw index to the problem matrix (see  here ) If any of the other arrays are not required, their corresponding argument position in the Handle is left as a variable.  Otherwise, the corresponding values for the arrays are obtained from the solved problem. Note that values may be unavailable for some arrays if the problem is a mixed-integer type.

After solving the problem and extracting the state results,  the cutpool constraints are removed from the problem by resetting the problem matrix -- this must be done after all the required results are extracted, because in some solvers, results cannot be extracted after the matrix is changed in this way.
This restoration of the original problem is also done if  p_cpx_optimise need to be aborted.
The cutpool constraints are added and removed in this way to allow normal constraints to be added  to and removed from the problem in the normal way.

For Xpress, the problem is not post-solved when aborted (i.e. the problem was not solved to completion), for LP problems, the problem is postsolved after extracting any solution information from it, as otherwise the problem can no longer be modified. This is done via the undocumented XPRSpostsolve(), which is available for Xpress > 15 only.

• cplex_get_objval(+CPH,-Cost), p_cpx_get_objval

get the cost of the solution found.  This is now obtained from the problem descriptor field objval, which is set in  p_cpx_optimise.
 
• get_darray_element(+Darray,+I,-Value), p_get_darray_element

get element I of a darray
 
• darray_list(+Darray,+M,-List), p_darray_list

• darray_size(+Darray, -Size), p_darray_size

• get_iarray_element(+Iarray,+I,-Value), p_get_iarray_element

• set_iarray_element(+Iarray,+I,+Value), p_set_iarray_element

• iarray_list(+Iarray,-List), p_iarray_list

• iarray_size(+Iarray,-Size), p_iarray_size

• create_iarray(+Size,-Iarray), p_create_iarray

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.

Dealing with best and worst obj bounds

The way the bounds are determined depends on the optimisation method used and the status of the solve.

For LP/QP:

• no (primal/dual) feasible solution, e.g. phase 1 of two phase Simplex: no  information on bounds [According to Oliver Bastert of DASH, the primal and dual objective values can usually serve as bounds even if they are infesible, but there are degenerate cases where this is not true]
• primal  feasible, e.g. phase 2 of primal simplex, or have a primal feasible solution for barrier: there is a feasible solution, and it is a worst bound [the optimal objective is at least as good as our possibly suboptimal objective]
• dual feasible, e.g. phase 2 of dual simplex, or have a dual feasible solution for barrier: the dual `solution' is superoptimal for the original problem. The dual objective is a best bound on the optimal objective

• a (best) feasible integer solution is a worst bound on the optimal
• after finding a feasible integer solution, the MIP search will look for a better integer solution, defined by the feasible integer solution + a MIP tolerance. Thus, if an optimal is found, the best bound is the objective + MIP tolerance
• best bound is the  `worst' objective  value at any search-tree node. Both CPLEX and Xpress provide function calls to obtain this *if the MIP search (i.e. not counting the root node solve)  have started*
• if any node was `cut-off', i.e. not branched on because its objective is worse than the cut-off value, then if no solution is found, this objective is a best bound. Unfortunately, neither CPLEX and Xpress allow the user to determine if any node had been cutoff during the MIP search, so strictly a infeasible MIP state means that that no feasible solution better than the cut-off value exist, i.e.  the cut-off value is the best bound for an infeasible MIP.
• if MIP search was aborted at the root node:
• root node solve completed: objective is a best bound
• root node solve aborted: if primal feasible, objective is a best bound

The bounds are computed when the solution result is determined: this is because the same return code/statuses from the solver is needed to determine how to get the bounds, along with the exact method used to solve the problem.
From the return codes after solving the problem, several macros are defined for the various solvers, to determine the state:
 

SuccessState	solution is optimal (may be optimal within tolerance)
FailState	problem is proven infesible or (for MIP), no feasible solution exists that is better than cutoff
MIPSemiSuccessState	MIP only: solution exists, but may be suboptimal
MIPSemiFailState	MIP only: no solution found, but problme not proven infeasible
LPAbortedState	solve was aborted in solving an LP problem. Depending on solver, this may include the root node LP solve of a MIP probelm (for Xpress). For LP, we cannot determine if problem is in a semi-fail or semi-success state without looking at the solving method
UnboundedState	problem is unbounded
MaybeFailState	problem is either infeasible or unbounded, but solver cannot determine which

For each state, we determine the bounds and the actual status returned (DESC_SOLVED_SOL etc.). This requires the actual solving method used in the LP cases. For CPLEX, this can be obtained by calls to the solver, but for Xpress, we need to do this ourselves, by remembering the method used to call the solver, and figuring out what the `default' method maps to -- this may change between versions and need to be updated.

For FailState in MIP, the best bound is currently set to the cutoff. This is because there does not appear to be a way of determining if any search-tree node had been cutoff during the search, so there is no way of distinguishing `true' infeasibility (where no cutoff occurred).

The bounds are computed in all cases, even for failure cases, even though there is currently no way to make use of this information. A failure handler may be developed (this will only be useful if functionality is added to access the solvers information on causes for failures, e.g. IIS)
 

Retrieving problem data

• cplex_get_prob_param(+CPH,+Which,-Value), p_cpx_get_prob_param

retrieve handle-specific properties (problem type, last status) and statistics (size, counters)
• cplex_get_col_bounds(CPH, J, Lo, Hi), p_cpx_get_col_bounds

• cplex_get_col_type(CPH, J, TypeCode), p_cpx_get_col_type

• cplex_get_row(+CPH,+CType,+I,-Delta), p_cpx_get_row

prepare retrieval of row information for row I of constraint type CType: 0 for normal problem constraint, 1 for unconditional cut pool, 2 for conditional cut pool, Delta is the displacement into the row values arrays (rmatind, rmatval) for the start of the row.


• cplex_get_rhs(+CPH,+CType,+I,-SenseCode,-Rhs), p_cpx_get_rhs

get current rowof type CType's sense and right hand side


• cplex_get_col_coef(+CPH,+CType,+J,-Cij), p_cpx_get_col_coef

get coefficient of current row (of type CType), column J


• cplex_get_obj_coef(+CPH,+J,-C), p_cpx_get_obj_coef

get objective coefficient for column J

Other functions

• cplex_get_param(ParamName,Value), p_cpx_get_param

get a global parameter setting. The ParamName is an atom. The result type is implicit (float,integer,string). This uses the name mapping table in eplex_params.h
• cplex_set_param(ParamName,Value), p_cpx_set_param

set a global parameter. The ParamName is an atom. The required value type is determined by the parameter itself.
• cplex_lpwrite(File,Format,CPH,CPCondSet), p_cpx_lpwrite

write the problem in a prticular format to File. All active cutpool constraints are added to the problem first (see this ). These constraints are removed before returning from the call.


• cplex_lpread(File,Format,Handle), p_cpx_lpread

read a problem from a file using the external solver's problem reading routing. Various problem information, such as problem type and size, are read from the problem to set their values in the problem descriptor. For CPLEX, the optimisation sense (min or max) is read from the problem, but this is assumed to be minimse for MPS files, which does not include the optimisation sense. For Xpress, the optimisation sense is assumed to be minimisation for all problems, as it ignores the sense from the problem (the API requires the user to specify the sense when solving a problem).
Note that if the input file contain ranged constraints, these will be read in by the external solver correctly, but they cannot be extracted from the external solver correctly, as eplex does not support ranged constraint.


• cplex_lo_hi(NegInf,PosInf), p_cpx_lo_hi

returns the solver's idea of negative and positive infinity (something like 1e20)
 
• cplex_matrix_base(Base), p_cpx_matrix_base
• cplex_matrix_offset(Offset), p_cpx_matrix_offset

        |----|------------------------------------------|
        0       base                                                                              mac-1
        <---><---------------------------------------->
         offset             valid columns

• cplex_output_stream(ChannelNr,AddRem,StreamNr), p_cpx_output_stream

associate or disassociate a Cplex I/O channel (result_channel (0), error_channel(1), warning_channel(2), log_channel (3)) with the given Eclipse stream StreamNr. Xpress has a similar concept of 4 message levels

Undo functions

• _untrail_cleanup *non time-stamped*

• _cpx_reset_probtype *non time-stamped*

• _cpx_restore_bounds *non time-stamped*

• _cpx_reset_col_type *time-stamped*

• _cpx_del_rowcols *time-stamped*

Multiple handles

Memory allocation

Buffer Arrays

Various buffer arrays (defined as part of the solver handle) are used to store the problem at the C level before the data is passed to the external solver.  These arrays are show schematically below.  The arrays are used for the initial matrix (shown in green), and for later additions of rows and columns (shown in yellow).  The name of the array is shown in brackets.
 

objective coeffs (objx)		(objx)
col upper bounds (bdu)		(bdu)
col lower bounds (bdl)		(bdl)
Matrix  (matind, matval   matbeg, matcnt)		Added cols  (matind,matval   matbeg)		sense  (senx)		rhs  (rhs)
Added rows  (rmatind, rmatval, rmatbeg)				(rsense)		(rhs)

Cutpool Constraints

The cutpool constraints are stored in the row-wise representation used for CPLEX/XPRESS at the C-level.  They are maintained in the problem descriptor, and their names are:

• cp_rmatind2, cp_rmapval2, cp_rmapbeg2  - coefficients for the rows
• cp_rhsx2, cp_senx2  - RHS and sense for the rows
• cp_nr2 - the next row index (int)
• cp_nr_sz2 - size of cutpool row arrays (int)
  
• cp_nnz2 - the next nonzero index (int)
• cp_nz_sz2 - size of cutpool nz array (int)
  

• cp_active2 - the active state for each row (array of char, size cp_nr_sz2)
  
• cp_initial_add2 - the add_initially status for each row (array of char, size cp_nr_sz2)
  
• cp_npools2 - the number of used name groups (int)
  
• cp_pools2 -  an array of integer arrays, each integer array represent one named group. The entry in each array represents the raw index (into cp_rampbeg2) for one constraint in the group.
• cp_names2 - an array of strings. Each string is the name for the group. This is used to map the names into the index used in cp_pools2. The first entry (index 0) is treated specially, for the default group, which use the nil atom ([]), which is detected specially and not matched with the names.

Support for cutpool constraints in p_cpx_optimiseI

•   if there is a solution state (optimal or suboptimal), then the active cutpool constraints not yet added to the problem are checked to see if they are violated.  This is done with calls to _cstr_state(). Any violated constraints are added to the problem.
•   if there is no solution state, but the problem status is unknown or unbounded, then all unadded active cutpool constraints are added to the problem. _cstr_state() calls are also made with add_cp_cstr = 2, these are `dummy' calls that always cause the constraints to be added.

The cutpool constraints are added to a problem initially by calling:

_setup_initial_cp_constraints(lp_desc * lpd,  int add_all, int * unadded_cntp, int * cp_unadded, int * cp_map2)

This routine is called in p_cpx_optimise (add_all=0), and p_cpx_lpwrite (add_all=1).

_cstr_state(lp_desc * lpd, int nrow, char add_cp_cstr, double * sols)

• cplex_get_cutpool_size(+CPH,  -NRows, -NNzs), p_get_cutpool_size

returns the size (number of rows, number of non-zeros) of the cutpool CType.  This is called before constraints are added to the cutpool, so that the original
cutpool state can be restored if failure occurs while the constraints are added (e.g. because of an invalid constraint). The restoration is done by calling cplex_reset_cutpool_size.
 
• cplex_reset_cutpool_size(+CPH, +NRows, +NNzs), p_reset_cutpool_size

resets the cutpool to the size in NRows and NNzs.
 
• cplex_set_cpcstr_cond(+CPH,+RawIdx, +OType,+ActVal), p_set_cpcstr_defaults

sets the cutpool option OType to the value ActVal for the cutpool constraint with the cutpool raw index RawIdx.


• cplex_init_cpcstr(+CPH, +RawIdx, +GrpIdx, +Active,+AddInit), p_init_cpcstr

initialise the cutpool constraint specific data of a  new constraint with raw index RawIdx. The constraint must already have been added to the cutpool.  This routine add the group information (adding its index to cp_pools2[GrpIdx] etc.), and sets the active and add_initially status.
 
• cplex_get_named_cp_index(+CPH, +Name, +OptSet, -GrpIdx), p_cpx_get_named_cp_index

get the GrpIdx for a named group with name Name.  This creates and set a new named group if OptSet is 1.  Otherwise, failure occurs if Name does not exist. The default group ([]) is treated specially, and is always created if it does not already exist. It is also tested for with test for nil atom rather than a name match. The default group is only created when needed to avoid the overhead when conditional cut pools are not used.
 
• cplex_get_named_cpcstr_indices(+CPH, +GrpIdx, -RawIdxs), p_cpx_get_named_cpcstr_indices

returns all the raw indexes for the named group represented by GrpIdx.
 

COIN/OSI solvers

• declare the call (with prefix "coin_") with the rest of the coinplex procedure declarations, with the types for the arguments, in seplex.h. Data contructs which are C++ specific (such as the COINprob *) should be passed as void pointers (and in C++ used as pointers to the data contructs), and should not be used at all in seplex.c.
  
• if the call is used within code that is shared with CPLEX/XPRESS, the macro transformation of the code into the coinplex procedure should be defined (with the rest of the COIN-specific macro transformations)

• write the code (in C++) for the procedure. The arguments for the procedure must be compatible with its declaration in seplex.c.
  
• the procedure should be prefixed by the `extern "C"'  declaration, to make it visible externally.
  

Problem descriptor

Solver specific Information

• OSI does not provide much control over MIP solving. The default  coin_branchAndBound() call OSI's branchAndBound().  Solver specific coin_branchAndBound() can provide more control over the MIP solving.
  
• OSI does not support the setting of solving methods beyond if a primal or dual method  should be used. coin_solveLinear() allow solver specific solving methods (such as interior point methods) to be used.
• Timeouts are not supported. coin_set_timeout() allows solver specific methods of setting timeout.
• OSI is not very good at determining semi-fail or semi-success state when a problem solve is aborted, and the unknown result  status  have to be returned. Solver specific  code can be added  to coin_get_result_state()  to better determine the result status.
• Obtaining best and worst objective value bounds is also  very solver specific. The default non-solver specific return value is the `infinity' value of the right sign.
  
• OSI supports only a small set of solver parameters. Solver specific parameters are supported via coin_set/get_*param() routines. See here for more detail.
  
• SOS (Special Order Sets) are not supported. coin_load_sos() allows solver specific support for SOS.
  

• mipmodel is a ClpModel* in COINprob for supporting specialised MIP code in coin_branchAndBound(). The code is largely taken from sample2 example driver for Cbc
  
• Cbc fixes bounds of some variables to their potential solution value during MIP presolve and solve. These bounds have to be undone after the probelm solve to allow the problem to be correctly resolved. This is done by copying the bounds before doing the presolve, and restore these bounds before exiting coin_branchAndBound().
  
• the method CbcModel  isContinuousUnbounded() method is used in  coin_get_result_state(), this method is currently (Nov 2006) only available on the trunk and development branches of Cbc, and not in the stable branch. 
• 
  

API between seplex.c and coinplex.cpp

• int coin_get_objsen(COINprob * lp)

• int coin_get_numcols(COINprob* lp)

• int coin_get_numrows(COINprob* lp)

• int coin_get_probtype(COINprob* lp)

• int coin_getrhs(COINprob * lp, double *rhs, int start, int end)

• int coin_getrowsense(COINprob * lp, char *rsense, int start, int end)

• int coin_getlb(COINprob * lp, double *lb, int start, int end)

• int coin_getub(COINprob * lp, double *ub, int start, int end)

• int coin_getcoltype(COINprob * lp, char *ctype, int start, int end)

returns in ctype the types of columns from start to end. ctype should be pointing at a char array of at least end-start elements. Returns -1 if error

• int coin_chgcoltype(COINprob * lp, int cnt, int *idxs, char *ctype)

• int coin_chgbds(COINprob * lp, int cnt, int * idxs, char * lu, double *bd)

• int coin_loadbasis(COINprob * lp, int *cbase, int *rbase)

• int coin_getbasis(COINprob * lp, int *cbase, int *rbase)

• int coin_get_lpobjval(COINprob * lp, double * objvalp)

• int coin_get_mipobjval(COINprob * lp, double * objvalp)

• int coin_get_bestmipbound(COINprob * lp, double * bound)

• int coin_get_objcoeffs(COINprob * lp, double *objc, int start, int end)

• int coin_chg_objcoeffs(COINprob * lp, int cnt, int * idxs, double * values)

• int coin_get_order(COINprob * lp, int cnt, int * idxs, int * prio, int * direction)

• int coin_chgqobj(COINprob * lp, int i, int j, double value)

• int coin_chgrhs(COINprob * lp, int cnt, int * idxs, double * values)

• int coin_loadprob(COINprob* lp, int mac, int mar, int objsen, double* objx, double* rhsx, char* senx, int * matbeg, int* matcnt, int* matind, double* matval,double* lb, double* ub)

• int coin_setcoltype(COINprob* lp, char *ctype)

• int coin_addcols(COINprob* lp, int coladded, int matnz, double* objx, int* matbeg, int* matind, double* matval, double* bdl, double* bdu)

• int coin_addrows(COINprob* lp, int rowadded, int nzadded, double* rhsx, char* senxm int* rmatbeg, int* rmatind, double* rmatval)

• int coin_chgobjsen(COINprob* lp, int objsen)

• int coin_get_row(COINprob* lp, int* nnz, int* rmatind, double* rmatval, int idx)

• int coin_delrows(COINprob* lp, int ndr, int* idx)

• int coin_delcols(COINprob* lp, int ndr, int* idx)

delete ndr columns from the problem, with indices specified in idx.

• int coin_get_bar_primal_objval(COINprob* lp, double* objval)

• int coin_get_bar_dual_objval(COINprob* lp, double* objval)

• state_t coin_get_result_state(lp_desc* lpd)

• int coin_get_mipcutoff(COINprob* lp, double* bestbound)

• double coin_infinity(COINprob* lp)

• int coin_getdblparam(COINprob* lp, int key, double* value)

• int coin_getintparam(COINprob* lp, int key, int* value)

• int coin_setdblparam(COINprob* lp, int key, double value)

• int coin_setintparam(COINprob* lp, int key, int value)

• int coin_get_solver_dblparam(COINprob* lp, int key, double* value)

• int coin_get_solver_intparam(COINprob* lp, int key, int* value)

• int coin_set_solver_dblparam(COINprob* lp, int key, double value)

• int coin_set_solver_intparam(COINprob* lp, int key, int value)

• int coin_solve_problem(lp_desc* lpd, int meth, int auxmeth, int node_meth, int node_auxmeth)

• int coin_get_stats(lp_desc* lpd)

• int coin_get_soln_state(lp_desc* lpd, double* sols, double* pis, double* slacks, double* djs, int* cbase, int* rbase)

• int coin_set_timeout(COINprob* lp, double timeout)

• int coin_create_prob(COINprob** lp)

• int coin_reset_prob(lp_desc* lpd)

• int coin_writeprob(COINprob* lp, char* file, char* otype)

• int coin_readprob(COINprob* lp, char* file, char* otype)

• int coin_getnumnz(COINprob* lp)

• int coin_getnumint(COINprob* lp)

• int coin_get_dual_infeas(COINprob* lp, int* infeas)

• int coin_get_primal_infeas(COINprob* lp, int* infeas)

Global Parameters

Cplex's CPX_PARAM_NODELIM becomes nodelim
Xpress's MAXNOD or N_MAXNOD becomes maxnod

Solver Numerical Differences

Debugging the External Solver

In order to report a problem to Dash or ILOG or COIN, we need to show that the problem
is due to their external solver. Several methods are available to do this:

• if the problem occur while the external solver is solving a problem, the problem state can be saved before it is solved by the external solver. If the problem also occurs when the saved problem is loaded back into (an interactive) session of the solver, then the saved problem can be used in the bug report. Eplex supports the saving of a problem before solving it with the option write_before_solve when the problem is setup.  The problem is written using as high a precision as possible when written as lp or mps format. However, sometimes the problem may not occur with these formats, but would occur when written using the binary format. The disadvantage of the binary format is that it is solver and platform specific, and is non human-readable.
• log the external solver calls by eplex. See next section for more details.

Logging External Solver Calls

Structure of the log code

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 seplex.h, which is for both normal and logged code, with the logged code compiled with a -DNOECLIPSE flag.
 

The include file has the following support variables (with the NOECLIPSE flag):

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

• Call(Ret, Proc):  Generates a call to Proc in the form Ret = Proc, and a log for Proc if LOG_CALLS is defined.
• CallN(Proc): Generates a call to Proc in the form Proc, and a log for Proc if LOG_CALLS is defined. This should be used if Proc should be called without getting the return code.
• Log0(Proc): Generate a log for Proc if LOG_CALLS is defined. No actual call is generated, so seperate code for the call is needed. This macro should be used instead of Call or CallN in case where the actual calls are in places where logging  cannot be done, or for code that is for the logging only, and not in the actual eplex code.
  
• Log1(Proc, A1): Generates a log for Proc if LOG_CALLS is defined. No actual call is generated, so seperate code for the call is needed. This macro should be used when an argument for Proc needs to be supplied dynamically at run-time. Proc can be written in printf style with a leading % for the argument supplied in A1.
• Log2(Proc, A1, A2): Same as Log1, except it allows two dynamic arguments.
• Log3(Proc, A1, A2, A3): Same as Log1, except it allows three dynamic arguments.
• Log4(Proc, A1, A2, A3, A4): Same as Log1, except it allows four dynamic arguments.

• Log5(Proc,A1,A2,A3,A4,A5): Same as Log1, except it allows five dynamic arguments.
• Log6(Proc,A1,A2,A3,A4,A5,A6): Same as Log1, except it allows six dynamic arguments.

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.