Mixed-integer quadratic program =============================== A mixed-integer quadratic program (MIQP) is an optimization problem of the form .. math:: \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 :math:`x \in \mathbf{Z}^n` is the optimization variable (:math:`\mathbf Z^n` is the set of :math:`n`-dimensional vectors with integer-valued components), :math:`Q \in \mathbf{S}_+^n` (the set of :math:`n \times n` symmetric positive semidefinite matrices), :math:`q \in \mathbf{R}^n`, and :math:`r \in \mathbf{R}` are problem data, and :math:`\mathcal C` is some convex set. An example of an MIQP is mixed-integer least squares, which has the form .. math:: \begin{array}{ll} \mbox{minimize} & \|Ax-b\|_2^2 \\ \mbox{subject to} & x \in \mathbf{Z}^n, \end{array} where :math:`x \in \mathbf{Z}^n` is the optimization variable, and :math:`A \in \mathbf{R}^{m \times n}` and :math:`b \in \mathbf{R}^{m}` are the problem data. A solution :math:`x^{\star}` of this problem will be a vector in :math:`\mathbf Z^n` that minimizes :math:`\|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``. .. code:: python import cvxpy as cp import numpy as np .. code:: python # Generate a random problem np.random.seed(0) m, n= 40, 25 A = np.random.rand(m, n) b = np.random.randn(m) .. code:: python # 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() .. parsed-literal:: 13.66000322824753 .. code:: python print("Status: ", prob.status) print("The optimal value is", prob.value) print("A solution x is") print(x.value) .. parsed-literal:: 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.]