Implementation Notes for lib(eplex), in ECLiPSe 5.10
Author: Joachim, Kish
Date: Nov 2006
Revision history: July 2003: Taken from lib(eplex) implementation notes
(5.6), revised Jan 2004 (5.7), Jan 2005 (5.8), Feb 2005 (5.9), July
2005
(5.9), May 2006 (5.9), Aug 2006 (Osi),
Nov 2006 (5.10)
Contents:
#Introdcution
#Global structure
#Eclipse Code Level
#C Code Level
Global structure
Files
The bulk of the code are in eplex_s.ecl and seplex.c.
Components:
- 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)
Related:
- lib(linearize): used to linearize arithmetic expressions
- lib(var_name): provides stable variable name support
- lib(constraint_pools): support for eplex instances
Modules
eplex_s.ecl contains two modules eplex and eplex_s.
Most
of the code is in eplex_ s and reexported through eplex. The reason to
have eplex_ s at all is that eplex redefines the arithmetic predicates
(>, >=, ...) which would be inconvenient to have in the actual
implementation
module.
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
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_s.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 more than one solver are available on a particular host, the
selected
solver is
- 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.
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.
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
Eplex variables have the following 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 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 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
]).
In general, the attribute handlers have to handle every single
attribute
structure in the chain. The attribute print handler prints the range
and
lp solutions (if it exists) of all the attribute structures in
the
chain(using the solver/idx fields in the attribute). The unify handler
is responsible for:
- 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
What we call a problem in the following consists of
- 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
Multiple problems are supported by eplex, each problem having its own
handles.We
have problem handles on several levels:
- Eclipse level: this is an Eclipse structure (struct
prob
), its fields are backtracked, the first field refers to the C level
descriptor
- C level: this is a C structure (struct lp_desc),
its
fields
are non-backtracked, it refers among others to the solver state
descriptor
- 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, % 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 _)
)
).
The vars list keeps a reference to all the variables involved
in
the problem. The variables in the list are in reverse coluumn order
(i.e.
first column at the tail of the list). 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 cutpool constraints
Cutpool constraints (`global cuts') are supported from version 5.9. The
support is mainly at the C level, where the cutpool constraints are
stored. The solving process is also mdified from previously, as a call
to the external solver can now result in multiple invocations of the
external solver. See here for the ECLiPSe level
descriptions, and here for the C level
descriptions.
Support for column generation
The column generation library uses the eplex library. The
main
support provided by eplex for column generation are:
- 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
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:
- solver has global parameters: acess to global parameters in eplex
directly
accesses the corresponding solver parameter.
- 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.
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
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.
Bounds constraints
These can be posted either as =:=, >= or =< constraints with a
single
variable, or with the ::/2 constraint (the ::/2 constraint
can be posted to an eplex instance only).
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
When two problem variables for the same problem instance are unified,
their
attributes are merged, so that the columns represented by the two
original
attributes is now represented by one attribute. One of the
attribute is maintained in the merged variable, while information from
the other attribute is merged into it. The following are done for the
merging:
- 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
One general design decision that was made is the treatment of any
existing
solution state information when two problem variables are merged: the
existing
solution is no longer valid because the problem is changed. The two
alternatives
are
- Retain the old state, with the definition that the state
information is
the information available from the (logically) last solve of the
problem
- 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
We implemented policy 1, as the state will be available as long as
possible
(until the solver is next called), and obtaining the state information
for probing fits into this notion of the state easily. Also, as
unification
of two problem variables can be done by some other solver, it would be
difficult for the user to know exactly when the state information might
be cleared. This retaning the solution state is now made
consisitent
when we modify the problem by adding constraints - the state is no
longer
cleared. Previously, the state is selectively cleared in some
situation.
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
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:
- storage for constraints
- predicates to set up and trigger solver state
- associated external solver state (if one has been setup)
Storage for constraints
This is implemented using lib(constraint_pools), with each eplex
instance
having an associated constraint pool. With standalone eplex,
constraints
are only stored in the pools before an external solver solver is set up
for the instance. After setup, posted constraints are immediately added
to the external solver. To make this more efficient, the vars
field of the problem handle was changed from a structure to a list.
If the added constraints contain new variables, these needed to be
added to the problem, and previously a new vars structure has to be
created
and the old variables copied to it.
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:
- the constraint gets normalised
- if ground, solve it now, i.e. check if satisfied
- before solver setup:
- add the normalised form to the linear constraint type of the
constraint
pool.
- 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.
integers/1 is handled by
- extract the variables into a list, eliminating ground integers
- 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:
- extract the variables into a list, eliminating ground integers
- 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)
- 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.
::/2 is handled by:
- fail if the the lower bound is greater than the upper bound
- extract the variables into a list
- 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:
- Determine which of the variables on the LHS are new (i.e. not
already
in
the solver state). New columns for these.
- 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).
- if any new bounds were imposed, trigger the bd_trigger suspension
list
of the problem
Thus before solver setup, 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
this
only applies to constraints posted before solver setup, because after
setup,
the constraints are added to the external solver immediately, and 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_s with the eplex instance name as an argument. All
the real work is done by the predicates in the eplex_s 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_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
In turn, the eplex_* predicates in eplex_s.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
- a list of already normalised constraints (equalities and
inequalities)
- an objective expression (linear or quadratic)
- a list of integer variables (within the option list)
- 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.
- 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 problem type can change into another problem type after problem
setup:
- 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.
Pseudocode:
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()
As from 5.7, an external solver state is always setup, even for an
empty
problem.
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
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.
Pseudocode:
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)
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 |
event(eplex_suboptimal) |
success |
DESCR_ABORTED_NOSOL |
no solution was found, but there may be one |
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. [Note CPlex 8 can properly handle
infeasible/unbounded
for primal/dual problems]
optimize
Optimize (the black-box solver) is a simple sequence of
- collecting the pending constraints (equalities, inequalities and
eplex:integers/1)
- setting up a solver
- run the solver
- unifying the resulting cost
- retrieving the solutions and unifying them with the variables
- 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:
- setting up a solver
- create the lp_demon suspension
- insert the suspension into the suspend field of the handle
- run the solver once if initial_solve option is yes
- calling the post-goal (see user documentation)
- bounding the Cost variable (using the generic set_var_bounds/3)
Note that if the Cost variable does not have some bounds attribute, it
would not be bounded by step 6. The actual solution value can still be
extracted in this case.
When the lp_demon is woken subsequently, it performs:
- calling the pre-goal
- run the solver again
- calling the post-goal
- bounding the Cost variable
Triggering the demon:
Trigger condition |
Implementation |
inst |
insert in all variable's (inst of suspend) lists |
bounds |
bd_trigger field of ECLiPSe handle for probelm is set to
bounds.
When a problem variable's bound is updated, eplex checks if bd_trigger
is set to bounds, and if so, triggers the demon explicitly if the
bounds
changed. The demon is also triggered during when columns are merged,
and
the bounds are changed by the merging (the column merge code
checks
to see if the demon has already been triggered by new_constraints, so
that
the demon is triggered only once) |
deviating_inst |
insert in all variable's (intol_inst of eplex) lists |
deviating_bounds |
bd_trigger field of ECLiPSe handle for problem is set to
deviating_bounds.
When a problem variable's bound is updated, eplex checks if
bd_trigger
is set to deviating_bounds, and if so, triggers the demon
explicitly
if the variable's solution value fall outside the new bounds by a
tolerance.
Merging of columns does NOT trigger the demon, as the solution values
in
the columns is no longer valid for the changed problem. |
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). The demon is also triggered when an equality
constraint
is posted when columns are merged |
trigger(atom) |
attach to a global trigger |
suspension(S) |
returns the demon suspension in S. The user can
then write
their own code for triggering the demon. For example, this allows the
user
to select specific variables to suspend the demon on. |
lp_add
lp_add add linear or integer constraints 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.
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:
- renormalise_and_check_simple:
Renormalise
any new linear constraints
- lp_add_normalised: Add
the
new
(normalised) constraints/variables to the problem
- var_triggers: Add the
new
variables
to the triggers
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
Adds the normalised constraints to the solver. It also returns a lists
that give the row indicies in the solver
matrix for the added constraints. No checks are performed on
the constraints: they are assumed to have
been checked previously (e.g. by renormalise_and_check_simple).
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
Note that unlike the bounds keeper eplex, there
are no non-problem variables.
This is because after solver setup, all constraints (linear, integer,
bounds)
are immediately added to the solver state (by lp_add implicitly) when
they
are posted.
The steps performed by lp_add are:
- If problem not yet initialised (no variables/constraints set up
yet),
initialise
it
- 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.
- 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)
- Pass the data on the new rows to the C level buffer arrays
(setup_new_rows)
- Call the C level predicate to flush the new data in the buffer
arrays
to
the external solver (cplex_flush_new_rowcols)
- 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/3
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
(only in 5.8 development branch: and new constraints
were posted that might possibly change the problem (i.e. new
arithematic
constraints, integer constraints on existing variables (`old
integers')).
lp_add_constraints/4
This is the user accessible interface to implementing column
generation.
Constraints are normalised (and not simplified), and checked to
make
sure that none are ground: an error is raised otherwise. It then
essentially call lp_add, but unlike lp_add_constraints/3, the row
indicies
are returned. Note also that adding constraints using this
predicate
will not trigger the external solver.
lp_add_columns/3
This is used by the column generation library (and in addition is
accessable
by the user) to add possibly non-empty columns to the solver's matrix.
The column information is specified by a list of pairs of Var:ColInfo,
where Var is the variable representing the new column, and ColInfo is a
list of Idx:Value pair, where Idx is either obj for the objective, or a
integer specifying the row number, and Value is the corresponding
coefficient.
All unspecified row/objective coefficients are taken to be zero.
The steps performed are:
- extract the indivdual column data into the format required
(separate
lists
for the objectives, row coefficients, etc., number of non-zero
coefficents,
etc.). Index each new column with a new column index by calling
set_var_index:
this creates a new eplex attribute for the variable representing the
column
and add the index to it.
- pass the extracted data to the C level buffer arrays with
setup_new_cols
- flush the data from the buffer arrays to the solver state with
cplex_flush_new_rowcols
- If var_names option is set, pass any variable names for
the new
varaibles
to the solver state.
- extend the basis by retaining the last basis and giving 0 to the
new
columns
In 5.7, the amount of code sharing between the various predicates
that add data to the external solver was increased: set_var_index is
used
to setup a new variable's column index in its attribute. setup_new_cols
is used to pass the new problem data in column-wise format (for
existing
rows) to the C level buffer arrays (expanding the buffer arrays if
necessary
in C), and cplex_flush_new_rowcols is used to pass C level data to the
solver. set_var_index was separated out from setup_new_cols to minimize
the number of traversal of the list of new variables.
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
These are called when the linear constraints (=:=, >=, =< and
their
$ equivalents, respectively) are posted to an eplex instance. The
actiions performed are described here.
lp_impose_interval
This is called when bounds constraints (::, $::) are posted to an eplex
instance. Type checking (integer/real/don't care) may be done.
Variables
are extracted from the LHS (wuth subscript being a special case), and
the
interval from the RHS. The actions performed are described here.
integers
This is called when integers constraints are posted to an eplex
instance.
The argument is a list of variables or integers. Type check is
performed,
and for the variables, the action performed are described here.
(5.8 development branch: the solver is invoked if the nc_trigger
field is set to yes, and the integers constraint was applied to
existing
variables ('old integers')).
lp_read, lp_write
lp_write is a simple wrapper around the C level cplex_lpwrite call.
lp_read does:
- 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]
the quadratic objective in the problem handle is used to set and reset
the quadratic objective during an objective probe only, so the
quadratic objective will not be cleared without the quadratic objective
coefficients.
lp_probe
lp_probe teomprarily modifies a problem and solves it, reutrning the
problem
to the original, unmodified, state upon exiting. The code is
strcutred
as:
lp_probe:
extract the probes from the
specifications
modify Handle's problem as specified
by
the
probes
invoke lp_solve on Handle
restore Handle's problem back to the
original
one
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.
The priority is needed in setting the probe because some probes need to
be set/unset before others. For example, CPLEX does not allowed a fixed
problem to be further modified, so this probe must be set last (and
unset
first). Currently only two priorities are used: 1 and 3.
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
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.
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.
Cutpool constraints
Cutpools implement the functionality of global constraints/cutpools,
needed for techniques such as cut generation. It provides the following
functionality:
- 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.
Each time the problem is solved, the cutpool constraints are appended
selectively to the end of the problem matrix. Only active
constraints which are either labelled as add_initially or are violated
by an intermediate solve are added to the matrix. The problem
matrix's constraints (rows) can be classified as
- 'Normal' problem constraints
- cutpool constraints - this consists of all the added cutpool
constraints
The number of `normal' constraints is stored in the mr field of the Eclipse
handle. F
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.
these status are mapped to their
numeric value by the predicate cp_cstr_state_code/2, which should also
correspond to the C level numeric values for these Map values (defined
by the macros CSTR_STATE_*)
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
add constraints to cutpools respectively. Options allow the active and
add_initially status to be specified (both can be changed later on), as
well as a named group for the 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
these are used to get information for cutpool constraints
(cutpool_info),
and to change coptions for cutpool constraints (cutpool_option),
and also to create new named groups (cutpool_name). Setting the options
is effective immeidately, and is non-logical (i.e. it is not undone on
backtracking).
Predicates affected by cutpool constraints:
lp_write
the problem that is dumped includes all the active cutpool constraints
cplex_optimise
if there are cutpool constraints, the external solver can be invoked
multiple times. As cplex_optimise is the C-level interface predicate
for solving a problem, this affects all user level problem solving
predicates like lp_solve, lp_proble. The write_before_solve option now
dumps the problem at the C level rather than call lp_write. This ensure
that the problem is dumped for each invocation of the solver.
C Code Level
Versions
The C code needs to be compiled separately for every version of the
Cplex
or Xpress solver , and every solver interfaced trhough OSI that we want
to support. The makefile builds
differently
named shared libraries from the single eplex.c source file, e.g.
- 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)
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.
For OSI, the `version' information is used to give the actual solver
(or combination of solvers) interfaced through OSI. Currently we do not
provide separate interfaces to different versions of these solvers,
because the COIN solvers do not have a very clearly defined concept of
version, as the source is constantly updated.
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 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
The descriptor has a state which is either one of the solution states
described
under lp_solve/2, or
- DESCR_LOADED during setup, no solve attempted yet
- DESCR_EMPTY after cleanup
Initialization and finalization
Two C externals are provided for initialise and finalise the whole
subsystem,
essentially this means dealing with the licences:
- 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
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/Osi
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:
- 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
set constraint
sense
and right hand side for constraint row I.
- 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
Initialise the bounds for a new column J in the external
solver
to Lo..Hi. This should be used only for setting the initial bounds of a
column (during setup and also when a new column is added). This is
because
no undo function is setup to restore a previous bound. For modification
of existing bounds of a column, use the cplex_impose_col_* family of
functions
instead.
- cplex_new_col_bound(CPH,Cj,Bd,Which),p_cpx_new_col_bound
This is for the special case of updating the Which bound
(<0:
lower, 0: both, >0: upper) of column J that has been initialised,
but the
new bound(s) does not need to be backtracked, so there is no need to
use
the cplex_impose_col_* functions. This occurs for example when bound
constraints
were posted to a problem before solver setup. A column's bound would
initially
be initialised with cplex_init_new_col_bounds(), but the bound(s) can
then
be updated by the bound constraint(s) during solver setup.
- cplex_set_var_name(CPH, Cj, Name), p_cpx_set_var_name
set the name for
the variable column J in the external solver. This name will
be used when
the external solver prints the problem.
- 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
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:
- 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
try to impose the bounds Lo..Hi on column J. Fail if
the interval for the column becomes empty after the bounds change. If
Flag
is 1, both new bounds are only imposed (passed to the external solver)
if the new bound is more narrow. If Flag is 0, the new bounds are not
checked
against the existing bounds (this is only used by external libraries,
not
by eplex). If either bound is imposed, an undo function
_cpx_restore_bounds
is trailed using the Attr's timestamp. Because of the time stamp, the
function
can be trailed at most once, and it restores both bounds, regardless of
which was changed. Also, because it uses the Attr as the time stamp,
the
column number must stay the same for the same Attri - this is the first
column in the column index list.
Handle is needed during the execution of the undo function to obtain
the CPH. Changed is set to 1 if either bound was changed. This is
needed at the Prolog level, e.g. to schedule the demon solver because
the
bound has changed. Note this can be used to impose bounds on a newly
added
column which has not yet been passed to the external solver. In this
case,
it is regarded as initialising the column's bounds, no undo function is
trailed, and Changed is set to 0.
- cplex_impose_col_lwb(Handle,
Attr, J, Lo, Changed),
p_cpx_impose_col_lwb
try to impose the lower bound Lo on column J. Fail if the
interval
for the column becomes empty after the bound change. Lo is only imposed
(passed to the external solver) if it is greater than the current lower
bound. In this case, an undo function _cpx_restore_bounds is
trailed
using the Attr's timestamp, which restores both bounds, regardless of
which
was changed. Changed is set to 1 if the bound was changed. This
is
needed at the Prolog level, e.g. to schedule the demon solver because
the
bound has changed.
- cplex_impose_col_upb(Handle,
Attr, J, Hi, Changed),
p_cpx_impose_col_upb
try to impose the upper bound Hi on column J. Fail if the
interval
for the column becomes empty after the bound change. Hi is only imposed
(passed to the external solver) if it is less than the current upper
bound.
In this case, an undo function _cpx_restore_bounds is trailed
using
the Attr's timestamp, which restores both bounds, regardless of which
was
changed. Changed is set to 1 if the bound was changed. This is
needed
at the Prolog level, e.g. to schedule the demon solver because the
bound
has changed.
- 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.
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 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
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.
Problem solving and result retrieval
Running the solver is always done with cplex_optimise, regardless of
the
problem type or the solver method used.
- 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.
There is one function to return the objective value:
- 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
convert the first M entries of a darray to a list of
doubles,
returns an out of range error if array size < M. M is
there
so that irrelevant data at the end of the array (e.g. the rows
generated
for cut pool constraints in the row results array) can be omitted.
- darray_size(+Darray, -Size), p_darray_size
get the size (number of elements) of a darray
- get_iarray_element(+Iarray,+I,-Value), p_get_iarray_element
get element I of an iarray
- set_iarray_element(+Iarray,+I,+Value), p_set_iarray_element
set element I of an iarray
- iarray_list(+Iarray,-List), p_iarray_list
convert an iarray to a list of integers
- iarray_size(+Iarray,-Size), p_iarray_size
get the size (number of elements) of an
iarray
- create_iarray(+Size,-Iarray), p_create_iarray
create an iarray of size Size.
A darray (iarray) is actually an Eclipse string, but it contains
doubles
(integers) 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.
Dealing with best and worst obj bounds
After invoking the solver, p_cpx_optimise determines the best and worst
bounds on the objective value, regardless of the status of the solve.
We
use best/worst bounds so that we don't need to worry about the
optimisation
direction when computing these bounds: for minimisation, best bound is
the lower bound, and worst bound the upper bound.
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
For MIP:
- 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 tightest of the valid bounds are used.
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
These are non-essential functions, used to retrieve information from
the
C level handle:
- 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
get the column bounds Lo..Hi for column
J.
- cplex_get_col_type(CPH, J,
TypeCode),
p_cpx_get_col_type
get the column type for the column
J.
TypeCode is one of the ASCII code B, I or J.
- 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
these two functions are used for specifying the valid
column
values in the external solver. These are fixed for a particular solver,
but can be different between solvers. base is the index for the first
valid
column (this can generally be 0 or 1), offset is the offset this value
is from 0, the start of C arrays. Strictly speaking offset is not
needed
but can be calculated from base. The two functions are provided to
avoid
this calculation at runtime at the ECLiPSe level.
|----|------------------------------------------|
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
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).
- _untrail_cleanup *non
time-stamped*
calls p_cpx_cleanup, and then free the
problem descriptor. Trailed during p_cpx_prob_init so problem space can
be freed upon backtracking
- _cpx_reset_probtype *non
time-stamped*
reset a problem type to a non-integer
type
(LP or QP). CPLEX has to be informed of the changed as well (but
not XPRESS). Trailed when problem is changed from a non-integer
to
mixed-integer problem type.
- _cpx_restore_bounds *non
time-stamped*
restore both bounds of a column.
Trailed
when either the upper or lower (or both) bound of a column was changed.
The untrail data contains the column's number and the original
bounds.
This function is not time-stamped because each column can only
change
type at most twice (C -> I -> B).
- _cpx_reset_col_type *time-stamped*
change a column back to its original
type.
Trailed when a column type is changed in p_cpx_change_col_type. The
untrail
data contains the column's number and the original type.
- _cpx_del_rowcols *time-stamped*
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.
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!
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Matrix
(matind, matval
matbeg, matcnt) |
|
|
Added
cols
(matind,matval
matbeg) |
|
|
|
|
|
|
Added
rows
(rmatind, rmatval, rmatbeg) |
|
|
|
|
|
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)
In addition, the conditional cut pool matrix has extra structures to
manage
the named groups and default status:
- 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
In cplex_optimise(), if there are cutpool constraints (lpd->cp_nr2
> 0), then:
1. Any active cutpool constraints with the add_initially
status are added to the problem matrix by _setup_initial_cp_constraints().
This is done at the start of cplex_optimise()
2. The solver is invoked inside a loop, and after
determining the status of the solution and solution state if available:
- 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.
3. If any cutpool constraints have been added to the
problem, invoke the solver again (step 2).
The violation check is done by looping through the cp_unadded array,
which hold information on the unadded cutpool constraints. This array
is initialised by the call to _setup_initial_cp_constraints() so that
initially the successive elements contains the raw index of the unadded
constraints, e.g. if there are 6 cutpool constraints, and constraints 0
and 2 are added initially to the matrix, then cp_unadded will be
initialised to {1,3,4,5}, i.e. constraints 1,3,4 and 5 are not yet
added.
On looping through the cp_unadded array, _cstr_state() is called to
check if the constraint is violated. If it is, it is added to the
problem matrix. The cp_unadded array is modified to reflect this change
by allowing the next cycle of solver invocation/checking constraints to
skip over these added constraints. This is done by changing the first
added constraint in a consecutive block of added constraints to a
negative number representing the displacement to the next unadded
constraint, e.g. for the above example, if constraints 2 and 3 are
added, then the cp_unadded array is changed to {1,-2,_,5}, i.e.
constraints 1 and 5 are still unadded, but the -2 in cp_unadded[1] will
cause the check to skip the block of added constraints from this cycle.
Note that because the block is skipped, the value for cp_unadded[2] is
no longer important (so it is represented by _).
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)
set up and add the initial cutpool constraints to the problem
represented
by the problem descriptor lpd. If add_all is 0, then the active cutpool
constraints with the add_initially status set (in cp_initial_add2
array) are added to the problem. If add_all is 1, then all active
cutpool constraints are added to the problem.
unadded_cntp is a pointer to the counter of number of unadded active
cutpool constraints constraints. This is set by the procedure.
cp_unadded is an array of the indexes of the unadded constraints.
This must be created before calling the procedure, and is currently
conservatively given the size of the number of cutpool constraints.
cp_map2 is an array mapping all the cutpool constraints to how they are
used. This is eventually returned to the user by p_cpx_optimise().
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)
check and return the state of the cutpool constraint with raw index
nrow (row nrow in the cutpool matrix). The return states are:
CSTR_STATE_VIOLATED - constraint
is violated
CSTR_STATE_BINDING - constraint is satisfied and binding
CSTR_STATE_SAT - constraint is satisfied but not binding
CSTR_STATE_INVALID - error with constraint (e.g. a unsupported
constraint type)
sols is the solution values array for the last solved problem. The
solution values are used with the column coefficients of the
constraint to calculate the lhs , and this is compared with the
rhs to see if the constraint is violated/binding/satisfied.
A binding constraint is a constraint which is satisfied, and the lhs
and rhs values are equal within the feasibility tolerance -- the
external solver's feasibility tolerance parameter value is used for
this test.
add_cp_cstr is a state variable used by the parent procedure
p_cpx_optimise(). In p_cpx_optimise() it specifies if adding
cutpool constraint should be considered for this external solver
invocation or not (== 0 for not adding cutpool constraint, > 0 for
adding cutpool constraint). _cstr_state() should only be called with
add_cp_cstr > 0. Normally, add_cp_cstr == 1, and the state checking
is done. However, if the last solved state is unbounded or unknown,
_cstr_state() is called with add_cp_cstr == 2, and no checking is done
in this case, and DESCR_STATE_VIOLATED is returned to force the adding
of the constraint. This is done to allow the same code to be used for
both both the normal and the unbonded/unknown case for checking and
adding constraints.
The following routines are called from the ECLiPSe level:
- 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
The COIN/OSI
interface is organised as follow:
_______________________________
_______________ |
____________|______
________ V
|
| |
|
| | |
--> CBC
| seplex.c | --|-> |
coinplex.cpp | --> | OSI |
--> CLP
|______________| |
|__________________| |_______|
--> SYMPHONY
|
--> ,,,
C
C++
coinplex.cpp effectively provides the solver API as used previously:
where eplex call XPRESS/CPLEX C API routines, it calls routines in
coinplex instead. The code in coinplex.cpp then calls OSI, which can be
interfaced to different solvers, or combination of solvers (such as CLP
as the linear solver, and CBC for MIP solver). The normal usage is
to use the appropriate OsiXxxSolverInterface, where Xxx is the solver
specific interface,
and coinplex.cpp is compiled with -DCOIN_USE_XXX
flag, with #ifdef COIN_USE_XXX macros
to
specify any solver specific code.
In the case of solver specific code, coinplex would make direct calls
to the solver, e.g. CBC as shown in the figure above. Solver
specific code is needed because the required feature is not supported
by the OSI API (e.g. timeouts), or the specific solver provide better
support for the feature (e.g. branch and bound in CBC).
To maximise the amount of shared code, the routines defined in the
coinplex API mimic those in CPLEX/XPRESS API as much as possible, so
that the same code can be used for the various solvers, with macros
mapping the CPLEX or XPRESS routine names to coinplex equivalent.
The coinplex.cpp routines that are to be called by seplex.c are
listed here. To define a new call for
the API:
in seplex.c/h:
- 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)
in coinplex.cpp:
- 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.
The C to coinplex API in seplex.h is only needed by the C code, and is
compiled with the -DC_TO_COIN flag
for C code (seplex.c, logged code), and not for C++ code (coinplex.cpp),
The code in seplex.c should be generic for OSI, i.e. not specific to
any solver. In coinplex.cpp, solver specific code can be given, but no
ECLiPSe specific code -- so that coinplex.cpp can be sent as part of
the logged code for reporting bugs (some ECLiPSe
specific code for I/O was needed so that messages from OSI can be
sent to ECLiPSe steams, but these are in a NOECLIPSE macro that can be
defined to exclude them).
Problem descriptor
The C level descriptor (lp_desc) contains a field that points to the
solver problem pointer, COINprob* in the case of COIN/OSI. This is
defined as a void* in C, but is defined as a structure in coinplex.cpp
as follow:
struct {
OsiXxxSolverInterface * Solver;
char** varnames; /* for names of variables (columns)
*/
unsigned int vnsize; /* number of variable names */
char notfirst; /* has problem been solved? */
.......
/* solver specific fields */
}
notfirst is required to determine if OSI's initialSolve() or resolve()
should be called to solve the linear problem.
varnames is used to store the variable names (if passed by eplex) that
are printed when the problem is written out in LP or MPS format).
vnsize is 0 if no names have been passed from the ECLIpSe level.
For example, for the CLP/CBC solver, there are the following fields:
char mipIsShared; /* 1 if shared with Solver, 0 if
copied */
CbcModel* mipmodel; /* pointer to the MIP model */
ClpInterior* interiormodel; /* pointer to the
interior point model */
double
timeout;
/* timeout value */
This contain information not supported by OSI (such as the timeout
value), and specific features required, such as the CbcModel pointer
for use by CBC.
Note the combination of CLP/CBC solver is done using the
OsiClpSolverInterface, and the CBC MIP solver is accessed via CbcModel
and CBC API, instead of using the OsiCbcSolverInterface, because this
is the recommended method from John Forrest, who is the main person
behind both CLP and CBC.
Solver specific Information
As much as possible, the external solver is accessed via OSI in coinplex.cpp, so that common
code could be used for the different solvers. However, some features
are not available or poorly supported by OSI, and specific solver
support for these features should be provided if possible:
- 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.
Most of the solver specific code are implemented for osI_clpcbc
currently, and there are also some code to work around some features of
Cbc:
- 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
The following procedures are defined:
-
int coin_get_objsen(COINprob * lp)
return the sense (SENSE_MIN or
SENSE_MAX) of the objective function for the problem
-
int coin_get_numcols(COINprob* lp)
returns the number of columns for the
problem
-
int coin_get_numrows(COINprob* lp)
returns the number of rows for the
problem
-
int coin_get_probtype(COINprob* lp)
returns the problem type of the problem
-
int coin_getrhs(COINprob * lp, double *rhs, int start, int end)
returns in rhs the right hand side
coeff. of rows from start to end. rhs should be pointing at a double
array of at least end-start elements. Returns -1 if error
-
int coin_getrowsense(COINprob * lp, char *rsense, int start,
int end)
returns in rsense the row senses for
rows from start to end. rsense should be pointing at a char array of at
least end-start elements. Returns -1 if error
-
int coin_getlb(COINprob * lp, double *lb, int start, int end)
returns in lb the lower bounds of
columns from start to end. lb should be pointing at a double array of
at least end-start elements. Returns -1 if error
-
int coin_getub(COINprob * lp, double *ub, int start, int end)
returns in ub the upper bounds of
columns from start to end. ub should be pointing at a double array of
at least end-start elements. Returns -1 if error
-
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)
change the column types for cnt columns
specified in idxs to the types given in ctype. idxs and ctype are
arrays of at least cnt elements. Returns -1 if error
-
int coin_chgbds(COINprob * lp, int cnt, int * idxs, char * lu,
double *bd)
change the bounds for cnt columns
specified in idxs to the bounds given in bd, with lu specifying which
bound to change. idxs, lu and bd are
arrays of at least cnt elements. Returns -1 if error
-
int coin_loadbasis(COINprob * lp, int *cbase, int *rbase)
loads the column (cbase) and row
(rbase) basis array into the problem if supported. cbase and rbase
should be previously obtained with coin_getbasis()
-
int coin_getbasis(COINprob * lp, int *cbase, int *rbase)
get the current basis. cbase is the
column basis, rbase is the row basis if supported
-
int coin_get_lpobjval(COINprob * lp, double * objvalp)
returns the current linear objective
value for the the problem in objvallp if supported. Otherwise the
current objective value is reutrned instead.
-
int coin_get_mipobjval(COINprob * lp, double * objvalp)
returns the MIP objective value for the
most recent solution to the problem.
-
int coin_get_bestmipbound(COINprob * lp, double * bound)
returns in bound the best bound on the
optimal MIP objective value, generally the best relaxed objective value
in an open node in the search tree. If not supported by the solver,
infinity of the right sign is returned.
-
int coin_get_objcoeffs(COINprob * lp, double *objc, int start,
int end)
returns the objective coeffs in objc
for columns from start to end. objc should point to a double array of
at least end-start elements. Returns -1 if error
-
int coin_chg_objcoeffs(COINprob * lp, int cnt, int * idxs,
double * values)
changes the objective coeffs for cnt
columns with indices specified in idxs to values. idxs and values
should point at arrays that have at least cnt elements. Returns -1 if
error
-
int coin_get_order(COINprob * lp, int cnt, int * idxs, int *
prio, int * direction)
currently unimplemented. For support of
cplex_loadorder/3.
-
int coin_chgqobj(COINprob * lp, int i, int j, double value)
currently unimplemented. For changing
an quadratic objective coefficient.
-
int coin_chgrhs(COINprob * lp, int cnt, int * idxs, double *
values)
changes the right hand side coeffs for
cnt rows with indices specified in idxs to values. idxs and
values should point at arrays of at least cnt size. Returns -1 if error
-
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)
loads the column-wise specified
problem. In the format used by the Coin function, matbeg needs to be
size mac+1, because matbeg[i+i] is used to specify the end of column i.
This is set by coin_loadprob() from matcnt[mac-1]+matbeg[mac-1],
so it does not need to be calculated in seplex.c, but the space for
matbeg[mac] must be allocated.
-
int coin_setcoltype(COINprob* lp, char *ctype)
sets the column types for all columns
in the problem. ctype should be a char array of the same size as the
number of columns. Returns -1 if error
-
int coin_addcols(COINprob* lp, int coladded, int matnz, double*
objx, int* matbeg, int* matind, double* matval, double* bdl, double*
bdu)
add coladded columns to the problem
-
int coin_addrows(COINprob* lp, int rowadded, int nzadded,
double* rhsx, char* senxm int* rmatbeg, int* rmatind, double* rmatval)
add rowadded rows to the problem
-
int coin_chgobjsen(COINprob* lp, int objsen)
change sense of objective function to
objsen (SENSE_MIN or SENSE_MAX)
-
int coin_get_row(COINprob* lp, int* nnz, int* rmatind, double*
rmatval, int idx)
returns in nnz, rmatind, rmatval the
values for row idx. Returns -1 if error
-
int coin_delrows(COINprob* lp, int ndr, int* idx)
delete ndr rows from the problem, with
indices specified in 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)
currently unimplemented. Returns the
primal objective value when using barrier
-
int coin_get_bar_dual_objval(COINprob* lp, double* objval)
currently unimplemented. Returns the
dual objective value when using barrier
-
state_t coin_get_result_state(lp_desc* lpd)
returns the result state for the most
recent optimisation
-
int coin_get_mipcutoff(COINprob* lp, double* bestbound)
returns in bestbound the cutoff if
supported by the solver, otheriwise infinity of the right sign is
returned. Function returns -1 if error.
-
double coin_infinity(COINprob* lp)
returns the solver's value for infinity
-
int coin_getdblparam(COINprob* lp, int key, double* value)
return the value of double OSI
parameter specified by key in value.
-
int coin_getintparam(COINprob* lp, int key, int* value)
return the value of integer OSI
parameter specified by key in value.
-
int coin_setdblparam(COINprob* lp, int key, double value)
set the double OSI parameter specified
by key to value
-
int coin_setintparam(COINprob* lp, int key, int value)
set the integer OSI parameter specified
by key to value
-
int coin_get_solver_dblparam(COINprob* lp, int key, double*
value)
return the value of double
solver-specific parameter specified by key in value.
-
int coin_get_solver_intparam(COINprob* lp, int key, int* value)
return the value of integer
solver-specific parameter specified by key in value.
-
int coin_set_solver_dblparam(COINprob* lp, int key, double
value)
set the double solver-specific
parameter specified by key to value
-
int coin_set_solver_intparam(COINprob* lp, int key, int value)
set the integer solver-specific
parameter specified by key to value
-
int coin_solve_problem(lp_desc* lpd, int meth, int auxmeth, int
node_meth, int node_auxmeth)
invoke the external solver to optimise
the problem with given methods.
-
int coin_get_stats(lp_desc* lpd)
return the iteration count for last
solve
-
int coin_get_soln_state(lp_desc* lpd, double* sols, double*
pis, double* slacks, double* djs, int* cbase, int* rbase)
returns the solution to the most recent
solve
-
int coin_set_timeout(COINprob* lp, double timeout)
if supported by the solver, set the
timeout to timeout seconds. Otherwise do nothing.
-
int coin_create_prob(COINprob** lp)
create a new COINprob handle and assign
a solver instance to it.
-
int coin_reset_prob(lp_desc* lpd)
reset the problem sate so that problem
can be resolved [needed by CBC]
-
int coin_writeprob(COINprob* lp, char* file, char* otype)
write out the problem in format
specified by otype into filename file. Note that currently COIN/OSI
does not support writing out of maximising problems very well - the
objective function's sign will be reversed and the problem written as a
minimsing problem, according to the documentation.
-
int coin_readprob(COINprob* lp, char* file, char* otype)
read in the problem in format otype in
the file file.
-
int coin_getnumnz(COINprob* lp)
returns the number of non-zero elements
in the problem
-
int coin_getnumint(COINprob* lp)
returns the number of integer columns
in the problem
-
int coin_get_dual_infeas(COINprob* lp, int* infeas)
if supported, returns the number of
dual infesibility for the current solution state (for Simplex solvers
only)
-
int coin_get_primal_infeas(COINprob* lp, int* infeas)
if supported, returns the number of
primal infesibility for the current solution state (for Simplex solvers
only)
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.
Note for OSI: OSI provides only a small number
of parameters, whose
name starts with Osi. Similar mapping rules as CPLEX and Xpress
are applied, so OsiDualObjectiveLimit
becomes dualobjectivelimit.
In addition, because these parameters are not sufficient to cover some
common functionality (especially for MIP solving), we include a further
set of common parameters that will map to solver specific parameters.
Currently these are:
node
limit
|
number of MIP search-tree nodes
allowed
|
solution_limit
|
number of MIP solution allowed
|
integrality
|
integer tolerance
|
abmipgap
|
absolute MIP gap
|
mipgap
|
MIP gap
|
objdifference
|
cutoff increment
|
Two new parameter types are used: 3 for integer solver-specific
parameters, 4 for double solver-specific parameters.
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 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.
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.
Note that in the case of OSI, the logged calls are to
coinplex.cpp, rather than directly to OSI. coinplex.cpp needs to
be included in the code in the report. The LOG_CALLS macro should
be defined (and coinplex.cpp compiled with it) when generating the
logged code. For the report, LOG_CALLS should be undef, and NOECLIPSE
defined.
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
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
Several macros are defined to minimise the amount of special logging
code
needed:
- 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.