Problem Creation Reference
- Mixed Integer Programs (MIP)
- Mixed Integer Quadratically Constrained Programs (MIQCQP)
- Problems With Special Constraints And Variables
There are two possibilities to input a problem into the FICO Xpress optimizer from R. The problem can be either incrementally formulated, for example by specifying each row separately, or by loading the entire problem at once. The FICO Xpress R interface provides a convenience function for loading an entire problem at once, which accepts R matrices as input for the various matrices that may describe the linear and quadratic constraint parts.
The xprs_loadproblemdata function accepts as input a list of named properties to declare all input at once. Internally, it uses the Xpress functions XPRSloadmip, XPRSloadmiqp etc. to translate the problem data into the internal formulation. The advantage of using a problem data object is that it lets the R user input matrices instead of sparse matrix representations for declaring linear and quadratic terms in the objective and constraints.
This page illustrates the two methods of formulating optimization problems for the FICO Xpress optimizer using an example of a mixed integer problem (MIP) and a mixed-integer quadratically constrained optimization problem (MIQCQP). As to the method that loads problem data at once, different ways of constructing matrices are discussed as well.
This page also shows the input of problems that contain some special constraints or variables, such as indicator constraints and semi-continuous variables, etc. It serves as a quick guide for the different elements of optimization problems and the interface functions to declare them.
Mixed Integer Programs (MIP)
We assume familiarity with the basic concepts of mathematical programming and its constraint notation. A mixed integer program is an optimization problem of the form
\begin{aligned}[t] &\min & cx\\ & \text{s.t.}& Ax &\{=, \leq, \geq\} b\\ & & \ell &\leq x \leq u\\ & & x_j &\in \{0, 1\} & \forall j \in \mathcal{B} \\ & & x_j &\in \mathbb{Z} & \forall j \in \mathcal{I}\\ & & \\ \end{aligned}
The Problem Data Representation
We use a simple MIP example to illustrate the two methods of loading problem data into the FICO Xpress optimizer.
\begin{aligned}[t] &\min & 2x_1 & +x_2 + 3x_3\\ & \text{s.t.}& 3x_1 & +2x_3 \geq\ 5\\ & & 6x_2 & -7x_3 \geq\ 8\\ & & & x_1\in \{0, 1\}\\ & & & x_2, x_3 \in \mathbb{Z} \\ & & 0 \leq x_2 &< \infty, 0 \leq x_3 < \infty\\ & & \\ \end{aligned}
The first way to input a problem into the FICO Xpress optimizer is to load the entire data at once using the function xprs_loadproblemdata. To realize this, we can write the constraint coefficients into an R matrix (in different ways, see next section), and then use the xprs_loadproblemdata function to load all data. Here we write the matrix in the example as a dense matrix and show the usage of xprs_loadproblemdata.
# create a list to store the problem data
problemdata <- list()
# write the constraint coefficients into a dense matrix
coefmatrix <- matrix(c(3, 0, 2, 0, 6,-7), nrow = 2, byrow = TRUE)
# load the matrix into the list as row coefficients
problemdata$A <- coefmatrix
# objective coefficients
problemdata$objcoef <- c(2, 1, 3)
# right-hand-side of the constraints
problemdata$rhs <- c(5, 8)
# row sense
problemdata$rowtype <- c("G", "G")
# specify all column types, where 'B' means 'binary' and 'I' means 'integer'
problemdata$coltype <- c('B', 'I', 'I')
#specify the indices of the binary and integer variables (use 0-based indexing)
problemdata$entind <- 0:2
# specify lower bounds and upper bounds for the columns
problemdata$lb <- c(0, 0, 0)
problemdata$ub <- c(1, Inf, Inf)
# specify the column names
problemdata$colname <- c("x_1", "x_2", "x_3")
# specify the row names
problemdata$rowname <- c("row1", "row2")
# problem name displayed when the solver solves the problem
problemdata$probname <- "MIPexample"
# load the problemdata into a problem 'p'
p <- xprs_loadproblemdata(problemdata = problemdata)
print(p)
# an alternative and equivalent way to do this is:
# p <- createprob()
# xprs_loadproblemdata(p, problemdata = problemdata) ## XPRESS problem object MIPexample ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons
# use `xprs_optimize` to solve the problem and see the results summary(xprs_optimize(p)) print(data.frame(Variable = problemdata$colname, Value = getsolution(p)$x))
## ## Final MIP objective : 8 ## Final MIP bound : 8 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 2 / 0 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 1 ## 2 x_2 3 ## 3 x_3 1
Working With R Matrices
There are several ways to represent the matrices in R according to the nature of the matrices. For low-dimensional matrices with mostly nonzero elements, we can use a dense specification as shown above, where every entry is specified.
Most high-dimensional matrices occurring in optimization problems are usually very sparse, i.e., most of the coefficients are zero. This fact is widely used in sparse matrix representations, which only store the nonzero coefficients of each column of a matrix together with an index into the rows that correspond to those nonzero entries. Using a sparse representation for such matrices saves a lot of memory. As a rule of thumb, we create sparse matrices when the problem data is too large to store every single of the ROWS \( \times \) COLS coefficients, or the matrix contains mostly 0 coefficients.
There are many ways to create sparse matrices. Here we still use the same MIP example to illustrate some possible methods to construct sparse matrices.
The first method only works for small-sized matrices because at creation we actually specify every element of the matrix.
We can always convert a sparse matrix back to a dense matrix:
# create a sparse matrix
coefmatrix_sparse1 <-
Matrix(c(3, 0, 2, 0, 6,-7),
nrow = 2,
byrow = TRUE,
sparse = TRUE)
coefmatrix_sparse1
# a sparse matrix can be converted to a dense matrix
coefmatrix_dense <- as.matrix(coefmatrix_sparse1)
print("The sparse matrix can be converted into a dense matrix:")
coefmatrix_dense ## 2 x 3 sparse Matrix of class "dgCMatrix" ## ## [1,] 3 . 2 ## [2,] . 6 -7 ## [1] "The sparse matrix can be converted into a dense matrix:" ## [,1] [,2] [,3] ## [1,] 3 0 2 ## [2,] 0 6 -7
In the second chunk, we first create a sparse matrix containing only 0’s, and then assign the nonzero elements:
# first create a sparse matrix containing only 0 values
coefmatrix_sparse2 <- Matrix(0, nrow = 2, ncol = 3, byrow = TRUE, sparse = TRUE,
doDiag = FALSE)
# then assign the nonzero values
coefmatrix_sparse2[1, c(1, 3)] <- c(3, 2)
coefmatrix_sparse2[2, 2:3] <- c(6, -7)
coefmatrix_sparse2 ## 2 x 3 sparse Matrix of class "dgCMatrix" ## ## [1,] 3 . 2 ## [2,] . 6 -7
The third one, which creates a sparse matrix in triplet format:
# create a sparse matirx in triplet format
coefmatrix_sparse3 <-
sparseMatrix(
i = c(1, 1, 2, 2),
j = c(1, 3, 2:3),
x = c(3, 2, 6,-7),
dims = c(2, 3)
)
coefmatrix_sparse3 ## 2 x 3 sparse Matrix of class "dgCMatrix" ## ## [1,] 3 . 2 ## [2,] . 6 -7
Incremental Formulation
Another way to input problem data into Xpress optimizer is to add the problem data incrementally. We can use the convenience functions xprs_addrow and xprs_addcol, which are exclusive to the R interface, or addrows and addcols to realize this. One difference between these two pairs of functions is that, for xprs_addrow and xprs_addcol, row type, row name, column type and column name can be specified inside these functions, whereas for addrows and addcols, row type can be defined inside function addrows, the other three features need to be specified using chgcoltype and addnames. Another difference is that xprs_addrow and xprs_addcol only add a single row and a single column, while addrows and addcols can add multiple rows and columns.
Of course, it is possible to mix the use of these functions to formulate problems.
Firstly we show how to use xprs_addcol and xprs_addrow to incrementally add the data.
# firstly, create a new empty problem 'prob1'
prob1 <- createprob()
# add the columns
xprs_addcol(prob1, lb = 0, ub = 1, coltype = 'B', name = "x_1", objcoef = 2)
xprs_addcol(prob1, lb = 0, ub = Inf, coltype = 'I', name = "x_2", objcoef = 1)
xprs_addcol(prob1, lb = 0, ub = Inf, coltype = 'I', name = "x_3", objcoef = 3)
# add the rows
xprs_addrow(prob1,
rowtype = "G",
rhs = 5,
name = "row1",
colind = c(0, 2),
rowcoef = c(3, 2),
)
xprs_addrow(prob1,
rowtype = "G",
rhs = 8,
name = "row2",
colind = c(1, 2),
rowcoef = c(6, -7),
)
# specify the name of the problem
setprobname(prob1, "MIPexample") # show the problem created print(prob1)
## XPRESS problem object MIPexample ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons
Next we show how to use addrows and addcols to incrementally add the problem data.
# firstly, create a new empty problem 'prob2'
prob2 <- createprob()
# add the columns
addcols(prob2,
objcoef = c(2, 1, 3),
start = c(0, 1, 2),
rowind = NULL,
rowcoef = NULL,
lb = c(0, 0, 0),
ub = c(1, Inf, Inf))
# specify the column types
chgcoltype(prob2, c(0, 1, 2), c('B', 'I', 'I'), ncols = 3)
# specify the column names
addnames(prob2, 2, c("x_1", "x_2", "x_3"), 0, 2)
# add the rows
addrows(prob2,
rowtype = "G",
rhs = 5,
start = 0,
colind = c(0, 2),
rowcoef = c(3, 2)
)
addrows(prob2,
rowtype = "G",
rhs = 8,
start= 0,
colind = c(1, 2),
rowcoef = c(6, -7)
)
# specify the row names
addnames(prob2, 1, c("row1", "row2"), 0, 1)
# specify the name of the problem
setprobname(prob2, "MIPexample") # show the problem created print(prob2)
## XPRESS problem object MIPexample ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons
Mixed Integer Quadratically Constrained Programs (MIQCQP)
Mixed Integer Quadratically Constrained Programming (MIQCQP) problems are an extension of Mixed Integer Programming (MIP) problems where the objective function and constraints may include a second order polynomial.
\begin{aligned}[t] &\min & \frac{1}{2} x^t Q_0 x + cx &\\ & \text{s.t.}& Ax + Q(x)&\{=, \leq, \geq\} b\\ & & \ell \leq x &\leq u\\ & & x_j &\in \{0, 1\} & \forall j \in \mathcal{B} \\ & & x_j &\in \mathbb{Z} & \forall j \in \mathcal{I}\\ & & \\ \end{aligned}
The function \( Q:\mathbb{R}^n \rightarrow \mathbb{R}^m \), \( Q(x) := (x^t Q_1x, x^t Q_2x, \dots, x^t Q_m x)^t \) is shorthand for the quadratic parts of the constraints.
The sets \( \mathcal{B} \) and \( \mathcal{I} \) denote the subsets of the columns (of \( A \)) that are restricted to binary or integer values, respectively. There are also some more advanced column types such as semi-continuous, semi-integer, and partial integer columns that are explained below.
The Problem Data Representation
As for MIP, there are two possibilities to input a problem into the FICO Xpress optimizer: loading at once and incremental formulation. To illustrate this, we use the example below, which extends the MIP example by some quadratic terms.
\begin{aligned}[t] &\min & \ x_1^2 + 2x_3^2+2x_1+x_2 -3x_3\\ & \text{s.t.}& 3x_1 + 2x_3^2 \leq\ 5\\ & & x_1^2 -7x_3 \leq\ 8\\ & & x_1\in \{0, 1\}\\ & & x_2, x_3 \in \mathbb{Z} \\ & & 0 \leq x_2 < \infty, 0 \leq x_3 < \infty\\ & & \\ \end{aligned}
In this example, the matrix \( Q_0 \) in the objective is: \begin{aligned}[t] && Q_0 = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 4\end{bmatrix} & & \\ \end{aligned}
The matrix \( Q_1 \) in the first row is: \begin{aligned}[t] && Q_1 = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 2\end{bmatrix} & & \\ \end{aligned}
The matrix \( Q_2 \) in the second row is:
\begin{aligned}[t] && Q_2 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0\end{bmatrix} & & \\ \end{aligned}
The first way we load the problem into the FICO Xpress optimizer at once is to use the function xprs_loadproblemdata.
qproblemdata <- list()
# objective coefficients
qproblemdata$objcoef <- c(2, 1, -3)
# write the constraint coefficients into a dense matrix
coefmatrix <- matrix(c(3, 0, 0, 0, 0,-7), nrow = 2, byrow = TRUE)
# load the matrix into the list as row coefficients
qproblemdata$A <- coefmatrix
# right-hand-side of the constraints
qproblemdata$rhs <- c(5, 8)
# row sense
qproblemdata$rowtype <- c("L", "L")
# specify all column types, where 'B' means 'binary' and 'I' means 'integer'
qproblemdata$coltype <- c('B', 'I', 'I')
#specify the indices of the binary and integer variables (use 0-based indexing)
qproblemdata$entind <- 0:2
# specify lower bounds and upper bounds for the columns
qproblemdata$lb <- c(0, 0, 0)
qproblemdata$ub <- c(1, Inf, Inf)
# specify the column names
qproblemdata$colname <- c("x_1", "x_2", "x_3")
# specify the row names
qproblemdata$rowname <- c("row1", "row2")
# problem Name displayed when the solver solves the problem
qproblemdata$probname <- "MIQCQPexample"
# # quadratic part in objective
# # 1.C-Style notation
# qproblemdata$nobjqcoef <- 2
# qproblemdata$objqcol1 <- c(0, 2)
# qproblemdata$objqcol2 <- c(0, 2)
# qproblemdata$objqcoef <- c(2, 4)
# 2.Matrix notation
qproblemdata$Qobj <-
Matrix(
c(2, 0, 0, 0, 0, 0, 0, 0, 4),
nrow = 3,
byrow = TRUE,
sparse = TRUE,
doDiag = FALSE
)
# # quadratic part in constraints
# # 1.C-Style notation
# qproblemdata$nqrows <- 2
# qproblemdata$qrowind <- c(0, 1)
# qproblemdata$nrowqcoefs <- c(1, 1)
# qproblemdata$rowqcol1 <- c(2, 0)
# qproblemdata$rowqcol2 <- c(2, 0)
# qproblemdata$rowqcoef <- c(2, 1)
# 2.Matrix notation
qproblemdata$Qrowlist <- list()
qproblemdata$Qrowlist[[1]] <-
Matrix(
c(0, 0, 0, 0, 0, 0, 0, 0, 2),
nrow = 3,
byrow = TRUE,
sparse = TRUE,
doDiag = FALSE
)
qproblemdata$Qrowlist[[2]] <-
Matrix(
c(1, 0, 0, 0, 0, 0, 0, 0, 0),
nrow = 3,
byrow = TRUE,
sparse = TRUE,
doDiag = FALSE
)
# load the problemdata into a problem 'qcqp'
qcqp <- xprs_loadproblemdata(problemdata = qproblemdata) ## 'as(<dsCMatrix>, "dgTMatrix")' is deprecated.
## Use 'as(as(., "generalMatrix"), "TsparseMatrix")' instead.
## See help("Deprecated") and help("Matrix-deprecated"). print(qcqp) # an alternative and equivalent way to do this is: # p <- createprob() # xprs_loadproblemdata(p, problemdata=qproblemdata)
## XPRESS problem object MIQCQPexample ## 2 rows 3 cols 2 elems ## 3 entities 0 sets 0 indicators ## 2 qelems 2 qcelems ## 0 gencons 0 pwlcons
# use `xprs_optimize` to solve the problem and see the results summary(xprs_optimize(qcqp)) print(data.frame(Variable = qproblemdata$colname, Value = getsolution(qcqp)$x))
## ## Final MIP objective : -1 ## Final MIP bound : -1 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 0 ## 2 x_2 0 ## 3 x_3 1
Working With R Matrices
Like for the linear part of the constraints (matrix \( A \)) and the quadratic objective matrix and the quadratic terms in constraints can be specified as matrices in sparse or dense representation.
In the above section, we specify all the matrices as dense matrices, and now we show how to construct them as sparse matrices.
The first way:
# create sparse matrix
qobjmat_sparse1 <-
Matrix(
c(2, 0, 0, 0, 0, 0, 0, 0, 4),
nrow = 3,
byrow = TRUE,
sparse = TRUE
)
qobjmat_sparse1
qrowmat1_sparse1 <-
Matrix(
c(0, 0, 0, 0, 0, 0, 0, 0, 2),
nrow = 3,
byrow = TRUE,
sparse = TRUE
)
qrowmat1_sparse1
qrowmat2_sparse1 <-
Matrix(
c(1, 0, 0, 0, 0, 0, 0, 0, 0),
nrow = 3,
byrow = TRUE,
sparse = TRUE
)
qrowmat2_sparse1 ## 3 x 3 diagonal matrix of class "ddiMatrix" ## [,1] [,2] [,3] ## [1,] 2 . . ## [2,] . 0 . ## [3,] . . 4 ## 3 x 3 diagonal matrix of class "ddiMatrix" ## [,1] [,2] [,3] ## [1,] 0 . . ## [2,] . 0 . ## [3,] . . 2 ## 3 x 3 diagonal matrix of class "ddiMatrix" ## [,1] [,2] [,3] ## [1,] 1 . . ## [2,] . 0 . ## [3,] . . 0
The second way:
# first create sparse matrices containing only 0 values
qobjmat_sparse2 <-
Matrix(
0,
nrow = 3,
ncol = 3,
byrow = TRUE,
sparse = TRUE,
doDiag = FALSE
)
qrowmat1_sparse2 <-
Matrix(
0,
nrow = 3,
ncol = 3,
byrow = TRUE,
sparse = TRUE,
doDiag = FALSE
)
qrowmat2_sparse2 <-
Matrix(
0,
nrow = 3,
ncol = 3,
byrow = TRUE,
sparse = TRUE,
doDiag = FALSE
)
# then assign the nonzero values
qobjmat_sparse2[1, 1] <- 2
qobjmat_sparse2[3, 3] <- 4
qrowmat1_sparse2[3, 3] <- 2
qrowmat2_sparse2[1, 1] <- 1
qobjmat_sparse2
qrowmat1_sparse2
qrowmat2_sparse2 ## 3 x 3 sparse Matrix of class "dsCMatrix" ## ## [1,] 2 . . ## [2,] . . . ## [3,] . . 4 ## 3 x 3 sparse Matrix of class "dsCMatrix" ## ## [1,] . . . ## [2,] . . . ## [3,] . . 2 ## 3 x 3 sparse Matrix of class "dsCMatrix" ## ## [1,] 1 . . ## [2,] . . . ## [3,] . . .
The third way:
# create sparse matrices in triplet format
qobjmat_sparse3 <-
sparseMatrix(
i = c(1, 3),
j = c(1, 3),
x = c(2, 4),
dims = c(3, 3)
)
qobjmat_sparse3
qrowmat1_sparse3 <-
sparseMatrix(
i = 3,
j = 3,
x = 2,
dims = c(3, 3)
)
qrowmat1_sparse3
qrowmat2_sparse3 <-
sparseMatrix(
i = 1,
j = 1,
x = 1,
dims = c(3, 3)
)
qrowmat2_sparse3 ## 3 x 3 sparse Matrix of class "dgCMatrix" ## ## [1,] 2 . . ## [2,] . . . ## [3,] . . 4 ## 3 x 3 sparse Matrix of class "dgCMatrix" ## ## [1,] . . . ## [2,] . . . ## [3,] . . 2 ## 3 x 3 sparse Matrix of class "dgCMatrix" ## ## [1,] 1 . . ## [2,] . . . ## [3,] . . .
Incremental Formulation
We can also formulate the MIQCQP example incrementally, and same as MIP, we can use the functions xprs_addrow and xprs_addcol, or addrows and addcols to realize this. The differences between these two pairs of functions are described in the MIP section. Here, we only show the usage of the convenience functions xprs_addrow and xprs_addcol.
As for the quadratic terms, we always use chgmqobj to add quadratic terms to the objective and addqmatrix to add quadratic terms to constraints.
# firstly, create a new empty problem 'qcqp1'
qcqp1 <- createprob()
# add the columns
xprs_addcol(qcqp1, lb = 0, ub = 1, coltype = 'B', name = "x_1", objcoef = 2)
xprs_addcol(qcqp1, lb = 0, ub = Inf, coltype = 'I', name = "x_2", objcoef = 1)
xprs_addcol(qcqp1, lb = 0, ub = Inf, coltype = 'I', name = "x_3", objcoef = -3)
# add the quadratic terms in objective
# since the quadratic matrix is assumed to be symmetric, so specifying the upper
# diagonal part of the matrix is enough, and the off-diagonal coefficients can be
# specified as they are.
chgmqobj(qcqp1, c(0, 2), c(0, 2), c(2, 4), 2)
# add the rows
xprs_addrow(qcqp1,
rowtype = "L",
rhs = 5,
name = "row1",
colind = 0,
rowcoef = 3,
)
xprs_addrow(qcqp1,
rowtype = "L",
rhs = 8,
name = "row2",
colind = 2,
rowcoef = -7,
)
# add quadratic terms in the constraints
addqmatrix(qcqp1,
row = 0,
rowqcol1 = 2,
rowqcol2 = 2,
rowqcoef = 2
)
addqmatrix(qcqp1,
row = 1,
rowqcol1 = 0,
rowqcol2 = 0,
rowqcoef = 1
)
# specify the name of the problem
setprobname(qcqp1, "MIQCQPexample") # show the problem created print(qcqp1)
## XPRESS problem object MIQCQPexample ## 2 rows 3 cols 2 elems ## 3 entities 0 sets 0 indicators ## 2 qelems 2 qcelems ## 0 gencons 0 pwlcons
# use `xprs_optimize` to solve the problem and see the results
summary(xprs_optimize(qcqp1))
print(data.frame(Variable=c("x_1", "x_2", "x_3"), Value=getsolution(qcqp1)$x)) ## ## Final MIP objective : -1 ## Final MIP bound : -1 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 0 ## 2 x_2 0 ## 3 x_3 1
Problems With Special Constraints And Variables
In this section, we display some examples that contain special constraints or variables and show how to input them into the FICO Xpress optimizer. To see how these special constraints or variables can have effect on the solutions, we use examples based on the MIP example so that we can compare the new solutions obtained with the MIP solution. For convenience, we create a function load_MIP_example to load the MIP example and we will use this function at the begining of each sub-section and then make adjustments on the MIP example incrementally (adding constraints or changing variable types, etc.).
load_MIP_example = function(){
# firstly, create a new empty problem 'prob'
prob <- createprob()
# add the columns
xprs_addcol(prob, lb = 0, ub = 1, coltype = 'B', name = "x_1", objcoef = 2)
xprs_addcol(prob, lb = 0, ub = Inf, coltype = 'I', name = "x_2", objcoef = 1)
xprs_addcol(prob, lb = 0, ub = Inf, coltype = 'I', name = "x_3", objcoef = 3)
# add the rows
xprs_addrow(prob,
rowtype = "G",
rhs = 5,
name = "row1",
colind = c(0, 2),
rowcoef = c(3, 2),
)
xprs_addrow(prob,
rowtype = "G",
rhs = 8,
name = "row2",
colind = c(1, 2),
rowcoef = c(6, -7),
)
# return 'prob'
prob
} Notice that for the constraints and special variables that will be discussed in this section, ‘Indicator Constraints’, ‘General Constraints’ and ‘Piecewise Linear Constraints’ cannot be specified when using the function xprs_loadproblemdata to load the problem at once. Instead, they need to be added using corresponding functions.
Indicator Constraints
Indicator constraints are constraints each with a specified associated binary ‘controlling’ variable where we assume the constraint must be satisfied when the binary variable is at a specified binary value; otherwise the constraint does not need to be satisfied.
We use an extension of the MIP example to show the formulation of problems with indicator constraints. Based on the MIP example, we add the constraint that if the binary variable \( x_1 \) takes value 1, then integer variable \( x_3 \) must be 0. Mathematically, we want to impose the implication:
\begin{aligned}[t] x_1 = 1 \Rightarrow x_3 = 0 \end{aligned}
To add this constraint, we first add a new row \( x_3 = 0 \), and then use the function setindicators to specify the indicator constraint.
# firstly, load the MIP example to a problem 'probIndicator'
probIndicator <- load_MIP_example()
# add the new row x_3 = 0
xprs_addrow(probIndicator,
rowtype = "E",
rhs = 0,
name = "row3",
colind = 2,
rowcoef = 1,
)
# add the indicator implication between variable x_1 and the new row
setindicators(probIndicator,
rowind = 2,
colind = 0,
complement = 1 # row is active when x_1 = 1
)
# specify the name of the problem
setprobname(probIndicator, "IndicatorConstraintExample") Now we solve this example. We see that the solution satisfies the indicator constraint, where \( x_1 \) takes 0 and thus \( x_3 \) can take nonzero value 3.
# show the problem created
print(probIndicator)
summary(xprs_optimize(probIndicator))
print(data.frame(
Variable = c("x1", "x2", "x3"),
Value = getsolution(probIndicator)$x
)) ## XPRESS problem object IndicatorConstraintExample ## 3 rows 3 cols 5 elems ## 3 entities 0 sets 1 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons ## ## Final MIP objective : 14 ## Final MIP bound : 14 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x1 0 ## 2 x2 5 ## 3 x3 3
General Constraints
General constraints are specific type of MIP constraints to model min, max, and, or, and absolute value relationships between two or more variables.
Here we still use the MIP example and add a general constraint that \( x_3 \) takes the minimum value between 2 and \( x_2 \), mathematically, we require:
\begin{aligned}[t] x_3 = \min \left\{ x_2, 2 \right\} \end{aligned}
We use the function addgencons to add this general constraint:
# firstly, load the MIP example to a problem 'probGeneral'
probGeneral <- load_MIP_example()
# set the general constraint:
addgencons(probGeneral,
contype = 1,
resultant = 2,
colstart = 0,
colind = 1,
valstart = 0,
val = 2)
# specify the name of the problem
setprobname(probGeneral, "GeneralConstraintExample") Now we solve this example. We see that the solution satisfies the general constraint, because \( x_3 \) takes the value \( \min \left\{ x_2=4, \ 2 \right\}=2 \).
# show the problem created
print(probGeneral)
summary(xprs_optimize(probGeneral))
print(data.frame(
Variable = c("x1", "x2", "x3"),
Value = getsolution(probGeneral)$x
)) ## XPRESS problem object GeneralConstraintExample ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 1 gencons 0 pwlcons ## ## Final MIP objective : 12 ## Final MIP bound : 12 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x1 1 ## 2 x2 4 ## 3 x3 2
Piecewise Linear Constraints
Piecewise linear constraints are constraints that define a piecewise linear relationship between two variables. These are defined via a set of breakpoints with linearly interpolated values between and beyond them (with the slope before the first and after the last point continuing the slope between the first/last two points). The piece-wise linear functions are allowed to be discontinuous by defining multiple points with the same value of the input variable x, in which case the output variable y is allowed to take any value between the corresponding y-values of these breakpoints, while the first of them will define the slope before and the last will define the slope after this x-value.
Based on the MIP example, we add a piecewise linear constraint between \( x_2 \) and \( x_3 \): \( x_2 = f(x_3) \), where:
\begin{aligned}[t] x_2 = f\left( x_3 \right)= \left\{ \begin{array}{lr} 2x_3, & \textsf{if}\ 0\leq x_3\leq 2\\ \frac{1}{2}\ x_3+3, & \textsf{if}\ 2< x_3<\infty \\ \end{array} \right. \end{aligned}
This function can be defined using the breakpoints (0, 0), (2, 4), and (4, 5). Note that the last breakpoint could also be replaced, e.g., by (3, 4.5). We will use the function addpwlcons to add this piecewise linear constraint.
# firstly, load the MIP example to a problem 'probPWL'
probPWL <- load_MIP_example()
# set the piecewise linear constraint:
addpwlcons(probPWL,
colind = 2,
resultant = 1,
start = 0,
xval = c(0, 2, 4),
yval = c(0, 4, 5))
# specify the name of the problem
setprobname(probPWL, "PWLExample") Now we solve this example. We see that the solution satisfies the piecewise linear constraint, where \( x_3=2 \) and thus \( x_2=2x_3=4 \).
# show the problem created
print(probPWL)
summary(xprs_optimize(probPWL))
print(data.frame(
Variable = c("x1", "x2", "x3"),
Value = getsolution(probPWL)$x
)) ## XPRESS problem object PWLExample ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 1 pwlcons ## ## Final MIP objective : 12 ## Final MIP bound : 12 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x1 1 ## 2 x2 4 ## 3 x3 2
Special Ordered Set Of Type 1 (SOS1)
SOS1 is a set of decision variables ordered by a set of specified continuous values (or reference values) of which at most one can take a nonzero value. Note that SOS constraints must be input in sparse row representation.
We illustrate the input of SOS1 by an extension of the MIP example. Here we only allow one of the three decision variables to assume a nonzero value by imposing the restriction
\begin{aligned}[t] \text{SOS1}\left(x_1, x_2, x_3\right) \end{aligned} A mathematically equivalent formulation of this SOS1 restriction requires auxiliary binary variables. We introduce one auxiliary binary variables for each decision variable to indicate whether they are 0 or nonzero. We restrict the sum of these auxiliary binary variables to 1 to ensure only one variable takes nonzero value. Since \( x_1 \) itself is a binary variable, we only need two binary variables \( a_2 \) and \( a_3 \) for \( x_2 \) and \( x_3 \) such that:
\begin{aligned}[t] x_j= 0 \Leftrightarrow a_j = 0 \quad \text{ for } j \in \{2, 3\} \end{aligned} Note that this relationship can only be imposed through a linear constraint if the variable \( x_j \) has a finite upper bound.
Finally, we restrict the sum of these binary variables:
\begin{aligned}[t] x_1 + a_2 + a_3 \leq 1 \end{aligned}
If we add this constraint to the original MIP example, the problem will be infeasible. So we change the row coefficient for \( x_3 \) in the second row “row2” from ‘-7’ to ‘7’, and keep everything else the same.
SOS-type constraints are called “Sets” in Xpress terminology. To add this SOS1 restriction, we use the function addsets.
# firstly, load the MIP example to a problem 'probSOS1'
probSOS1 <- load_MIP_example()
# change the row coefficient of x_3 in the second row from '-7' to 7
chgcoef(probSOS1, 1, 2, 7)
# add the SOS1 set
addsets(probSOS1,
settype = '1',
start = 0,
colind = c(0, 1, 2),
refval = c(1, 2, 3))
# specify the name of the problem
setprobname(probSOS1, "SOS1Example") Now we solve this example. We see that the solution satisfies the SOS1 restriction, where only \( x_3 \) takes nonzero value 3.
# show the problem created
print(probSOS1)
summary(xprs_optimize(probSOS1))
print(data.frame(
Variable = c("x1", "x2", "x3"),
Value = getsolution(probSOS1)$x
)) ## XPRESS problem object SOS1Example ## 2 rows 3 cols 4 elems ## 3 entities 1 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons ## ## Final MIP objective : 9 ## Final MIP bound : 9 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x1 0 ## 2 x2 0 ## 3 x3 3
SOS1 can also be specified when loading the problem at once, so next we will show how to add SOS1 when using function xprs_loadproblemdata.
# create a list to store the problem data
pSOS1data <- list()
# write the constraint coefficients into a dense matrix
coefmatrix <- matrix(c(3, 0, 2, 0, 6, 7), nrow = 2, byrow = TRUE)
# load the matrix into the list as row coefficients
pSOS1data$A <- coefmatrix
# objective coefficients
pSOS1data$objcoef <- c(2, 1, 3)
# right-hand-side of the constraints
pSOS1data$rhs <- c(5, 8)
# row sense
pSOS1data$rowtype <- c("G", "G")
# specify all column types, where 'B' means 'binary' and 'I' means 'integer'
pSOS1data$coltype <- c('B', 'I', 'I')
#specify the indices of the binary and integer variables (use 0-based indexing)
pSOS1data$entind <- 0:2
# specify lower bounds and upper bounds for the columns
pSOS1data$lb <- c(0, 0, 0)
pSOS1data$ub <- c(1, Inf, Inf)
# specify the column names
pSOS1data$colname <- c("x_1", "x_2", "x_3")
# specify the row names
pSOS1data$rowname <- c("row1", "row2")
# problem Name displayed when the solver solves the problem
pSOS1data$probname <- "SOS1Example"
# specify SOS1
pSOS1data$settype <- '1'
pSOS1data$setstart <- c(0, 3)
pSOS1data$setind <- c(0, 1, 2)
pSOS1data$refval <- c(1, 2, 3)
# load the problemdata into a problem 'pSOS1'
pSOS1 <- xprs_loadproblemdata(problemdata=pSOS1data)
print(pSOS1) ## XPRESS problem object SOS1Example ## 2 rows 3 cols 4 elems ## 3 entities 1 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons
We solve this example and we get the same solution as before.
# use `xprs_optimize` to solve the problem and see the results summary(xprs_optimize(pSOS1)) print(data.frame(Variable = pSOS1data$colname, Value = getsolution(pSOS1)$x))
## ## Final MIP objective : 9 ## Final MIP bound : 9 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 0 ## 2 x_2 0 ## 3 x_3 3
Special Ordered Set Of Type 2 (SOS2)
SOS2 is a set of variables ordered by a set of specified continuous values (or reference values) of which at most two can be nonzero, and if two are nonzero then they must be consecutive in their ordering. Note that SOS constraints must be input in sparse row representation.
We illustrate the input of SOS2 by an extension of the MIP example as well, here we only allow two consecutive decision variables to take nonzero values and we change the upper bounds of \( x_2 \) and \( x_3 \) both from infinity to 10.
As for SOS1, an alternative, mathematically equivalent representation of an SOS2 constraint, requires auxiliary binary variables \( a_2 \) and \( a_3 \), of which at most can be set to 1: \begin{aligned}[t] x_1 + a_2 + a_3 \leq 1 \end{aligned}
But this time, we set the constraints for each variable in this way:
\begin{aligned}[t] && x_1\leq x_1\cdot1 \\ && x_2\leq (x_1 + a_2)\cdot 10 \\ && x_3\leq (a_2 + a_3)\cdot 10 \end{aligned}
So for example, if the constraint enforces \( a_2 \) to be 1, then \( x_1 \) must be 0, and \( x_2 \) and \( x_3 \) are allowed to take nonzero values, which satisfy the SOS2 restriction.
To add this SOS2 restriction, we use again the function addsets with the appropriate set type.
# firstly, load the MIP example to a problem 'probSOS2'
probSOS2 <- load_MIP_example()
# change the upper bounds for both x_2 and x_3
chgbounds(probSOS2,
colind = c(1, 2),
bndtype = c('U', 'U'),
bndval = c(10, 10))
# add the SOS2 set
addsets(probSOS2,
settype = '2',
start = 0,
colind = c(0, 1, 2),
refval = c(1, 2, 3))
# specify the name of the problem
setprobname(probSOS2, "SOS2Example") Now we solve this example. We see that the solution satisfies the SOS2 restriction, where only \( x_2 \) and \( x_3 \) take nonzero values 5 and 3.
# show the problem created
print(probSOS2)
summary(xprs_optimize(probSOS2))
print(data.frame(
Variable = c("x_1", "x_2", "x_3"),
Value = getsolution(probSOS2)$x
)) ## XPRESS problem object SOS2Example ## 2 rows 3 cols 4 elems ## 3 entities 1 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons ## ## Final MIP objective : 14 ## Final MIP bound : 14 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 0 ## 2 x_2 5 ## 3 x_3 3
SOS2 can also be specified when loading the problem at once, so next we will show how to add SOS2 when using function xprs_loadproblemdata.
# create a list to store the problem data
pSOS2data <- list()
# write the constraint coefficients into a dense matrix
coefmatrix <- matrix(c(3, 0, 2, 0, 6,-7), nrow = 2, byrow = TRUE)
# load the matrix into the list as row coefficients
pSOS2data$A <- coefmatrix
# objective coefficients
pSOS2data$objcoef <- c(2, 1, 3)
# right-hand-side of the constraints
pSOS2data$rhs <- c(5, 8)
# row sense
pSOS2data$rowtype <- c("G", "G")
# specify all column types, where 'B' means 'binary' and 'I' means 'integer'
pSOS2data$coltype <- c('B', 'I', 'I')
#specify the indices of the binary and integer variables (use 0-based indexing)
pSOS2data$entind <- 0:2
# specify lower bounds and upper bounds for the columns
pSOS2data$lb <- c(0, 1, 1)
pSOS2data$ub <- c(1, 10, 10)
# specify the column names
pSOS2data$colname <- c("x_1", "x_2", "x_3")
# specify the row names
pSOS2data$rowname <- c("row1", "row2")
# problem Name displayed when the solver solves the problem
pSOS2data$probname <- "SOS2Example"
# specify SOS2
pSOS2data$settype <- '2'
pSOS2data$setstart <- c(0, 3)
pSOS2data$setind <- c(0, 1, 2)
pSOS2data$refval <- c(1, 2, 3)
# load the problemdata into a problem 'p'
pSOS2 <- xprs_loadproblemdata(problemdata = pSOS2data)
print(pSOS2) ## XPRESS problem object SOS2Example ## 2 rows 3 cols 4 elems ## 3 entities 1 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons
We solve this example and we get the same solution as before.
# use `xprs_optimize` to solve the problem and see the results
summary(xprs_optimize(pSOS2))
print(data.frame(
Variable = c("x_1", "x_2", "x_3"),
Value = getsolution(pSOS2)$x
)) ## ## Final MIP objective : 14 ## Final MIP bound : 14 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 0 ## 2 x_2 5 ## 3 x_3 3
Semi-Continuous Variables
Semi-continuous variables are decision variables that either have value 0, or a continuous value above a specified nonnegative limit. To show how we specify semi-continuous variables when formulating problems, we use the MIP example but change the variable type of \( x_3 \) from integer to semi-continuous, and set the nonzero limit of \( x_3 \) as 2:
\begin{aligned}[t] &\min & 2x_1 & +x_2 + 3x_3\\ & \text{s.t.}& 3x_1 & +2x_3 \geq\ 5\\ & & 6x_2 & -7x_3 \geq\ 8\\ & & & x_1\in \{0, 1\}\\ & & & x_2 \in \mathbb{Z}\ , 0 \leq x_2 < \infty \\ & & & x_3\in \mathcal{S}, \ x_3=0 \ \text{or } \ 2\leq x_3 < \infty \ \ and\ \ x_3 \in \mathbb{R}\\ & & \\ \end{aligned}
Firstly we load the MIP example, then use chgcoltype to change the type of \( x_3 \) and use chglblimit to specify the nonzero limit of \( x_3 \).
# firstly, load the MIP example to a problem 'problemS' problemS <- load_MIP_example() # change the type of x_3 chgcoltype(problemS, 2, 'S') # set the lower bound for semi-continuous variable x_3 chgglblimit(problemS, 2, 2) # specify the name of the problem setprobname(problemS, "MIPExampleWithS")
Notice that for setting a semi-continuous variable, we can directly declare its type as ‘S’ when adding the column. Or when we incrementally formulate the problem, we can declare a semi-continuous variable by function xprs_addcol or adcols and set ‘coltype’ as ‘S’.
Now we solve this example. We see that the solution satisfies the semi-continuous restriction on \( x_3 \), whose value changed from 1 to 2.
# show the problem created
print(problemS)
summary(xprs_optimize(problemS))
print(data.frame(
Variable = c("x_1", "x_2", "x_3"),
Value = getsolution(problemS)$x
)) ## XPRESS problem object MIPExampleWithS ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons ## ## Final MIP objective : 12 ## Final MIP bound : 12 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 1 ## 2 x_2 4 ## 3 x_3 2
More functions to interact with semi-continuous variables are: chgbounds, chgcoef, chgobj, delcols and getcoltype.
Semi-continuous Integer Variables
Semi-continuous integer variables are decision variables that either have value 0, or an integer value above a specified nonnegative limit. To show how we specify semi-continuous integer when formulating problems, we use the MIP example but change the variable type of \( x_3 \) from integer to semi-continuous integer, and set the nonzero limit of \( x_3 \) as 2:
\begin{aligned}[t] &\min & 2x_1 & +x_2 + 3x_3\\ & \text{s.t.}& 3x_1 & +2x_3 \geq\ 5\\ & & 6x_2 & -7x_3 \geq\ 8\\ & & & x_1\in \{0, 1\}\\ & & & x_2 \in \mathbb{Z}\ , 0 \leq x_2 < \infty \\ & & & x_3\in \mathcal{R}, \ x_3=0 \ \text{or } \ 2\leq x_3 < \infty \ and \ x_3 \in \mathbb{Z}\\ & & \\ \end{aligned}
Firstly, we load the MIP example, then use chgcoltype to change the type of \( x_3 \) and use chglblimit to specify the nonzero limit of \( x_3 \).
# firstly, load the MIP example to a problem 'problemR' problemR <- load_MIP_example() # change the type of x_3 chgcoltype(problemR, 2, 'R') # set the lower bound for semi-continuous integer variable x_3 chgglblimit(problemR, 2, 2) # specify the name of the problem setprobname(problemR, "MIPExampleWithR")
Notice that for setting a semi-continuous integer variable, we can directly declare its type as ‘R’ when adding the column. Or when we incrementally formulate the problem, we can declare a semi-continuous variable by function xprs_addcol or adcols and set ‘coltype’ as ‘R’.
Now we solve this example. We see that the solution satisfies the semi-continuous integer restriction on \( x_3 \), whose value changed from 1 to 2.
# show the problem created
print(problemR)
summary(xprs_optimize(problemR))
print(data.frame(
Variable = c("x_1", "x_2", "x_3"),
Value = getsolution(problemR)$x
)) ## XPRESS problem object MIPExampleWithR ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons ## ## Final MIP objective : 12 ## Final MIP bound : 12 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 1 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 1 ## 2 x_2 4 ## 3 x_3 2
More functions to interact with semi-continuous integer variables are: chgbounds, chgcoef, chgobj, delcols, and getcoltype.
Partial Integer Variables
Partial integer variables are decision variables that have integer values below a specified limit and continuous values above the limit. To show how we specify partial integer variables when formulating problems, we use a modification of the MIP example where we change the variable type of \( x_2 \) from integer to partial integer, and set the specified limit of \( x_2 \) as 2:
\begin{aligned}[t] &\min & 2x_1 & +x_2 + 3x_3\\ & \text{s.t.}& 3x_1 & +2x_3 \geq\ 5\\ & & 6x_2 & -7x_3 \geq\ 8\\ & & & x_1\in \{0, 1\}\\ & & & x_2 \in \mathcal{P}\ , \ \ x_2\in \mathbb{Z} \ \ \ \text{if} \ 0\leq x_2\leq 2, \ \text{and}\ \ x_2\in \mathbb{R}\ \ \text{if} \ x_2> 2\\ & & & x_3\in \mathbb{Z}, \ 0 \leq x_3 < \infty\\ & & \\ \end{aligned}
Firstly, we load the MIP example, then use chgcoltype to change the type of \( x_2 \) and use chglblimit to specify the nonzero limit of \( x_2 \).
# firstly, load the MIP example to a problem 'problemP' problemP <- load_MIP_example() # change the type of x_2 chgcoltype(problemP, 1, 'P') # set the specified limit for partial integer variable x_2 chgglblimit(problemP, 1, 2) # specify the name of the problem setprobname(problemP, "MIPExampleWithP")
Notice that for setting a partial integer variable, we can directly declare its type as ‘P’ when adding the column. Or when we incrementally formulate the problem, we can declare a partial integer variable by function xprs_addcol or adcols and set ‘coltype’ as ‘P’.
Now we solve this example. We see that the solution satisfies the partial integer restriction on \( x_2 \), whose value changed from 3 to 2.5.
# show the problem created
print(problemP)
summary(xprs_optimize(problemP))
print(data.frame(
Variable = c("x_1", "x_2", "x_3"),
Value = getsolution(problemP)$x
)) ## XPRESS problem object MIPExampleWithP ## 2 rows 3 cols 4 elems ## 3 entities 0 sets 0 indicators ## 0 qelems 0 qcelems ## 0 gencons 0 pwlcons ## ## Final MIP objective : 7.5 ## Final MIP bound : 7.5 ## Solution time / primaldual integral : 0s / 0.00% ## Number of solutions found / nodes : 3 / 1 ## MIPSTATUS: 6 ## Variable Value ## 1 x_1 1.0 ## 2 x_2 2.5 ## 3 x_3 1.0
More functions to interact with partial integer variables are: chgbounds, chgobj, chgcoef, delcols, and getcoltype.
© 2001-2024 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.