Modeling and Solving Optimization Problems

This chapter will introduce how to model and solve different types of optimization problems using the COPT solver. The content of the chapter is structured as follows:

The types of problems and corresponding optimization algorithms currently supported by the COPT solver are shown in Table 22:

Table 22 Types of Problems and Algorithms Supported by COPT

Problem type

Available algorithms

Linear Programming (LP)

Dual simplex; Barrier; First-Order Method

Second-Order-Cone Programming (SOCP)

Barrier

Exponential Cone Programming (ExpCone)

Barrier

Convex Quadratic Programming (QP)

Barrier

Convex Quadratically Constrained Programming (QCP)

Barrier

Semidefinite Programming (SDP)

Barrier; ADMM

Mixed Integer Linear Programming (MILP)

Branch-and-Cut

Mixed Integer Second-Order-Cone Programming (MISOCP)

Branch-and-Cut

Mixed Integer Convex Quadratic Programming (MIQP)

Branch-and-Cut

Mixed Integer Convex Quadratically Constrained Programming (MIQCP)

Branch-and-Cut

COPT supports three methods of inputting optimization problems: model file reader, programming interface, and third-party tools.

  1. For model file input, please refer to File Formats.

  2. The programming language interfaces supported by COPT include:

    • C

    • Python

    • C++

    • C#

    • Java

    • Fortran

  3. The main third-party tools interfaces currently supported by COPT include:

    • AMPL

    • AIMMS

    • GAMS

    • Julia

    • Pyomo

    • PuLP

    • CVXPY

Linear Programming (LP)

Linear Programming, as the most fundamental and important branch of operations research, has a wide range of applications. The objective function and constraints of a linear programming problem are both linear.

Mathematical Model

The mathematical formulation is as follows:

(18)\[\begin{split}\min\quad &\sum_{i=0}^{m-1}c_jx_j +c^f\\ \mathrm{s.t.}\quad &l_i^c\leq \sum_{j=0}^{n-1}a_{ij}x_j\leq u_i^c,\qquad i=1,2,\cdots,m-1 \\ &l_j^v\leq x_j\leq u_j^v,\qquad j=1,2,\cdots,n-1\end{split}\]

Alternatively, the model can be concisely expressed using vectors and matrices:

(19)\[\begin{split}\min\quad &c^Tx +c^f\\ \mathrm{s.t.}\quad &l^c\leq Ax\leq u^c \\ &l^v\leq x\leq u^v\end{split}\]

The variables and parameters in the model have the following meanings:

  • Problem size: \(m\) represents the number of constraints, and \(n\) represents the number of decision variables.

  • Decision variables: \(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\)

  • Variable bounds: \(l^v, u^v\in\mathbb{R}^n\), where \(l^v\) represents the lower bounds and \(u^v\) represents the upper bounds of the variables.

  • Constraint bounds: \(l^c, u^c\in\mathbb{R}^m\), where \(l^c\) represents the lower bounds and \(u^c\) represents the upper bounds of the constraints.

  • Coefficient matrix for linear constraints: \(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\)

  • Coefficients of variables in the objective function: \(c\in\mathbb{R}^n\) represents the coefficients of the variables in the objective function, and \(c^f\) represents the constant term in the objective function.

Modeling

The basic steps to build and solve a Linear Programming (LP) model in COPT are as follows:

  1. Create the COPT environment and model.

  2. Add required data.

  3. Construct the linear programming model:

    • Add decision variables.

    • Add linear constraints.

    • Set the linear objective function.

  4. Set optimization parameters and solve the model.

  5. Retrieve the solution results.

Modeling: Adding Linear Constraints

The COPT provides three methods to add linear constraints:

  1. Add a single linear constraint to the model.

  2. Batch add a group of linear constraints.

  3. Add a single linear constraint with lower and upper bounds.

When adding linear constraints to the model, the main parameters that can be specified are:

  • expr/ builder : Linear constraint expression or linear constraint builder.

  • sense: Type of constraint. For possible values, please refer to Constants Section: Constraint Type.

  • name: Name of the linear constraint.

If adding a linear constraint with bounds, the following must also be specified:

  • lb: Lower bound of the linear constraint.

  • ub: Upper bound of the linear constraint.

The implementation methods in different programming interfaces are shown in Table 23:

Table 23 Functions for Adding Linear Constraints

API

Add a single constraint

Add a group of constraints in batch

C

COPT_AddRow

COPT_AddRows

C++

Model::AddConstr()

Model::AddConstrs()

C#

Model.AddConstr()

Model.AddConstrs()

Java

Model.addConstr()

Model.addConstrs()

Python

Model.addConstr()

Model.addConstrs()

Notes

  • For linear constraint operations, the function names, calling methods, and argument names may vary slightly across different programming interfaces, but the functionality and argument meanings are consistent.

  • COPT supports defining constraints using constraint types, but we recommend defining constraints directly using bounds.

  • In the C API, linear constraints are added using the coefficient matrix as an input argument.

  • In the Python API, an additional method for adding linear constraints with bounds is provided: Model.addBoundConstr().

Linear Programming Problem Example

(20)\[\begin{split}\text{Maximize:} & \\ & 1.2 x + 1.8 y + 2.1 z \\ \text{Subject to:} & \\ & 1.5 x + 1.2 y + 1.8 z \leq 2.6 \\ & 0.8 x + 0.6 y + 0.9 z \geq 1.2 \\ \text{Bounds:} & \\ & 0.1 \leq x \leq 0.6 \\ & 0.2 \leq y \leq 1.5 \\ & 0.3 \leq z \leq 2.8\end{split}\]

For corresponding code implementations in different programming interfaces, please refer to: COPT Quick Start Section.

In the programming interfaces provided by COPT, except for the C language, the other object-oriented programming interfaces (C#, C++, Java, Python) offer classes related to linear constraints:

Solving

For linear programming problems, the COPT solver provides the Simplex method and Barrier method. The specific method can be selected by setting the optimization parameter "LpMethod". By configuring other related optimization parameters for linear programming, you can control the detailed workflow of the solving algorithm. For more details, please refer to Parameter: Linear Programming Related.

For the solving logs of linear programming problems, please refer to Logging Section: Simplex Method and Interior Point Method.

Second-Order Cone Programming (SOCP)

Second-Order Cone Programming (SOCP) is an optimization problem where the objective function is linear, and the constraints include second-order cone.

Mathematical Model

Second-Order Cone (SOC):

(21)\[\mathcal{Q}^{n+1} = \left\{(t,x)\in \mathbb{R}\times\mathbb{R}^n\ |\ t\geq \|x\|_2 \right\}\]

Second-Order Cone Constraint:

When \(t\in \mathbb{R}\text{ and } x\in \mathbb{R}^n\) are decision variables, a constraint of the form \(t\geq \|x\|_2\) is called a second-order cone constraint.

The mathematical formulation is as follows:

(22)\[\begin{split}\min\quad &c^Tx +c^f\\ \mathrm{s.t.}\quad &l^c\leq Ax\leq u^c \\ &l^v\leq x\leq u^v\\ &Fx+g\in \mathcal{Q}\end{split}\]

The variables and arguments in the model have the following meanings:

  • Decision variables: \(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\)

  • Decision variable bounds: \(l^v, u^v\in\mathbb{R}^n\), where \(l^v\) represents the lower bounds, and \(u^v\) represents the upper bounds of the variables.

  • Constraint boundaries: \(l^c, u^c\in\mathbb{R}^m\), where \(l^c\) represents the lower bounds, and \(u^c\) represents the upper bounds of the linear constraints.

  • Coefficient matrix of linear constraints: \(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\)

  • Coefficients in the objective function: \(c\in\mathbb{R}^n\) represents the coefficients of the variables in the objective function, and \(c^f\) represents the constant term in the objective function.

  • Problem size: \(m\) represents the number of linear constraints, \(n\) represents the number of decision variables, and \(k\) represents the number of second-order cone constraints.

The following are the meanings of arguments related to the cone constraints:

  • \(F\): \(F\in\mathbb{R}^{k\times n}\) is the coefficient matrix of the cone constraints.

  • \(g\): \(g\in\mathbb{R}^k\) is the constant vector in the cone constraints.

  • \(\mathcal{Q}\): Represents the Cartesian product of \(k\) sets, \(\mathcal{Q} = \mathcal{Q}_1\times \mathcal{Q}_2\times \cdots \times \mathcal{Q}_p\), where \(p\) represents the number of second-order cone constraints, and each \(\mathcal{Q}_i,i\in\{1,2,\cdots,p\}\) represents a second-order cone.

Modeling

The basic steps to construct and solve a Second-Order Cone Programming (SOCP) model in COPT are as follows:

  1. Create the COPT environment and model.

  2. Add required data.

  3. Construct the SOCP model:

    • Add decision variables.

    • Add constraints (second-order cone constraints, linear constraints).

    • Set the objective function.

  4. Set solver parameters and solve.

  5. Retrieve the solution results.

Modeling: Adding Second-Order Cone Constraints

COPT supports modeling the following two types of second-order cone constraints:

Standard Second-Order Cone

(23)\[Q^n= \left\{x\in \mathbb{R}^n\ \left|\ x_0\geq\sqrt{\sum_{i=1}^{n-1} x_i^2}, x_0\geq0 \right. \right\}\]

Constant representation: CONE_QUAD

Rotated Second-Order Cone

(24)\[Q^n_r= \left\{x\in \mathbb{R}^n\ \left|\ 2x_0x_1\geq\sum_{i=2}^{n-1} x_i^2, x_0\geq0, x_1\geq 0 \right. \right\}\]

Constant representation: CONE_RQUAD

When adding second-order cone constraints to the model, the main function arguments that can be specified by the user are:

  • ctype: The type of second-order cone constraint.

    • CONE_QUAD : Standard second-order cone.

    • CONE_RQUAD: Rotated second-order cone.

  • cvars: Variables that form the second-order cone constraint.

  • dim: Dimension of the second-order cone constraint.

The implementation in different programming interfaces is shown in the table below:

Table 27 Functions for Adding Second-Order Cone

API

Function

C

COPT_AddCones

C++

Model::AddCone()

C#

Model.addCone()

Java

Model.addCone()

Python

Model.addCone()

Note

  • The function names, calling methods, and argument names differ slightly in different programming interfaces for operations related to modeling second-order cone constraints, but the functionality and argument meanings are consistent.

  • When providing variables that form the second-order cone constraint, please input them sequentially according to their order in the constraint expression.

  • In the C API, the members of the second-order cone constraints are provided in compressed row storage format. For more information on sparse matrix compressed storage in the C API, please refer to the specific example in the relevant section.

  • In the Python API, an additional member method Model.addConeByDim() is provided for specifying the dimension of the second-order cone.

Example of Second-Order Cone Constraints

A standard second-order cone formed by \(x_4,x_1,x_2,x_3\):

(25)\[x_4 \geq \sqrt{x_1^2 + x_2^2 + x_3^2}\]

A rotated second-order cone formed by \(x_3,x_4,x_1,x_2\):

(26)\[2 x_3 x_4 \geq x_1^2 + x_2^2\]

Taking the standard second-order cone formed by \(x_4,x_1,x_2,x_3\) as an example, the code implementation in different programming interfaces is as follows:

C Interface:

int ncone = 1;
int conetype[] = {COPT_CONE_QUAD};
int conebeg[] = {0};
int conecnt[] = {4};
int coneind[] = {3, 0, 1, 2};
COPT_AddCones(prob, ncone, conetype, conebeg, conecnt, coneind)

C++ Interface:

VarArray cvars;
cvars.PushBack(x4);
cvars.PushBack(x1);
cvars.PushBack(x2);
cvars.PushBack(x3);
model.AddCone(cvars, COPT_CONE_QUAD);

C# Interface:

VarArray cvars = new VarArray();
cvars.PushBack(x4);
cvars.PushBack(x1);
cvars.PushBack(x2);
cvars.PushBack(x3);
model.AddCone(cvars, Copt.Consts.CONE_QUAD);

Java Interface:

VarArray cvars = new VarArray();
cvars.PushBack(x4);
cvars.PushBack(x1);
cvars.PushBack(x2);
cvars.PushBack(x3);
model.addCone(cvars, copt.Consts.CONE_QUAD);

Python Interface:

model.addCone([x4, x1, x2, x3], COPT.CONE_QUAD)

In the programming interfaces provided by COPT, with the exception of the C language, object-oriented programming interfaces (C#, C++, Java, Python) provide classes related to second-order cone constraints:

Attributes Related to Second-Order Cone Constraints

  • COPT_INTATTR_CONES or "Cones"

    Integer attribute. The number of second-order cone constraints in the model.

This attribute provides the count of second-order cone constraints that have been added to the model. It can be useful for monitoring or validating the structure of the model during or after the modeling process.

Exponential Cone

Mathematical Formulation

COPT supports two types of exponential cone contraints:

  • EXPCONE_PRIMAL : Primal exponential cone

(27)\[\mathrm{cl}(S_1) = S_1 \cup S_2\]
(28)\[\begin{split}\begin{aligned} S_1 &= \left\{\begin{pmatrix} t \\ s \\ r \end{pmatrix}\in \mathbb{R}^3\ |\ s > 0,\ t \geq s\ \mathrm{exp}\left(\frac{r}{s} \right) \right\}, \\ S_2 &= \left\{\begin{pmatrix} t \\ s \\ r \end{pmatrix}\in \mathbb{R}^3\ |\ s=0,\ t\geq 0,\ r\leq 0 \right\} \end{aligned}\end{split}\]

  • EXPCONE_DUAL : Dual exponential cone

(29)\[\mathrm{cl}(S_1) = S_1 \cup S_2\]
(30)\[\begin{split}\begin{aligned} S_1 &= \left\{\begin{pmatrix} t \\ s \\ r \end{pmatrix}\in \mathbb{R}^3\ |\ r < 0,\ t \geq -r\ \mathrm{exp}\left(\frac{s}{r}-1\right) \right\}, \\ S_2 &= \left\{\begin{pmatrix} t \\ s \\ r \end{pmatrix}\in \mathbb{R}^3\ |\ r = 0,\ t\geq 0,\ s\geq 0 \right\} \end{aligned}\end{split}\]

Exponential Cone Example

Take \((u_1, 1, u_3) \in K_{\text{exp}}\) for example, which mathematical form is \(u_1 \geq e^{u_3}\). The code implementation is as follows:

C Interface:

Please refer to the example code in the installation package expcone_gp.c.

Python Interface:

u1 = model.addVar(lb=-COPT.INFINITY)
u2 = model.addVar(lb=1.0, ub=1.0)
u3 = model.addVar(lb=-COPT.INFINITY)
model.addExpCone([u1, u2, u3], COPT.EXPCONE_PRIMAL)

C++ Interface:

Var u1 = model.AddVar(-COPT_INFINITY, +COPT_INFINITY, 0.0, COPT_CONTINUOUS, "u1");
Var u2 = model.AddVar(1.0, 1.0, 0.0, COPT_CONTINUOUS, "u2");
Var u3 = model.AddVar(-COPT_INFINITY, +COPT_INFINITY, 0.0, COPT_CONTINUOUS, "u3");

VarArray uconevars;
uconevars.PushBack(u1);
uconevars.PushBack(u2);
uconevars.PushBack(u3);
model.AddExpCone(uconevars, COPT_EXPCONE_PRIMAL);

C# Interface:

VarArray uconevars = new VarArray();
uconevars.PushBack(u1);
uconevars.PushBack(u2);
uconevars.PushBack(u3);
model.AddExpCone(uconevars, Copt.Consts.EXPCONE_PRIMAL);

Var u1 = model.AddVar(-Copt.Consts.INFINITY, +Copt.Consts.INFINITY, 0.0, Copt.Consts.CONTINUOUS, "u1");
Var u2 = model.AddVar(1.0, 1.0, 0.0, Copt.Consts.CONTINUOUS, "u2");
Var u3 = model.AddVar(-Copt.Consts.INFINITY, +Copt.Consts.INFINITY, 0.0, Copt.Consts.CONTINUOUS, "u3");

Java Interface:

Var u1 = model.addVar(-copt.Consts.INFINITY, +copt.Consts.INFINITY, 0.0, copt.Consts.CONTINUOUS, "u1");
Var u2 = model.addVar(1.0, 1.0, 0.0, copt.Consts.CONTINUOUS, "u2");
Var u3 = model.addVar(-copt.Consts.INFINITY, +copt.Consts.INFINITY, 0.0, copt.Consts.CONTINUOUS, "u3");

VarArray uconevars = new VarArray();
uconevars.pushBack(u1);
uconevars.pushBack(u2);
uconevars.pushBack(u3);
model.addExpCone(uconevars, copt.Consts.EXPCONE_PRIMAL);

Semidefinite Programming (SDP)

Semidefinite Programming (SDP) consists semidefinite variables and cone constraints.

Mathematical Model

Positive Semidefinite Cone:

Let \(\mathcal{S}^n\) denote the set of \(n\) -dimensional symmetric matrices, the positive semidefinite cone is defined as:

(31)\[\mathcal{S}_+^n = \left\{X\in \mathcal{S}^n\ |\ u^TXu \geq 0, \forall u\in \mathbb{R}^n\right\}\]

Positive Semidefinite (PSD) Variable:

In an SDP model, the decision variable \(X\in \mathcal{S}_+^n\), can also be denoted as \(X\succeq 0\). This decision variable is referred to as a semidefinite variable. Besides, the linear constraints of the model include semidefinite variables.

Semidefinite Cone Constraint

In an SDP model, \(X\succeq 0\) is commonly referred to as the semidefinite cone constraint, while a constraint of the form \(A\bullet X = b\), which involves a semidefinite variable, is referred to as a linear constraint consisting of PSD variables. For simplicity, in the following chapter, we will refer to it as the semidefinite constraint and distinguish it from the semidefinite cone constraint (i.e., \(X\succeq 0\)).

The mathematical form of semidefinite programming is as follows:

(32)\[\begin{split}\min\quad &\sum_{j=0}^{n-1} c_jx_j + \sum_{j=0}^{p-1} C_j \bullet X_j + c^f \\ \text{s.t.}\quad &l_i^c \leq \sum_{j=0}^{n-1} a_{ij} x_j + \sum_{j=0}^{p-1} A_j \bullet X_j \leq u_i^c,\qquad i=0,1, ..., m-1 \\ &l_j^v\leq\qquad\qquad\quad x_j\qquad\qquad \leq u_j^v,\qquad j=0,1, ..., n-1\\ &\qquad\qquad\qquad X_j \succeq 0,\qquad j = 0,1, ..., p-1\end{split}\]

Here, the operator \(\bullet\) denotes the matrix inner product operation:

Given two matrices \(A = \{a_{ij}\} \in \mathbb{R}^{m\times n}\) and \(B = \{b_{ij}\}\in \mathbb{R}^{m\times n}\), the inner product of matrix \(A\) and matrix \(B\) is defined as:

(33)\[A\bullet B = \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} a_{ij}b_{ij}\]

The variables and arguments in the model have the following meanings:

  • Problem size: \(m\) denotes the number of constraints, \(n\) denotes the number of non-semidefinite variables, and \(p\) denotes the number of semidefinite variables.

  • Decision variables: non-semidefinite variables \(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\), semidefinite variables \(X_j\in \mathcal{S}_+^{r_j}\) (for \(j=0, ..., p-1\)).

  • Non-semidefinite variable range: \(l^v, u^v\in\mathbb{R}^n\), where \(l^v\) denotes the lower bounds and \(u^v\) denotes the upper bounds of the non-semidefinite variables.

  • Constraint boundaries: \(l^c, u^c\in\mathbb{R}^m\), where \(l^c\) denotes the lower bounds and \(u^c\) denotes the upper bounds of the constraints.

  • Coefficient matrix of the linear constraints: \(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\), \(A_j\in \mathbb{R}^{r_j\times r_j}\).

  • Coefficients in the objective function: \(c\in\mathbb{R}^n\) represents the coefficients of the non-semidefinite variables, \(C_j\in\mathbb{R}^{r_j\times r_j}\) represents the coefficients of the semidefinite variables, and \(c^f\) represents the constant term in the objective function.

Modeling

The basic steps to construct and solve a semidefinite programming (SDP) model in COPT are as follows:

  1. Create the COPT environment and model.

  2. Add required data.

  3. Construct the semidefinite programming model:

    • Add decision variables (semidefinite and non-semidefinite variables).

    • Add constraints (including semidefinite constraints).

    • Set the objective function.

  4. Set optimization parameters and solve.

  5. Retrieve the solution.

Modeling: Adding Semidefinite Variables and Semidefinite Constraints

In COPT, semidefinite variables are added by specifying the dimension ( dim ) of the semidefinite variables:

  1. Add a single semidefinite variable.

  2. Add multiple semidefinite variables.

COPT provides two ways to add semidefinite constraints:

  1. First construct the semidefinite constraint expression by combining the semidefinite terms (semidefinite variables and their corresponding coefficient matrices) and the linear terms, and then add them to the model.

  2. Directly provide the semidefinite constraint expression (or semidefinite constraint builder) as a argument input, and add it to the model.

When adding semidefinite constraints to the model, the main arguments that can be specified are:

  • expr / builder : The semidefinite constraint expression or semidefinite constraint builder.

  • rhs : The right-hand side of the semidefinite constraint.

  • sense : The constraint type. For possible values, refer to Constants Chapter: Constraint Type.

  • name : The name of the semidefinite constraint.

The implementation in different programming interfaces is shown in Table 28:

Table 28 Functions for Adding Semidefinite Variables/Constraints

API

Add Semidefinite Variable

Add Semidefinite Constraint

C

COPT_AddPSDCol / COPT_AddPSDCols

COPT_AddPSDConstr

C++

Model::AddPsdVar() / Model.AddPsdVars()

Model::AddPsdConstr()

C#

Model.AddPsdVar() / Model.AddPsdVars()

Model.AddPsdConstr()

Java

Model.addPsdVar() / Model.addPsdVars()

Model.addPsdConstr()

Python

Model.addPsdVar() / Model.addPsdVars()

Model.addPsdConstr()

Notes

  • Regarding the operations for modeling semidefinite variables and semidefinite constraints, the function names, calling methods, and argument names differ slightly among different programming interfaces, but the functionality and argument meanings are consistent.

  • In the C API, when adding semidefinite constraints, arguments such as the indices of the non-zero linear term coefficients and the semidefinite variable indices need to be provided. For more details, refer to function COPT_AddPSDConstr .

  • In the Python API, Model.addConstr() can be used to add a linear constraint, a semidefinite constraint, or an indicator constraint to the model. For more details, please refer to Python API Functions: Model Class.

Examples of PSD varibales and PSD constraints

(34)\[\begin{split}&A\bullet X + x_1 + x_2 = 0.6 \\ &x_1 \geq 0, x_2 \geq 0, X\succeq 0\end{split}\]

where

(35)\[\begin{split}&A=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}\end{split}\]

The code implementation in different programming interfaces is as follows:

C API:

{
  /* Matrix A */
  int ndim = 3;
  int nelem = 6;
  int rows[] = {0, 1, 2, 1, 2, 2};
  int cols[] = {0, 0, 0, 1, 1, 2};
  double elems[] = {1.0, 1.0, 1.0, 1.0, 1.0, 1.0};
  retcode = COPT_AddSymMat(prob, ndim, nelem, rows, cols, elems);
  if (retcode) goto exit_cleanup;
}
/* Add PSD columns */
int nPSDCol = 1;
int colDims[] = {3};
retcode = COPT_AddPSDCols(prob, nPSDCol, colDims, NULL);
if (retcode) goto exit_cleanup;
/* Add columns */
int nCol = 2;
retcode = COPT_AddCols(prob, nCol, NULL, NULL, NULL, NULL, NULL, NULL,
NULL, NULL, NULL);
if (retcode) goto exit_cleanup;
/* Add PSD constraints */
{
  int nRowMatCnt = 2;
  int rowMatIdx[] = {0, 1};
  double rowMatElem[] = {1.0, 1.0};
  int nColCnt = 1;
  int psdColIdx[] = {0};
  int symMatIdx[] = {2};
  char cRowSense = COPT_EQUAL;
  double dRowBound = 0.6;
  retcode = COPT_AddPSDConstr(prob, nRowMatCnt, rowMatIdx, rowMatElem, nColCnt,
    psdColIdx, symMatIdx, cRowSense, dRowBound, 0.0, NULL);
  if (retcode) goto exit_cleanup;
}

C++ API:

SymMatrix A = model.AddOnesMat(3);
Var x1 = model.AddVar(0.0, COPT_INFINITY, 0, COPT_CONTINUOUS, "x1");
Var x2 = model.AddVar(0.0, COPT_INFINITY, 0, COPT_CONTINUOUS, "x2");
PsdVar barX = model.AddPsdVar(3, "X");
model.AddPsdConstr(A * barX + x1 + x2 == 0.6, "PSD_R");

C# API:

SymMatrix A = model.AddOnesMat(3);
Var x1 = model.AddVar(0.0, Copt.Consts.INFINITY, 0, Copt.Consts.CONTINUOUS, "x1");
Var x2 = model.AddVar(0.0, Copt.Consts.INFINITY, 0, Copt.Consts.CONTINUOUS, "x2");
PsdVar barX = model.AddPsdVar(3, "X");
model.AddPsdConstr(A * barX + x1 + x2 == 0.6, "PSD_R");

Java API:

SymMatrix A = model.addOnesMat(3);
Var x1 = model.addVar(0.0, copt.Consts.INFINITY, 0, copt.Consts.CONTINUOUS, "x1");
Var x2 = model.addVar(0.0, copt.Consts.INFINITY, 0, copt.Consts.CONTINUOUS, "x2");
PsdVar barX = model.addPsdVar(3, "X");
PsdExpr pexpr = new PsdExpr(x1, 1.0);
pexpr.addTerm(x2, 1.0);
pexpr.addTerm(barX, A);
model.addPsdConstr(pexpr, copt.Consts.EQUAL, 0.6, "PSD_R");

Python API:

A = m.addOnesMat(3)
x1 = m.addVar(lb=0.0, ub=COPT.INFINITY, name="x1")
x2 = m.addVar(lb=0.0, ub=COPT.INFINITY, name="x2")
X = m.addPsdVars(3, "BAR_X")
psdc = model.addConstr(A * X + x1 + x2 == 0.6, name="PSD_C")

In the programming interfaces provided by COPT, except for the C language, other object-oriented programming interfaces (C#, C++, Java, Python) offer classes related to semidefinite constraints:

Solving

For SDP problems, COPT provides the Barrier method and the ADMM method. You can specify the solving method by setting the optimization parameter SDPMethod.

For more details, please refer to Parameter Section: Semidefinite Programming Related.

Quadratic Programming (QP)

Mathematical Formulation

Convex Quadratic Programming (QP) has a convex quadratic objective function and linear constraints.

The mathematical formulation is as follows:

(36)\[\begin{split}\min\quad x^TQx + c^Tx + c^f\\ \text{s.t.}\quad &l_i^c\leq\sum_{j=0}^{n-1}a_{ij}x_j\leq u_i^c,\qquad i=0,\cdots,m-1\\ &l_j^v\leq x_j\leq u_j^v,\qquad j=0,1,\cdots,n-1\end{split}\]

The variables and arguments in the model are defined as follows:

  • Decision variables: \(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\);

  • Variable bounds: \(l^v, u^v\in\mathbb{R}^n\); where \(l^v\) denotes the lower bounds and \(u^v\) denotes the upper bounds of the variables;

  • Constraint bounds: \(l^c, u^c\in\mathbb{R}^m\); where \(l^c\) denotes the lower bounds and \(u^c\) denotes the upper bounds of the constraints;

  • Coefficient matrix of linear constraints: \(A=(a_{ij})_{m\times n}\in\mathbb{R}^{m\times n}\)

  • Coefficients in the objective function:

    • \(Q\in\mathbb{R}^{n\times n}\) represents the coefficients of the quadratic term in the objective function

    • \(c\in\mathbb{R}^n\) represents the coefficients of the linear term in the objective function, and \(c^f\) represents the constant term in the objective function

  • Problem size: \(m\) denotes the number of constraints, and \(n\) denotes the number of decision variables.

Quadratically Constrained Programming (QCP)

Convex Quadratically Constrained Programming (QCP) consists of convex quadratic constraints.

Mathematical Model

The mathematical formulation is as follows:

(37)\[\begin{split}\min\quad &\frac{1}{2} x^TQx + c^Tx + c^f\\ \text{s.t.}\quad&\frac{1}{2}x^TP_ix+a^T_ix_j\leq u_i^c,\qquad i=0,\cdots,m-1\\ &l^v\leq x_j\leq u^v,\qquad j=0,1,\cdots,n-1\end{split}\]

The variables and parameters in the model are defined as follows:

  • Decision variables: \(x=(x_j)_{j=0}^{n-1}\in\mathbb{R}^n\);

  • Variable bounds: \(l^v, u^v\in\mathbb{R}^n\), where \(l^v\) denotes the lower bounds and \(u^v\) denotes the upper bounds of the variables;

  • Constraint bounds: \(u^c\in\mathbb{R}^m\), where \(u^c\) denotes the upper bounds of the constraints;

  • Coefficients in the quadratic constraints:

    • \(P_i\in \mathbb{R}^{n\times n}\) (for \(i=0,...,m-1\)),

    • \(a_i = (a_{ij})_{n}\in\mathbb{R}^{n}\);

  • Coefficients in the objective function:

    • \(Q\in\mathbb{R}^{n\times n}\) represents the coefficients of the quadratic term in the objective function;

    • \(c\in\mathbb{R}^n\) represents the coefficients of the linear term in the objective function, and \(c^f\) represents the constant term in the objective function.

  • Problem size: \(m\) denotes the number of constraints, and \(n\) denotes the number of decision variables.

Notes

  • The COPT solver currently supports solving convex quadratic programming and convex quadratically constrained programming problems. The matrices \(Q\) and \(P_i\) (for \(i=0,1,\cdots,n\)) must be positive semidefinite.

  • When the constraint type is >= (of the form \(\quad\frac{1}{2}x^TP_ix+\sum_{j=0}^{n-1}a_{ij}x_j\geq l_i^c\)), the matrix \(Q\) must be negative semidefinite.

  • As seen from the mathematical formulation above, the quadratic constraint expression includes quadratic terms, linear terms, and constant terms.

Modeling

The basic steps to construct and solve a Quadratically Constrained Programming (QCP) model in COPT are as follows:

  1. Create a COPT environment and model.

  2. Add model parameters.

  3. Construct the QCP model:

    • Add variables.

    • Add quadratic constraints.

    • Set the quadratic objective function.

  4. Set solving parameters and solve.

  5. Retrieve the solution.

Modeling: Adding Quadratic Constraints

COPT provides two ways to add quadratic constraints:

  1. First, construct the quadratic constraint expression by combining the quadratic and linear terms, then add it to the model.

  2. Directly provide the quadratic constraint expression (or a quadratic constraint builder) as a parameter input and add it to the model.

When adding quadratic constraints to the model, the following parameters can be specified by the user:

  • expr / builder: The quadratic constraint expression or quadratic constraint builder.

  • rhs: The right-hand side of the quadratic constraint.

  • sense: The type of constraint, which can be COPT_LESS_EQUAL or COPT_GREATER_EQUAL.

  • name: The name of the quadratic constraint.

The implementation in different programming interfaces is shown in Table 30:

Table 30 Functions for Adding Quadratic Constraints

Programming Interface

Function

C

COPT_AddQConstr

C++

Model::AddQConstr()

C#

Model.AddQConstr()

Java

Model.addQConstr()

Python

Model.addQConstr()

Note:

  • The operations related to quadratic constraint modeling may vary slightly in terms of function names, calling methods, and parameter names in different programming interfaces, but the functionality and parameter meanings are consistent.

  • In the C API, when adding a quadratic constraint, non-zero linear term coefficient indices, quadratic term indices, and other parameters must be provided. For more details, please refer to C API Functions: Constructing and Modifying the Model under the function COPT_AddQConstr.

  • In the Python API, Model.addQConstr() can be used to add a quadratic constraint to the model. For more details, please refer to Python API Functions: Model Class.

Examples of quadratic constraints

(38)\[x_1^2 + x_2^2 + x_1 + 2x_2 <= 0\]

The code implementation in different programming interfaces is as follows:

C API:

int nRowMatCnt = 2;
int rowMatIdx[] = {0, 1};
double rowMatElem[] = {1.0, 2.0};

int nQMatCnt = 2;
int qMatRow[] = {0, 1};
int qMatCol[] = {0, 1};
double qMatElem[] = {1.0, 1.0};
char cRowSense = COPT_LESS_EQUAL;
double dRowBound = 0.0;
char *name = "q1";
errcode = COPT_AddQConstr(prob, nRowMatCnt, rowMatIdx, rowMatElem,
                          nQMatCnt, qMatRow, qMatCol, qMatElem,
                          cRowSense, dRowBound, name);

C++ API:

model.AddQConstr(x1*x1 + x2*x2 + x1 + 2*x2 <= 0, "q1");

C# API:

model.AddQConstr(x1*x1 + x2*x2 + x1 + 2*x2 <= 0, "q1");

Java API:

QuadExpr q1 = new QuadExpr(0.0);
q1.addTerm(x1, x1, 1);
q1.addTerm(x2, x2, 1);
q1.addTerm(x1, 1);
q1.addTerm(x2, 2);
model.addQConstr(q1, copt.Consts.LESS_EQUAL, 0, "q1");

Python API:

model.addQConstr(x1*x1 + x2*x2 + x1 + 2*x2 <= 0, name="q1")

In the programming interfaces provided by COPT, except for C language, other object-oriented programming interfaces (C#, C++, Java, Python) offer classes related to quadratic constraints:

Related Attributes

Attributes for Quadratic Programming (QP) and Quadratically Constrained Programming (QCP) models are shown in Table 31:

Table 31 Attributes for QP and QCP

Name

Type

Description

QConstrs

Integer

Number of quadratic constraints

QElems

Integer

Number of non-zero quadratic elements in the quadratic objective function

HasQObj

Integer

Whether the problem has quadratic objective function

Mixed-Integer Programming (MIP)

Modeling

Mixed-Integer Programming (MIP) refers to optimization problems where some of the decision variables are restricted to integer values. Currently, COPT supports integer variables combined with linear programming, second-order cone programming, quadratic programming, and quadratically constrained programming.

MIP Problem Type

Solving Algorithm

MILP

Branch-and-Cut

MISOCP

Branch-and-Cut

MIQP

Branch-and-Cut

MIQCP

Branch-and-Cut

In COPT, the supported integer variable types and their corresponding constants are as follows:

  • BINARY

    Binary variable (0-1 variable)

  • INTEGER

    Integer variable

When adding decision variables to the model:

  • Specify the parameter vtype as BINARY to add 0-1 variables;

  • Specify the parameter vtype as INTEGER to add integer variables.

Solving

For integer programming problems, COPT provides the Branch-and-Cut algorithm, which can be specified by setting the optimization parameter "MipMethod". By configuring other related optimization parameters, you can control the specific workflow of the Branch-and-Cut algorithm. For more details, please refer to Parameter Section: Integer Programming Related.

For the solving logs of integer programming problems, please refer to Logging Section: Branch-and-Cut.

Related Attributes

Table 32 Overview of attributes for MIP

Name

Type

Description

Bins

Integer

Number of binary variables

Ints

Integer

Number of integer variables

Indicators

Integer

Number of indicator constraints

IsMIP

Integer

Whether the problem is a MIP

NodeCnt

Integer

Number of explored nodes

HasMipSol

Integer

Whether MIP solution is available

BestObj

Double

Best integer objective value for MIP

BestBnd

Double

Best bound for MIP

BestGap

Double

Best relative gap for MIP

Special Constraints

COPT supports the construction of two types of special constraints: SOS constraints and Indicator constraints.

SOS Constraints

SOS constraints (Special Ordered Set) are a special type of constraint that restricts the values of a group of variables. Currently, COPT supports two types of SOS constraints:

  1. SOS1 Constraint: In this type of constraint, at most one variable in the specified group can take a non-zero value.

  2. SOS2 Constraint: In this type of constraint, at most two variables in the specified group can take non-zero values, and the variables with non-zero values must be adjacent in the order.

These two types of SOS constraints correspond to the following constants in COPT, which can be specified when adding SOS constraints to the model:

  • SOS_TYPE1

    SOS1 Constraint

  • SOS_TYPE2

    SOS2 Constraint

When adding SOS constraints to the model, the following arguments can be specified by the user:

  • sostype: Specifies the type of the SOS constraint.

  • vars: The variables involved in the SOS constraint.

  • weights: The weights of the variables involved in the SOS constraint; an optional argument, default is None.

Note

  • The variables involved in the SOS constraint can be continuous variables, binary variables, or integer variables.

  • If the model includes SOS constraints, the model is an integer programming model.

  • The specific operations and usage of SOS constraints, including the function names, calling methods, and argument names, may vary slightly in different programming interfaces, but the functionality and argument meanings are consistent.

COPT provides related functions to support operations on SOS constraints. Below are the corresponding functions for adding and retrieving SOS constraints in different programming interfaces:

Table 33 Adding and Retrieving SOS Constraints

API

Add SOS Constraints

Retrieve All SOS Constraints in the Model

C

COPT_AddSOSs

COPT_GetSOSs

C++

Model::AddSos()

Model::GetSoss()

C#

Model.AddSos()

Model.GetSoss()

Java

Model.addSos()

Model.getSoss()

Python

Model.addSOS()

Model.getSOSs()

For operations related to SOS constraints, the function names, calling methods, and argument names may vary slightly in different programming interfaces, but the functionality and argument meanings are consistent. Please refer to the corresponding sections of each programming language’s API reference manual for specific details:

In the programming interfaces provided by COPT, except for the C language, other object-oriented programming interfaces (C#, C++, Java, Python) offer classes related to SOS constraints:

  • Encapsulation of operations related to SOS constraints:

    1. Sos Class: Encapsulation of operations related to SOS constraints in COPT.

    2. SosArray Class: Facilitates user operations on a group of Sos class objects.

  • Encapsulation of SOS constraint builders:

    1. SosBuilder Class: Encapsulation of builders for constructing SOS constraints in COPT, providing the following member methods:

    2. SosBuilderArray Class: Facilitates user operations on a group of SosBuilder class objects.

For more details on the member methods and specific descriptions of the above SOS constraint-related classes, please refer to the corresponding sections in the API reference manuals of each programming language.

Indicator Constraints

Indicator constraint is a type of logical constraint that uses a binary variable \(y\) as the indicator variable to determine the logical relationship between the value of \(y\) and whether the linear constraint \(a^{T}x \leq b\) is satisfied. Currently, COPT supports three types of Indicator constraints: If-Then, Only-If, and If-and-Only-If.

  • INDICATOR_IF

    If-Then:

    If \(y = f\), then the linear constraint is satisfied;

    If \(y \ne f\), then the linear constraint can be violated.

(39)\[\begin{split}y &= f \rightarrow a^{T}x \leq b\\ f &\in \{0, 1\}\end{split}\]

  • INDICATOR_ONLYIF

    Only-If:

    If the linear constraint \(a^{T}x \leq b\) is satisfied, then \(y = f\);

    If the linear constraint \(a^{T}x \leq b\) is not satisfied, then \(y\) can take the value of 0 or 1.

(40)\[\begin{split}a^{T}x &\leq b \rightarrow y = f\\ f &\in \{0, 1\}\end{split}\]

  • INDICATOR_IFANDONLYIF

    If-and-Only-If:

    The linear constraint \(a^{T}x \leq b\) and \(y = f\) are equivalent. They must both be satisfied or both be unsatisfied.

(41)\[\begin{split}a^{T}x &\leq b \leftrightarrow y = f\\ f &\in \{0, 1\}\end{split}\]

COPT provides two methods to add Indicator constraints:

  1. By calling an API function (e.g., in Python: Model.addGenConstrIndicator()). The key parameters for constructing an Indicator constraint are:

    • binVar: The binary indicator variable.

    • binval: The value (True or False) of the indicator variable that is conditionally related to the satisfaction of the linear constraint.

    • builder: The linear constraint builder.

    • type: The type of Indicator constraint (possible values are listed in Indicator constraint types).

  2. By overloading operators (for If-Then and Only-If constraints):

    • >>: Represents the If-Then logical relationship, corresponding to INDICATOR_IF;

    • <<: Represents the Only-If logical relationship, corresponding to INDICATOR_ONLYIF.

Here are examples of how to implement these methods in Python API:

  1. Adding an If-Then type Indicator constraint where the linear constraint \(y + 2z >= 3\) is satisfied if \(x\) is true.

    (42)\[x = 1 \rightarrow y+2z \geq 3\]
    model.addGenConstrIndicator(x, True, y + 2*z >= 3)

    model.addConstr((x==1) >> (y + 2*z >= 3))

  2. Adding an Only-If type Indicator constraint where \(x\) is false if the linear constraint \(y + 2z <= 3\) is satisfied.

    (43)\[x = 0 \leftarrow y+2z \leq 3\]
    model.addGenConstrIndicator(x, False, y + 2*z <= 3, type=COPT.INDICATOR_ONLYIF)

    model.addConstr((x==0) << (y + 2*z <= 3))

  3. Adding an If-and-Only-If type Indicator constraint where the binary variable \(x\) being true is equivalent to the linear constraint \(y + 2z = 3\) being satisfied.

    (44)\[x = 1 \leftrightarrow y+2z = 3\]
    model.addGenConstrIndicator(x, True, y + 2*z == 3, type=COPT.INDICATOR_IFANDONLYIF)

Note

  1. The general expression of the linear constraint given above, \(a^{T}x \leq b\), can actually take the forms \(\leq\), \(\geq\), or \(=\).

  2. If the model includes Indicator constraints, it is considered an integer programming model.

  3. COPT supports adding a batch of Indicator constraints to the model by calling an API function. In Python, the corresponding function is: Model.addGenConstrIndicators().

  4. The method of adding Indicator constraints by overloading operators only supports If-Then and Only-If constraints. If you need to add an If-and-Only-If constraint, you must use the API function and specify the type as INDICATOR_IFANDONLYIF.

  5. The specific operations and usage of Indicator constraints, including function names, calling methods, and parameter names, may vary slightly in different programming interfaces, but the functionality and parameter meanings are consistent.

COPT provides related functions to support adding Indicator constraints and retrieving the corresponding Indicator constraint builders, as listed below:

Table 34 Adding and Retrieving Indicator Constraints in Different APIs

API

Add Indicator

Retrieve Indicator

C

COPT_AddIndicator

COPT_GetIndicator

C++

Model::AddGenConstrIndicator()

Model::GetGenConstrIndicator()

C#

Model.AddSos()

Model.GetGenConstrIndicator()

Java

Model.addSos()

Model.getGenConstrIndicator()

Python

Model.addGenConstrIndicator()

Model.getGenConstrIndicator()

For operations such as building and adding Indicator constraints, the function names, calling methods, and argument names may vary slightly in different programming interfaces, but the functionality and argument meanings are consistent. Please refer to the corresponding sections of each programming language’s API reference manual for specific details:

In the programming interfaces supported by COPT, except for the C language, other object-oriented programming interfaces (C#, C++, Java, Python) offer classes related to Indicator constraints:

  • Encapsulation of operations related to Indicator constraints:

    1. GenConstr Class: Encapsulation of operations related to Indicator constraints in COPT.

    2. GenConstrArray Class: Facilitates user operations on a group of GenConstr class objects.

  • Encapsulation of Indicator constraint builders:

    1. GenConstrBuilder Class: Encapsulation of builders for constructing Indicator constraints in COPT.

    2. GenConstrBuilderArray Class: Facilitates user operations on a group of GenConstrBuilder class objects.

For more details on the member methods and specific descriptions of the above Indicator constraint-related classes, please refer to the corresponding sections in the API reference manuals of each programming language.

Attributes for Special Constraints

COPT provides the following attributes to describe the number of special constraints in the model, as shown in Table 35.

For methods of retrieving these attributes in different programming interfaces, please refer to: Attributes Section.

Table 35 Overview of Special Constraints-Related Attributes

Attribute

Type

Description

Soss

Integer

Number of SOS constraints

Indicators

Integer

Number of indicator constraints

IISSOSs

Integer

Number of SOS constraints in IIS

IISIndicators

Integer

Number of indicator constraints in IIS

IIS Status of Special Constraints

Regarding the IIS (Irreducible Infeasible Set) calculation results for infeasible models, COPT provides related functions to obtain the IIS status of SOS constraints. Please refer to Handling Infeasible Models Section: Retrieving IIS Status of Special Constraints.