COPT

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

Option Description Default
AbsGap The absolute gap for MIP
Range: [0, ∞]
GAMS optca
BarIterLimit Barrier iteration limit
Range: {0, ..., ∞}
GAMS iterlim
DualTol The tolerance for dual solutions and reduced cost
Range: [1e-09, 0.0001]
1e-06
FeasTol The feasibility tolerance
Range: [1e-09, 0.0001]
1e-06
IntTol The integer feasibility tolerance
Range: [1e-09, 0.1]
1e-06
MatrixTol The input matrix coefficient tolerance
Range: [0, 1e-07]
1e-10
NodeLimit Limit of nodes for MIP
Range: {-1, ..., ∞}
GAMS nodlim
RelGap The relative gap for MIP
Range: [0, ∞]
GAMS optcr
TimeLimit Time limit of the optimization
Range: [0, 1e+20]
GAMS reslim

Presolving and Scaling

Option Description Default
Dualize Whether to dualize a problem before solving it
-1: Choose automatically.
0: No dualizing.
1: Dualizing the problem.
-1
Presolve Whether to perform persolving before solving a problem
-1: Choose automatically.
0: No presolving.
1: Fast presolving.
2: Normal presolving.
3: Aggressive presolving.
-1
Scaling Whether to perform scaling before solving a problem
-1: Choose automatically.
0: No scaling.
1: Apply scaling.
-1

LP solving

Option Description Default
BarHomogeneous Whether to use homogeneous self-dual form in barrier
-1: Choose automatically.
0: No.
1: Yes.
-1
BarOrder Ordering method for barrier
-1: Choose automatically.
0: Approximate Minimum Degree (AMD).
1: Nested Dissection (ND).
-1
Crossover Whether to run crossover after barrier
Range: boolean
1
DualPerturb Whether to allow the objective function perturbation
-1: Choose automatically.
0: No perturbation.
1: Allow objective function perturbation.
-1
DualPrice Specifies the dual simplex pricing algorithm
-1: Choose automatically.
0: Using Devex pricing algorithm.
1: Using dual steepest-edge pricing algorithm .
-1
LpMethod Specifies the LP method
-1: Choose automatically.
1: Dual simplex.
2: Barrier.
3: Crossover.
4: Concurrent (Use simplex and barrier simultaneously).
-1
ReqFarkasRay Whether to return a Farkas or Ray when an LP is infeasible or unbounded
Range: boolean
1

MIP solving

Option Description Default
ConflictAnalysis Whether to perform conflict analysis
-1: Automatic.
0: No.
1: Yes.
-1
CutLevel Level of cutting planes generation
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1
DivingHeurLevel Level of diving heuristics
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1
HeurLevel Level of heuristics
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1
MipStartMode Specifies MIP start mode
-1: Automatic.
0: Disable MIP starts.
1: Only use full and feasible MIP starts.
2: Try to complete partial feasible MIP starts by solving subMIPs.
-1, if GAMS tryint = 0, otherwise 2
MipStartNodeLimit Limit of nodes for MIP start sub-MIP (to complete partial MIP starts) (-1: unlimited)
Range: {-1, ..., ∞}
-1
NodeCutRounds Maximum cut rounds in a local node
Range: {-1, ..., ∞}
-1
RootCutLevel Level of root cutting planes generation
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1
RootCutRounds Maximum cut rounds in the root (-1: unlimited)
Range: {-1, ..., ∞}
-1
RoundingHeurLevel Level of rounding heuristics
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1
StrongBranching Level of strong branching
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1
SubMipHeurLevel Level of sub-MIP heuristics
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1
TreeCutLevel Level of tree cutting planes generation
-1: Automatic.
0: Off.
1: Fast.
2: Normal.
3: Aggressive.
-1

Multithreading

Option Description Default
BarThreads Number of threads to use in the barrier solver
Range: {-1, ..., 128}
-1
CrossoverThreads Number of threads to use in the crossover
Range: {-1, ..., 128}
-1
MipTasks Number of MIP tasks in parallel (-1: automatic)
Range: {-1, ..., 256}
-1
SimplexThreads Number of threads to use in the simplex solver
Range: {-1, ..., 128}
-1
Threads Number of threads to use
Range: {-1, ..., 128}
GAMS threads

Infeasibility Analysis

Option Description Default
.feaspref preference to include variable bound or equation side into feasibility relaxation
The higher the value, the more likely it will be that associated variable bounds or equation sides are relaxed when computing a feasible relaxation. If zero, then the associated variable bounds or equation sides are not to considered for relaxation.
Range: [0, ∞)
1.0 for equations, 0.0 for variables
FeasRelax whether to compute a feasible relaxation instead of solving the problem
Range: boolean
Synonyms: feasopt
0
FeasRelaxMode Specifies the feasibility relaxation mode
0: Minimize sum of violations.
1: Optimize original objective function under minimal sum of violations.
2: Minimize number of violations.
3: Optimize original objective function under minimal number of violations.
4: Minimize sum of squared violations.
5: Optimize original objective function under minimal sum of squared violations.
Synonyms: feasoptmode
0
iis whether to compute an Irreducible Inconsistent Subsystem (IIS) if the problem is infeasible
Range: boolean
0
IISMethod Specifies the IIS method
-1: Automatic.
0: Find smaller IIS.
1: Find IIS quickly.
-1

GAMS/COPT link

Option Description Default
readparams read COPT parameter file
Range: string
solnpool Solution pool file name
The name of a solutions index gdx file for writing alternate solutions found by COPT. The GDX file specified by this option will contain a set called index that contains the names of GDX files with the individual solutions.
Range: string
solnpoolmerge Solution pool file name for merged solutions
Range: string
solvefinal whether to solve the LP obtained from fixing discrete variables and variables in SOS after a MIP solve
If marginals are not accessed after a MIP solve, it is advised to disable this option.
Range: boolean
1
writebas name of file to which to write advanced starting basis in basis format
Range: string
writebin name of file to which to write problem in COPT binary format
Range: string
writelp name of file to which to write problem in LP file format
Range: string
writemps name of file to which to write problem in MPS file format
Range: string
writemst name of file to which to write MIP starting point
Range: string