Matrix Modeling Method

The COPT Python API provides matrix modeling, supports NumPy multi-dimensional array, a two-dimensional NumPy matrix, SciPy compressed sparse column matrix ( csc_matrix ) and compressed sparse row matrix ( csr_matrix ) operations and can be combined with ordinary (scalar) variables and constraints.

NumPy version should be 1.23 or above, and no higher than 2.0 (since NumPy 2.0 introduced incompatible changes). Python minimum version requirement is 3.8. COPT mainly provides the following utilities:

Add multi-dimensional variables ( MVar ) and other related operations;
Construct multi-dimensional linear expressions ( MLinExpr ), add multi-dimensional linear constraints ( MConstr ) and other related operations;
Construct multi-dimensional quadratic expression ( MQuadExpr ), add multi-dimensional convex quadratic constraint ( QConstraint ) and other related operations.

Two different matrix modeling modes

The matrix modeling function provided by COPT currently supports two modes: original legacy mode and experimental mode. Among them, the legacy mode (by default) relies on Python’s NumPy library. 7.1.4 adds a new internal test mode, which is based on the built-in matrix modeling class implementation of the COPT C++ interface. The modeling speed could be improved to a certain extent compared with the former.

In the Python interface, the two modes can be controlled and switched through Model.matrixmodelmode , and the default is the legacy mode. Please set according to your usage scenarios:

Model.matrixmodelmode = "legacy" (default mode), depends on the NumPy library.
Model.matrixmodelmode = "experimental", C++ built-in matrix modeling class based on COPT ( NdArray ) , no external dependencies.

The functions and operation types supported by the two modes are slightly different.

1.The order (storage) method of MConstr.reshape()/MVar.reshape() , that is, the value of the function parameter order:

Legacy mode: supports both 'C' (by row) and 'F' (by column)
Experimental mode: only supports 'C' (by row)

2.Advanced indexing support:

Take the nqueen problem for example, only one queen can appear on each diagonal:

Legacy mode: Compatible with NumPy’s advanced index, which can be implemented as follows:

import coptpy as cp
import numpy as np

env = cp.Envr()
model = env.createModel()
model.matrixmodelmode = "legacy"
for i in range(1, 2*n):
    # At most one queen per diagonal
    diagn = (range(max(0, i-n), min(n, i)), range(min(n, i)-1, max(0, i-n)-1, -1))
    model.addConstrs(x[diagn].sum() <= 1, nameprefix="diag"+str(i))
    # At most one queen per anti-diagonal
    adiagn = (range(max(0, i-n), min(n, i)), range(max(0, n-i), min(n, 2*n-i)))
    model.addConstrs(x[adiagn].sum() <= 1, nameprefix="adiag"+str(i))

Experimental mode: The above advanced indexing method is not supported and requires the built-in Python indexing method, which can be implemented as follows:

import coptpy as cp
import numpy as np

env = cp.Envr()
model = env.createModel()
model.matrixmodelmode = "experimental"
for i i in range(-n+1, n):
    # At most one queen per diagonal
    model.addConstrs(x.diagonal(i).sum() <= 1, nameprefix="diag"+str(i))
    # At most one queen per anti-diagonal
    model.addConstrs(x[:, ::-1].diagonal(i).sum() <= 1, nameprefix="adiag"+str(i))

3.The relevant information obtained from matrix objects (objects such as MConstr and MVar), and the return value types are different:

Legacy mode: numpy.ndarray
Experimental mode: coptcore.NdArray

4.The supported dimensions are different:

Legacy mode: There is no restriction on dimensions and can support higher-dimensional matrices.
Experimental mode: The highest supported dimensions are three.

5.When adding multi-dimensional quadratic constraints, the support for variable dimensions participating in constraint formation and the type of return value are different:

Legacy mode: The dimension of the variables involved in forming the quadratic constraint needs to be 1 (i.e. vector), higher dimensions are not supported, and the return value type is QConstraint Class object.

import coptpy as cp
import numpy as np

env = cp.Envr()
model = env.createModel()
model.matrixmodelmode = "legacy"
Q = np.full((3, 3), 1)
mx = model.addMVar(3, nameprefix="mx")
# mqc <coptpy.QConstraint: >
mqc = model.addQConstr(mx@Q@mx<=1)

Experimental mode: The dimensions of variables participating in the quadratic constraints can be one or two-dimensional, and the return value type is MQConstr Class object.

import coptpy as cp
import numpy as np

env = cp.Envr()
model = env.createModel()
model.matrixmodelmode = "experimental"
Q = np.full((3, 3), 1)
mx = model.addMVar((3, 3), nameprefix="mx")
# mqc <coptpy.MQConstr: shape=(3, 3)>
mqc = model.addQConstr(mx@Q@mx <= 1)

Multi-dimensional Variables

Add multi-dimensional variable MVar

MVar constains operations related to multi-dimensional variables. Users can use Model.addMVar() to add a matmulti-dimensionalrix variable MVar of any dimension and shape to the model. In addition to the need of specifying the argument shape (matrix shape), the rest of the arguments are consistent with ordinary variables, including: lb , ub , vtype , nameprefix .

Add one-dimensional continuous multi-dimensional variables: x = Model.addMVar(3)

Add two-dimensional 3x3 binary multi-dimensional variables: y = Model.addMVar(shape(3,3), vtype=COPT.BINARY)

In addition, the MVar multi-dimensional variables can also be sliced, such as: y1 = y[:,0:2]

Get multi-dimensional variable related attributes:
- Number of dimensions: MVar.ndim
- The shape of the multi-dimensional variable: MVar.shape
- Number of elements in the multi-dimensional variable: MVar.size

Multi-dimensional array operations and expressions

Multi-dimensional Linear Expressions

Multi-dimensional variables and their coefficients (can be ndarray ) form a Multi-dimensional linear expression (MLinExpr), and the supported operations mainly include:

Matrix multiplication: A @ x

x = model.addMVar(3)
A = np.array([[1, 0, 1],[0, 0, 1]])
expr1 = A @ x

Vector inner product

x = model.addMVar(3)
c = np.array([1, 2, 3])
expr2 = c @ x

Multi-dimensional Quadratic Expression

Common multi-dimensional quadratic expressions and their corresponding mathematical forms are as follows:

x @ Q @ x: \(x^TQx\)
x @ x: \(x^Tx\)
x @ Q @ x + c @ x + b: \(x^TQx+c^Tx+b\)

Other multi-dimensional array operations

Combine with regular linear variables, regular linear expressions, and constants:

x = model.addMVar(3)
y = model.addVar()
c = np.array([1, 2, 3])
Q = np.full((3, 3), 1)
expr3 = 2 * x @ Q @ x + c @ x + 2 * y + 1

Self-increment/self-subtraction/self-multiplication operations:

mx = m.addMVar((3, 3))
B = np.array([[1, 0, 1], [0, 1, 1]])
expr_add = B @ mx
expr_add += 1
expr_add *= 2

Notes

When we directly print the multi-dimensional expression with print(MLinExpr)/print(MQuadExpr) , the shape of the expression will be output at the same time. When shape=() , it means that the expression is a scalar (single linear/quadratic expression), corresponding to ndim=0 , size=1 . The same is true for multi-dimensional variables MVar ;
When performing matrix multiplication (A@x), the matrix multiplication algorithm needs to be satisfied, and the number of columns of A and the number of rows of X need to be the same;
COPT supports the combination of MLinExpr and LinExpr , but it should be noted that the MLinExpr needs shape=() at this time, and the final returned expression is MLinExpr with shape=() .

Matrix Constraints

Matrix linear Constraints

COPT supports two ways of adding multi-dimensional linear constraints, and the format provided by the function arguments is different:

Model.addMConstr() that specifically adds multi-dimensional linear constraints, the arguments that can be specified are:
- A : coefficient matrix for linear constraints
- x : decision variables ( MVar )
- sense : type of linear constraint, the possible values are: 'L' (<=), 'G' (>=), 'E' (=)
- b : right-hand-side of linear constraints (vector with dimensions equal to the number of rows of matrix A)
- name : name prefix for linear constraints

x = model.addMVar(shape=3, vtype=COPT.BINARY, nameprefix='x')
A = np.array([[1, 2, 3], [3, 2, 1]])
b = np.array([2, 5])
mconstrs = model.addMConstr(A, x, 'L', b, nameprefix='c')
obj = np.array([1, 2, 1])
model.setObjective(obj @ x, COPT.MINIMIZE)

Matrix linear constraints can be regarded as a set of linear constraints, so Model.addConstrs() can also add multi-dimensional linear constraints:

x = model.addMVar(shape=3, vtype=COPT.BINARY, nameprefix='x')
A = np.array([[1, 2, 3], [3, 2, 1]])
b = np.array([2, 5])
mconstrs = model.addConstrs(A @ x <= b, nameprefix='c')
obj = np.array([1, 2, 1])
model.setObjective(obj @ x, COPT.MINIMIZE)

Quadratic Constraints

COPT supports two ways of constructing multi-dimensional quadratic constraints, and the format provided by the function arguments is different:

Model.addMQConstr() that specifically adds multi-dimensional quadratic constraints, the arguments that can be specified are:
- Q : quadratic coefficient matrix
- c : vector of linear term coefficients, or None if there is no linear term
- sense : type of quadratic constraint, the possible values are: 'L' (<=), 'G' (>=), 'E' (=)
- rhs : right-hand-side of quadratic constraints
- xQ_L : the left-hand variable of the quadratic coefficient matrix Q (vector whose length is consistent with the number of rows of the matrix Q )
- xQ_R : right-hand variable of the quadratic coefficient matrix Q (vector whose length is consistent with the number of columns of the matrix Q )
- xc : the variables for the linear term, or None if there is no linear term
- name : name prefix for quadratic constraints

Q = np.diag([3, 2, 1])
x = model.addMVar(3)
c1 = model.addMQConstr(Q, None, 'L', 1.0, x, x)

Model.addQConstr(), directly gives the multi-dimensional quadratic expression

lhs : multi-dimensional quadratic expression

sense : constraint type

rhs : right-hand-side of quadratic constraints
Q = np.diag([3, 2, 1])
x = model.addMVar(3)
c2 = model.addQConstr(x@Q@x<=1.0)

Objective function composed of multi-dimensional variables

COPT supports setting linear and quadratic objective functions, and provides two ways to set objective functions. The format of function arguments is different:

Model.setMObjective() that specifically sets the objective function composed of multi-dimensional variables, the arguments that can be specified are:
- Q : quadratic coefficient matrix, or None if the objective function is linear
- c : vector of linear term coefficients, or None if there is no linear term
- constant : the constant term of the objective function
- xQ_L: the left-hand variable of the quadratic term coefficient matrix Q (vector whose length is consistent with the number of rows of the matrix Q), or None if the objective function is linear
- xQ_R: the right-hand variable of the quadratic coefficient matrix Q (vector, whose length is consistent with the number of columns in the matrix Q), or None if the objective function is linear
- xc: the variable for the linear term, or None if there is no linear term
- sense: direction of optimization, possible values are: COPT.MINIMIZE or COPT.MAXIMIZE
Model.setObjective() that directly gives the expression of the objective function
- expr: Objective function expression, which can be linear or quadratic
- sense: optimization direction, possible values are: COPT.MINIMIZE or COPT.MINIMIZE

x = model.addMVar(shape=3, vtype=COPT.BINARY, nameprefix="x")
obj = np. array([1, 2, 1])
model.setObjective(obj @ x, COPT.MINIMIZE)

Regarding the matrix modeling method, the COPT Python interface provides multi-dimensional variables, (linear and convex quadratic) expressions, and matrix constraint classes respectively, and contains related operations. For the methods and specific introductions included, please refer to the corresponding part of the Python API :

Multi-dimensional variable: MVar
Multi-dimensional linear expression: MLinExpr
Multi-dimensional quadratic expressions: MQuadExpr
Matrix constraints: MConstr