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

$\begin{split}\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}\end{split}$

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{split}\begin{array}{ll} \mbox{minimize} & \|Ax-b\|_2^2 \\ \mbox{subject to} & x \in \mathbf{Z}^n, \end{array}\end{split}$

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 CVXPY. You need to install a mixed-integer nonlinear solver to run this example. CVXPY’s preferred open-source mixed-integer nonlinear solver is SCIP. It can be installed with pip install pyscipopt or conda install -c conda-forge pyscipopt.

import cvxpy as cp
import numpy as np

# Generate a random problem
np.random.seed(0)
m, n= 40, 25

A = np.random.rand(m, n)
b = np.random.randn(m)

# Construct a CVXPY problem
x = cp.Variable(n, integer=True)
objective = cp.Minimize(cp.sum_squares(A @ x - b))
prob = cp.Problem(objective)
prob.solve()

13.66000322824753

print("Status: ", prob.status)
print("The optimal value is", prob.value)
print("A solution x is")
print(x.value)

Status:  optimal
The optimal value is 13.66000322824753
A solution x is
[-1.  1.  1. -1.  0.  0. -1. -2.  0.  0.  0.  1.  1.  0.  1.  0. -1. -1.
-1.  0.  2. -1.  2.  0. -1.]