5.6.1. Modeling for Mixed Integer Quadratically Constrained Programming

A Mixed Integer Quadratically constrained program (referred to as MIQCP for simplicity) can be represented as follows:

\[\begin{split}\begin{matrix} \min & & x^T Q_0 x &+& c^Tx &-& c^f \\ \mbox{s.t.} & & x^T Q_i x &+& a_i^\top x & \leq & u_i^r, & \quad i = 1, 2, \cdots, m \\ & & l^c &\leq& x &\leq& u^c, \\ & & x_k &\in &\mathbb{Z}, &k \in I \subseteq \{1, \cdots, m\} \end{matrix}\end{split}\]

where

• \(x \in \mathbb{R}^{n}\) is the decision variable,

• \(l^c \in \mathbb{R}^{n}\) and \(u^c \in \mathbb{R}^{n}\) are the lower and upper bounds of \(x\),

• \(c^f \in \mathbb{R}\) is the constant term in the objective function,

• \(c \in \mathbb{R}^{n}\) is the linear coefficient in the objective function,

• \(Q_0 \in \mathbb{R}^{n\times n}\) is the quadratic coefficient matrix in the objective function,

• \(\{a_i \in \mathbb{R}^{n}\mid i=1,2,\cdots,m\}\) are the linear coefficient vectors of the constraints,

• \(\{Q_i \in \mathbb{R}^{n\times n}\mid i=1,2,\cdots,m\}\) are the quadratic coefficient matrices of the constraints,

• \(l^r \in \mathbb{R}^{m}\) and \(u^r \in \mathbb{R}^{m}\) are the lower and upper bounds of the constraints,

• \(x_k \in I\) are integer variables.

Note

Currently MindOpt supports solving convex Mixed Integer Quadratically Constrained Programs. Specifically:

• The objective quadratic matrix \(Q_0\) must be positive semi-definite.

• Each quadratic constraint must define a convex feasible region. MindOpt automatically recognizes convexity in the following cases:

  1. For constraints of the form \(x^\top Q_i x + a_i^\top x \leq u_i^r\), the matrix \(Q_i\) must be positive semi-definite.

  2. For constraints of the form \(x^\top Q_i x + a_i^\top x \geq l_i^r\), the matrix \(Q_i\) must be negative semi-definite.

  3. For constraints of the form \(x^\top Q_i x + a_i^\top x \leq y^2\), the matrix \(Q_i\) must be positive semi-definite, and y is nongative variable (a second order cone constraints, if \(Q_i = I\) indentity matrix)

  4. For constraints of the form \(x^\top Q_i x + a_i^\top x \leq yz\), the matrix \(Q_i\) must be positive semi-definite, and y and z are nongative variables (a roated Second Order Cone constraints, if \(Q_i = I\) indentity matrix)

We follow the steps below to use MindOpt :

1. Create an optimization model;

2. Input the optimization problem and set algorithm parameters;

3. Solve the optimization problem and retrieve the optimal solutions.

Note

MindOpt only stores the non-zero elements in the constraint matrices A and \(Q\). Therefore, we only need to input the positions and the values of the non-zero elements during the modeling process.

5.6.1.1. Example of Mixed Integer Quadratically Constrained Programming

In the following, we consider two example of Mixed Integer Quadratically Constrained Programming problem:

5.6.1.1.1. MIQCP Example I

\[\begin{split}\begin{matrix} \min & & 1 x_0 & + & 1 x_1 & + & 1 x_2 & + & 1 x_3 \\ & + & \frac{1}{2}x_0^2 & + & \frac{1}{2}x_1^2 & + & \frac{1}{2} x_2^2 & + & \frac{1}{2} x_3^2 & + & \frac{1}{2} x_0 x_1 \\ \mbox{s.t.} & & 1 x_0 & + & 1 x_1 & + & 2 x_2 & + & 3 x_3 \\ & - & \frac{1}{2}x_0^2 & - & \frac{1}{2}x_1^2 & - & \frac{1}{2} x_2^2 & - & \frac{1}{2} x_3^2 & - & \frac{1}{2} x_0 x_1 & \geq & 1 \\ & & 1 x_0 & & & - & 1 x_2 & + & 6 x_3 & + & \frac{1}{2} x_1^2 & \leq & 1 \end{matrix}\end{split}\]

\[\begin{split}\begin{matrix} 0 & \leq & x_0 & \leq & 10 \\ 0 & \leq & x_1 & \leq & \infty \\ 0 & \leq & x_2 & \leq & \infty \\ 0 & \leq & x_3 & \leq & \infty \\ & & x_0 \in \mathbb{Z} & & \end{matrix}\end{split}\]

5.6.1.1.2. MIQCP Example II

\[\begin{split}\begin{matrix} \min & 1 x_0 & + & 2 x_1 & + & 1 x_2 & + & 1 x_3 & + & 0.5 x_4 & \\ \mbox{s.t.} & 1 x_0 & + & 1 x_1 & + & 2 x_2 & + & 3 x_3 & & & \geq & 1 \\ & 1 x_0 & & & - & 1 x_2 & + & 6 x_3 & & & = & 1 \\ & & & 1 x_1^2 & + & 1 x_2^2 & & & - & 1 x_4^2 & \leq & 0 \\ \end{matrix}\end{split}\]

\[\begin{split}\begin{matrix} 0 & \leq & x_0 & \leq & 10 \\ 0 & \leq & x_1 & \leq & \infty \\ 0 & \leq & x_2 & \leq & \infty \\ 0 & \leq & x_3 & \leq & \infty \\ 0 & \leq & x_4 & \leq & \infty \\ & & x_0、x_1、x_2 \in \mathbb{Z} \end{matrix}\end{split}\]

We will provide example codes illustrating how MindOpt models and solves the above MIQCP problem in different programming languages.