## Generate a random problem
set.seed(0)
m <- 40
n <- 25
A <- matrix(runif(m * n), nrow = m, ncol = n)
b <- rnorm(m)Mixed-Integer Quadratic Program
Introduction
A mixed-integer quadratic program (MIQP) is an optimization problem of the form
\[ \begin{array}{ll} \mbox{minimize} & x^T Q x + q^T x + r \\ \mbox{subject to} & x \in \mathcal{C}\\ & x \in \mathbf{Z}^n, \end{array} \]
where \(x \in \mathbf{Z}^n\) is the optimization variable (\(\mathbf{Z}^n\) is the set of \(n\)-dimensional vectors with integer-valued components), \(Q \in \mathbf{S}_+^n\) (the set of \(n \times n\) symmetric positive semidefinite matrices), \(q \in \mathbf{R}^n\), and \(r \in \mathbf{R}\) are problem data, and \(\mathcal{C}\) is some convex set.
An example of an MIQP is mixed-integer least squares, which has the form
\[ \begin{array}{ll} \mbox{minimize} & \|Ax-b\|_2^2 \\ \mbox{subject to} & x \in \mathbf{Z}^n, \end{array} \]
where \(x \in \mathbf{Z}^n\) is the optimization variable, and \(A \in \mathbf{R}^{m \times n}\) and \(b \in \mathbf{R}^{m}\) are the problem data. A solution \(x^{\star}\) of this problem will be a vector in \(\mathbf{Z}^n\) that minimizes \(\|Ax-b\|_2^2\).
Example
In the following code, we solve a mixed-integer least-squares problem with CVXR. We use the GUROBI solver which supports mixed-integer quadratic programs. (Alternatively, CPLEX can also be used.)
Note
MIQP problems require a commercial solver such as GUROBI or CPLEX. Free solvers like GLPK_MI support mixed-integer linear programs but not mixed-integer quadratic programs.
## Construct and solve a CVXR problem
## (message: false suppresses a deprecation warning from the gurobi R
## package which calls as(x, "dgCMatrix") on a dtCMatrix internally;
## see gurobi::to_triplets — needs fix in the gurobi package)
x <- Variable(n, integer = TRUE)
objective <- Minimize(sum_squares(A %*% x - b))
prob <- Problem(objective)
result <- psolve(prob, solver = "GUROBI")cat(sprintf("Status: %s\n", status(prob)))
cat(sprintf("The optimal value is %f\n", result))
cat("A solution x is\n")
print(value(x))Status: optimal
The optimal value is 25.609230
A solution x is
[,1]
[1,] 0
[2,] -3
[3,] -1
[4,] 1
[5,] 2
[6,] 0
[7,] 0
[8,] -1
[9,] 2
[10,] 0
[11,] -1
[12,] 0
[13,] 0
[14,] -1
[15,] -1
[16,] 0
[17,] 1
[18,] 1
[19,] 1
[20,] 0
[21,] -1
[22,] 0
[23,] 1
[24,] 0
[25,] 0Session Info
R version 4.5.3 (2026-03-11)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3.1
Matrix products: default
BLAS: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib; LAPACK version 3.12.1
locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8
time zone: America/Los_Angeles
tzcode source: internal
attached base packages:
[1] stats graphics grDevices utils datasets methods base
other attached packages:
[1] CVXR_1.8.1
loaded via a namespace (and not attached):
[1] slam_0.1-55 cli_3.6.5 knitr_1.51 ECOSolveR_0.6.1
[5] rlang_1.1.7 xfun_0.56 clarabel_0.11.2 otel_0.2.0
[9] gurobi_13.0-1 Rglpk_0.6-5.1 highs_1.12.0-3 cccp_0.3-3
[13] scs_3.2.7 S7_0.2.1 jsonlite_2.0.0 backports_1.5.0
[17] htmltools_0.5.9 Rmosek_11.1.1 gmp_0.7-5.1 piqp_0.6.2
[21] rmarkdown_2.30 grid_4.5.3 evaluate_1.0.5 fastmap_1.2.0
[25] yaml_2.3.12 compiler_4.5.3 codetools_0.2-20 htmlwidgets_1.6.4
[29] Rcpp_1.1.1 osqp_1.0.0 lattice_0.22-9 digest_0.6.39
[33] checkmate_2.3.4 Matrix_1.7-4 tools_4.5.3