Cardinal Optimizer by Cardinal Operations is a solver for linear programming problems (LPs) and mixed-integer linear programming problems (MIPs).

Usage

A GAMS/COPT or GAMS/COPT-Link license is required to use the GAMS/COPT interface that is distributed with GAMS. If only a GAMS/COPT-Link license is available, also a separate COPT license needs to be installed on the system, see the "Cardinal Operations User Guide" for details.

The following statement can be used inside your GAMS program to specify using COPT

Option MIP = COPT;     { or LP, RMIP }

The above statement should appear before the Solve statement. If COPT was specified as the default solver during GAMS installation, the above statement is not necessary.

COPT supports special ordered sets (SOS), but no semicontinuous or semiinteger variables.

Specification of COPT Options

The following GAMS parameters are currently supported by GAMS/COPT: reslim, iterlim, nodlim, optcr, optca, tryint, and threads.

Further options can be set via a solver options file, see Section The Solver Option File for further information. Following is an example options file copt.opt:

TreeCutLevel 0
SimplexThreads 4

It will cause COPT to use cut generators only in the root node (for a MIP solve) and specifies to use 4 threads in the simplex algorithm.

Specification of Indicators

Indicators are a modeling tool to specify that certain equations in a model must only be satisfied if certain binary variables take a specified value. Indicators are not supported by the GAMS language, but can be passed to COPT via a GAMS/COPT solver options file, see Indicator Constraints for more details on its syntax.

MIP Starting Point

When solving a MIP, by default all values that are specified as variable levels in the GAMS model are passed as starting point to COPT (unless MipStartMode = 0). However, if GAMS option tryint is set to a nonzero value or MipStartMode = 2, then only values of binary and integer variables which fractionality is at most the value tryint are passed as starting point to COPT (possible fractional values are rounded to integers). COPT will then try to complete this partial solution to a feasible solution.

Solution Pool

When COPT solves a problem, it may find several solutions, whereof only the best one is available to the GAMS user via the variable level values in the GAMS model. If the option solnpool is specified, then all alternative solutions found by COPT are written into GDX files and an index file with the name given by the this option is written. If the option solnpoolmerge is specified, then all alternative solutions found by COPT are written into a single GDX file, which name is given by the this option.

The GAMS testlib model dumpsol shows an example use for this option.

Infeasible and unbounded LPs

If an LP is found infeasible by COPT, a primal infeasibility certificate in form of a Farkas proof (see also Mosek manual) is computed. The GAMS/COPT link returns the values of this certificate in the equations marginal values and sets the INFES markers (see solution listing) for those equations that are included in the Farkas proof.

If an LP is found unbounded by COPT, a dual infeasibility certificate in form of a primal ray is computed. If the problem is feasible, then the primal ray gives a direction in which the objective function can be infinitely improved. The GAMS/COPT link returns the values of the primal ray in the variable level values and sets UNBND markers (see solution listing) for those variables that are included in the ray.

COPT option ReqFarkasRay can be used to disable the calculation of these infeasibility certificates.

Finding an Irreducible Inconsistent Subsystem (IIS) of Constraints

If COPT declares an LP or MIP as infeasible, it has the capability to identify a subset of the constraints that are infeasible and become feasible once any one of them is eliminated. Option iis can be used to enable finding an IIS.

As an example, consider a GAMS model containing

Positive Variables x, y;
Equation e1;
e1.. x + y =l= -1;

The corresponding COPT output when iis has been enabled will look like

Starting the simplex solver using 1 thread

Method   Iteration           Objective  Primal.NInf   Dual.NInf        Time
Dual             0    0.0000000000e+00            1           0       0.00s

Solving finished
Status: Infeasible  Objective: -  Iterations: 0  Time: 0.00s
Start the IIS computation for an LP

 Iteration  Min RowBnd  Max RowBnd  Min ColBnd  Max ColBnd      Time
         0           0           1           0           2      0.00s
         1           0           1           0           2      0.00s
         2           1           1           0           2      0.00s
         3           1           1           1           2      0.00s
         4           1           1           2           2      0.00s

IIS summary: 1 rows, 2 bounds of columns
IIS computation finished (0.000s)
IIS is minimal
Number of equations in IIS: 1
  Upper: e1 <= -1
Number of variables in IIS: 2
  Lower: x >= 0
  Lower: y >= 0

That is, COPT finds the problem infeasible. Then the IIS computation is started and an IIS is found. The IIS is then printed to the log and listing file. It consists of the lower bounds of variables x and y and equation e1. This suggests that the entire model can be made feasible by lowering the lower bound of x or y or by increasing the right-hand side of e1.

Using the Feasibility Relaxation

The feasibility relaxation is enabled by the FeasRelax parameter in a COPT solver option file.

With the FeasRelax option COPT selectively relaxes the variable bounds and constraint sides of an infeasible model instance in a way that a weighted penalty function is minimized. In essence, the feasible relaxation tries to suggest the least change that would achieve feasibility. It returns an infeasible solution to GAMS and marks the relaxations of bounds and constraints with the INFES marker in the solution section of the listing file.

Attention

At the moment, COPT can only relax sides of linear constraints. Indicator and quadratic constraints are not considered for relaxation.

By default all equation sides are candidates for relaxation and weighted equally but none of the variable bounds can be relaxed. This default behavior can be modified by assigning relaxation preferences to variable bounds and constraints. These preferences can be conveniently specified with the dot option feaspref. A zero preference means that the associated bound or constraint side is not to be modified. The weighted penalty function is constructed from these preferences. The larger the preference, the more likely it will be that a given variable bound or constraint side will be relaxed. However, it is not necessary to specify a unique preference for each bound or range. In fact, it is conventional to use only the values 0 (zero) and 1 (one) except when your knowledge of the problem suggests assigning explicit preferences.

Preferences can be specified through a COPT solver option file. The syntax is:

(variable or equation) .feaspref (value)

For example, suppose we have a GAMS declaration:

   Set i /i1*i5/;
   Set j /j2*j4/;
   variable v(i,j); equation e(i,j);

Then, the relaxation preference in the copt.opt file can be specified by:

feasrelax 1
v.feaspref            1
v.feaspref('i1',*)    2
v.feaspref('i1','j2') 0

e.feaspref(*,'j1')    0
e.feaspref('i5','j4') 2

First we turn the feasible relaxation on. Furthermore, we specify that all variables v(i,j) have preference of 1, except variables over set element i1, which have a preference of 2. The variable over set element i1 and j2 has preference 0. Note that preferences are assigned in a procedural fashion so that preferences assigned later overwrite previous preferences. The same syntax applies for assigning preferences to equations as demonstrated above. If you want to assign a preference to all variables or equations in a model, use the keywords variables or equations instead of the individual variable and equations names (e.g. variables.feaspref 1).

The parameter FeasRelaxMode allows different strategies in finding feasible relaxation in one or two phases. In its first phase, it attempts to minimize its relaxation of the infeasible model. That is, it attempts to find a feasible solution that requires minimal change. In its second phase, it finds an optimal solution (using the original objective) among those that require only as much relaxation as it found necessary in the first phase. Values of the parameter FeasRelaxMode indicate two aspects: (1) whether to stop in phase one or continue to phase two and (2) how to measure the relaxation (as a sum of required relaxations; as the number of constraints and bounds required to be relaxed; as a sum of the squares of required relaxations). Also check model feasopt1 in the GAMS model library.

List of COPT Options

In the following, we give a detailed list of available COPT options.

Limits and Tolerances

Presolving and Scaling

LP solving

MIP solving

Multithreading

Infeasibility Analysis

GAMS/COPT link