COPT

Cardinal Optimizer by Cardinal Operations is a solver for mixed-integer linear and convex quadratic programming problems.

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, QCP, MIQCP, ... }

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 MI(QC)P 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 an LP or MIP is infeasible, COPT 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 set to 1 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.

If one knows in advance that the problem is infeasible, then option iis can be set to 2 to skip the initial solve.

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.

Parameter Tuning Tool

The COPT tuning tool performs multiple solves on a model instance, choosing different parameter settings for each run, in a search for settings that improve runtime or other quality measures. The longer it is run, the more likely it is to find a significant improvement. For notes on the limitation of parameter tuning tools, see also the GAMS/Gurobi manual.

A number of tuning-related parameters allow to control the operation of the tuning tool. To enable tuning, option Tuning needs to be set. The value of Tuning will be used as a prefix for the name of option files written by the solver link. The amount of time spend for tuning can be controlled by option TuneTimeLimit. Options TuneMode and TuneMeasure allow to specify whether solving time or bounds on the optimal value should be used as quality measure for the tuning time.

Options that are set in a GAMS/COPT options file are considered as fixed parameters and are not changed by the tuning tool. Since the GAMS/COPT link changes the default for a few COPT options, please check the log for the fixed parameters.

Using option TuneParams, a COPT options file with parameters that should be tuned can be specified. Note that this parameter file is read by COPT directly, so that its syntax may deviate from the one of GAMS/COPT solver option files. The file allows multiple values for each parameter name. For example, if the file contains the lines RootCutLevel 0 1 2 3 and TreeCutLevel 0 1 2 3, then the tuner will optimize only the amount of cutting plane generation for the given instance. If TuneParams is not set, the tuner will generate tuning parameter sets automatically.

If the tuning tool found one or several parameter sets that improve performance, then these will be written into files named <Tuning>.<idx>, where Tuning is the value of option Tuning and idx the index of the parameter set. The parameter set that yields best performance has index 000. GAMS/COPT does not return a solution if the tuning tool is used. Tuning cannot be used at the same time as other advanced features, like feasibility relaxation.

Using Graphical Processing Units (GPUs)

COPTs first-order LP method PDLP can make use of NVIDIA GPUs on Linux and Windows systems. To do so, the following steps need to be taken:

  • Option LpMethod needs to be set 6 to select the PDLP solver.
  • CUDA libraries need to be installed on the system. They are not included with the GAMS distribution. Further, COPT needs to be able to find the CUDA libraries at runtime, which can be ensured by setting environment variable LD_LIBRARY_PATH on Linux or augmenting environment variable PATH on Windows.

When the PDLP solver runs, COPT will indicate in the log whether it found CUDA libraries and a compatible GPU device. If CUDA or an NVIDIA GPU were not found, PDLP will fallback to use the CPU only. Option GPUMode can be used to force or disable the use of GPUs. Option GPUDevice can be used to select a GPU in case several are available.

The use of GPUs is currently available for LPs and the PDLP method only.

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
PDLPTol Convergence tolerance for the first-order method (PDLP)
Range: [1e-12, 0.0001]
1e-06
RelGap The relative gap for MIP
Range: [0, ∞]
GAMS optcr
SolTimeLimit Time limit that is only effictive after a primal feasible solution has been found
Range: [0, 1e+20]
1e+20
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 Level of presolving performed 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
BarStart Starting Point method for barrier
-1: Choose automatically.
0: Simple.
1: Mehrotra.
2: Modified Mehrotra.
-1
Crossover Whether to run crossover after barrier
-1: Choose automatically. Only run crossover when the LP solution is not primal-dual feasible.
0: No.
1: Yes.
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
GPUDevice Utilize the GPU with the specified device ID (in cases where the running machine has multiple GPUs)
Range: {-1, ..., ∞}
-1
GPUMode Usage mode of the GPU solver
-1: Choose automatically.
0: Force the use of CPU mode.
1: Utilize NVIDIA GPU.
-1
LpMethod Specifies the LP method
-1: Dual Simplex for LP. Automatic choice between Dual Simplex and Barrier for MIP.
1: Dual simplex.
2: Barrier.
3: Crossover.
4: Concurrent (Use simplex and barrier simultaneously).
5: Choose between simplex and barrier automatically (Based on features such as sparsity and/or coefficients ranges).
6: First-order method (PDLP).
-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
FAPHeurLevel Level of fix-and-propagate 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 parallel tasks in MIP solving (-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 (-1: automatic, 0: 1 thread)
GAMS threads = 0 sets the default for COPT threads to -1, i.e., let COPT choose the number of processors 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
0: no
1: compute IIS after solve if infeasible
2: compute IIS without solving original problem
0
IISMethod Specifies the IIS method
-1: Automatic.
0: Find smaller IIS.
1: Find IIS quickly.
-1

Parameter Tuning

Option Description Default
TuneMeasure Method to aggregate multiple permutation solves into a single measure for tuner
-1: Choose automatically.
0: Average value.
1: Maximum value.
-1
TuneMethod Tuning method
-1: Choose automatically.
0: Greedy search strategy.
1: Broader search strategy.
-1
TuneMode Specifies tuning mode for tuner
-1: Choose automatically.
0: Solving time.
1: Relative optimality gap.
2: Primal bound (objective function value of incumbent).
3: Dual bound (bound on optimal value).
-1
TuneOutputLevel Output level for tuner
0: No tuning log.
1: Summary of the improved parameters only.
2: Summary of each tuning attempt.
3: Detailed log of each tuning attempt.
2
TuneParams COPT parameter file with options to be tuned
For each parameter, multiple values can be specified.
Range: string
TunePermutes Number of permuted solves for each parameter set by tuner (0: auto)
Range: {0, ..., ∞}
0
TuneTargetRelGap Target relative gap for tuning
Range: [0, ∞]
0.0001
TuneTargetTime Target elapsed time for tuning
Range: [0, ∞]
0.01
TuneTimeLimit Time limit of tuning (0: auto)
Range: [0, 1e+20]
0
Tuning If set, enables tuning tool. The option value should be the prefix for names of tuned option files that are written.
Range: string

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
solvetrace name of file for writing solving progress information during solve
Range: string
solvetracenodefreq frequency in number of nodes for writing to solve trace file
The node frequency does not work when COPT is run with multiple threads.
Range: {0, ..., ∞}
100
solvetracetimefreq frequency in seconds for writing to solve trace file
Range: (0, ∞)
5
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