### Table of Contents

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 |
---|---|---|

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

## LP solving

## 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 |