Mixed-Integer Quadratic Program

Introduction

A mixed-integer quadratic program (MIQP) is an optimization problem of the form

$$\begin{array}{ll}\text{minimize}& x^{T}Qx+q^{T}x+r\\ \text{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}\text{minimize}& \parallel Ax-b{\parallel }_2^2\\ \text{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 $\parallel Ax-b{\parallel }_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.

## Generate a random problem
set.seed(0)
m <- 40
n <- 25

A <- matrix(runif(m * n), nrow = m, ncol = n)
b <- rnorm(m)

## 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,]    0

Session Info

R version 4.5.2 (2025-10-31)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3

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    Rcplex_0.3-8     
[17] backports_1.5.0   htmltools_0.5.9   Rmosek_11.1.1     gmp_0.7-5.1      
[21] piqp_0.6.2        rmarkdown_2.30    grid_4.5.2        evaluate_1.0.5   
[25] fastmap_1.2.0     yaml_2.3.12       compiler_4.5.2    codetools_0.2-20 
[29] htmlwidgets_1.6.4 Rcpp_1.1.1        osqp_1.0.0        lattice_0.22-9   
[33] digest_0.6.39     checkmate_2.3.4   Matrix_1.7-4      tools_4.5.2      

References