Solver Specific Information

10.11 Solver Specific Information

The external solvers currently supported by the eplex library are:

XPRESS-MP, a product of Dash Optimisation (www.dashoptimization.com)
CPLEX, a product of ILOG (www.ilog.com)
Solvers accessed via OSI, an Open Source solver interface of the COIN-OR project (www.coin-or.org). Various solvers are supported via OSI using the generic interface. The following are currently distributed:
- clpcbc: COIN-OR’s CLP linear solver in combination with the CBC branch and cut framework for MIP problems. The CLP solver may be compiled with third-party open-source packages, such as University of Florida’s AMD package (www.cise.ufl.edu/research/sparse/amd/), used by CLP barrier solve. Eplex provides specialised support for this combination, which enhance the features provided and improve performance for solving larger MIP problems.
- symclp: COIN-OR’s SYMPHONY MILP solver (with CLP as the linear solver). Supported via the generic OSI API.

Both Dash and ILOG offer academic licences at discounted prices, or academic partner programs.

To load a specific solver explicitly, use:

:- lib(eplex_cplex).
:- lib(eplex_xpress).
:- lib(eplex_osi_clpcbc). 
:- lib(eplex_osi_symclp).

The first line explicitly requests the CPLEX solver, the second line explicitly requests the XPRESS-MP solver. Note that these solvers must be available for your machine for the above to work. The third line requests the CLP/CBC solver, and the fourth line requests the SYMPHONY solver.

10.11.1 Versions and Licences

All the solvers supported by the library come in various versions. The set of supported solver versions may vary between different releases of ECLⁱPS^e; please refer to the release notes.

For commercial solvers, you may require solver licence to use the solver, and depending on which solver licence you have (for the commercial solvers), which version of it, and which hardware and operating system, you need to use the matching version of this interface.² Because an ECLⁱPS^e installation can be shared between several computers on a network, we have provided you with the possibility to tell the system which licence you have on which machine. To configure your local installation, simply add one line for each computer with the appropriate licence to the file <eclipsedir>/lib/eplex_lic_info.ecl, where <eclipsedir> is the directory or folder where your ECLⁱPS^e installation resides. The file contains lines of the form

licence(Hostname, Solver, Version, LicStr, LicNum).

For example, if you have CPLEX version 7.5 on machine workhorse, and XPRESS-MP version 15.20 (with the license file located in /my/xpress/license) on machine mule, and your Internet domain is +icparc.ic.ac.uk, you would add the lines

licence('workhorse.icparc.ic.ac.uk', cplex, '75', '', 0).
licence('mule.icparc.ic.ac.uk', xpress, '1520', '/my/xpress/license', 0).

The hostname must match the result of get_flag(hostname,H), converted to an atom (this is normally the complete Internet domain name, rather than just the machine). Version is formed from the concatenation of the major and minor version numbers. The meaning of LicStr and LicNum depends on the optimiser: For an open source solver, both LicStr and LicNum are unused, as no license is required. For CPLEX with normal licenses, they are unused (the environment variable ILOG_LICENSE_FILE should be set to the CPLEX license file access.ilm as usual). For XPRESS-MP, LicStr is a string specifying the directory where licence file is located (overrides value of XPRESS environment variable). LicNum is unused. If a machine has more than one licence and lib(eplex) is called, the first one listed in eplex_lic_info.ecl will be used.

10.11.2 Solver Differences

While the eplex library allows the user to write code in a solver-independent way, there are differences between the solvers that the user should be aware of:

Different solvers may support different features. In particular, solvers may support different methods of solving the problem, and solving of problems with a quadratic objective is not supported for all solvers. At the very minimum, solvers must be able to solve (optimise) linear problems with a linear objective. Currently, all supported solvers can solve linear and MIP problems, with a Simplex solver.
Some features may be poorly supported by a particular solver, and some feature (such as the relaxed probe of eplex_probe/2 may be supported slightly differently).
Performance for specific problem may vary very significantly (orders of magnitude) between different solvers. This does not necessarily indicate that one solver would consistently out perform another. In addition, the different solvers may return a different optimal solution to specific problems, i.e. with the same objective value, but different solution values for the variables.
The solvers have different solver parameters to control/tune the solver. These can be accessed from eplex, and is one of the only places where the user code may need to be solver specific.

CPLEX

CPLEX supports solving of linear and mixed integer problems, both with a linear objective (LP and MILP), and also with a quadratic objective (QP and MIQP). It supports various solving methods: simplex (primal and dual), barrier, network simplex, and sifting.

In recent versions of CPLEX, the relaxed and fixed probes are implemented by removing the integer information from the problem and solving the relaxed problem, and then adding the interger information back. This is because the CPLEX API does not provide access to the root node of the MIP solve.

CPLEX have only global parameters.

OSI

The features provided by eplex OSI is determined by the actual solver(s) used via OSI, and to a lesser extent by what the OSI API supports. The OSI API is mainly designed to support solving of linear and, to a lesser extent, MILP problems. However, for specific solvers, in particular the CLP/CBC combination, eplex directly access the solvers’ own API to provide some functionality not supportable via OSI. Note however the OSI API is constantly evolving and improving, so some of the features may be directly supported via OSI in the future.

The sources for the porjects in COIN-OR can be downloaded from www.coin-or.org/download.html. Features not supported by OSI:

changing of solving method (it does support specifying if the problem should be solved as a primal or dual)
problems with a quadratic objective function
time-outs from solving a problem.
obtaining detailed information about the MIP solving process, especially when the MIP search was not complete, such as the best MIP objective bound.
determining if an aborted solve have a suboptimal solution
writing out a problem with a maximising objective function in LP or MPS format.
writing out or reading in an quadratic objective function in LP or (extended) MPS format.
use of Special Order Set (SOS)
extracting an IIS for an infeasible problem

osi_clpcbc

Supports primal, dual simplex and barrier (interior point) methods for solving linear and MIP problems with linear objective function, and linear problems with a quadratic objective function. It also supports time-outs, and is better at determining the state of an aborted problem than using OSI on its own. For the MIP related functionality, the MIP solver CBC is accessed directly rather than through OSI, and this provides better MIP support: SOS (both SOS 1 and 2) are supported, and more information on the MIP solver state is available, and a more sophisticated MIP search (using the standalone CBC Solver) than the default is performed, generally leading to faster MIP solves.

For the barrier/interior point method, CLP can take advantage of third-party packages to order a sparse matrix prior to Cholesky factorisation. Such packages are crucial to the performance of the barrier method, and currently the binary distribution of CLP is compiled with University of Florida’s AMD (Approximate Minimum Degree ordering) package. The source for this package needs to be downloaded separately from the COIN-OR project at www.cise.ufl.edu/research/sparse/amd/.

A quadratic objective needs to be in postive semi-definite form, but currently CLP does not check this, and the result of trying to solve a problem with a quadratic objective not in positive semi-definite form is undefined.

The problem representation is stored by CLP, and one performance issue when using CLP is that incrementally adding new constraints to a problem after solver setup can be expensive, as the whole problem has to be copied and expanded for each addition. It is therefore more efficient to either post the constraints before problem setup, or add a large number of constraints in one go, e.g. by using eplex_add_constraints/3 . Unfortunately, this can be less memory efficient than incrementally adding the constraints, if those constraints are only needed by eplex and not at the ECLⁱPS^e level.

osi_symclp

Supports primal and dual simplex methods for solving linear and MILP problems. MILP is currently performed via the standard OSI API, and so has the same restrictions. Special Order Sets (SOS) are not supported. Time-outs are not supported.

Another restriction is due to SYMPHONY, which does not allow the objective coefficients to be modified after a problem have been solved once. Thus the objective changing probes are not supported.

XPRESS

XPRESS supports solving of linear and mixed integer problems, both with a linear objective (LP and MILP), and also with a quadratic objective (QP and MIQP). It supports simplex (primal and dual) and barrier solving methods.

XPRESS does not maintain an optimisation direction with the problem; instead it requires this to be specified each time the problem is solved. As such, the optimisation direction, given in a LP format specification of the problem, is ignored when a problem is read in, and when writing a problem, minimisation is assumed.

10.11.3 Access to External Solver’s Control Parameters

The external solver has a number of control parameters that affect the way it works. These can be queried and modified using the lp_get/2 , eplex_get/2 , lp_get/3 , and lp_set/2 , eplex_set/2 , lp_set/3 predicates respectively:

lp_get(+Handle, optimizer_param(+ParamName), -Value)

Retrieve the value of a control parameter for the external solver for the problem represented by Handle. These parameters are solver specific; see lp_get/3 for more details..

EplexInstance:eplex_get(optimizer_param(+ParamName), -Value)

Like lp_get/3, but get a control parameter for the external solver associated with the specified eplex instance.

lp_get(optimizer_param(+ParamName), -Value)

Retrieve the global value of a control parameter for the external solver. The parameters and the exact meaning of ‘global’ is solver specific: if the solver does not have global parameters, this gets the global default value, rather than the globally applicable value. The parameters are as in lp_get/3.

\begin{verbatim}
    ( lp_get(optimizer, xpress) ->
        lp_set(Handler, optimize_param(maxnode), 100)
    ; lp_get(optimizer, cplex) ->
        lp_set(Handler, optimize_param(node_limit), 100)
    ; lp_get(optimizer, osi) ->
        (lp_get(optimizer_version, clpcbc) -> 
             lp_set(Handler, optimize_param(node_limit), 100)
        ;
             true
        )
    ), ...

2: Note that it is not sufficient that you have a valid license and solver libraries for a particular version of the solver. That solver version must also be supported by the release of ECLⁱPS^e you are using.