5.5.1. Modeling for Mixed Integer Quadratic Programming

A linear-constrained mixed integer quadratic program (referred to as MIQP for simplicity) can be represented as follows:

\[\begin{split}\begin{matrix} \min & &-c^f &+& c^Tx &+& x^T Q x \\ \mbox{s.t.} & &l^r& \leq& Ax &\leq &u^r \\ & & 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 \in \mathbb{R}^{n\times n}\) is the quadratic coefficient matrix in the objective function,

• \(A \in \mathbb{R}^{m \times n}\) is the constraint matrix,

• \(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.

The steps to use MindOpt are as follows:

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. Currently MindOpt supports solving convex Mixed Integer quadratically constrained programming. Thus it requires the quadratic coefficient matrices in the objective \(Q_0\) and quadratic constraints \(\{Q_i \mid i=1,2,\cdots,m\}\) to be positive semi-definite. When users input quadratic constraints in the direction of \(\geq\), then it requires the quadratic matrices to be negative semi-definite.

5.5.1.1. Example of Mixed Integer Quadratic Programming

We consider the following Quadratic Programming problem:

\[\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 & \geq & 1 \\ & & 1 x_0 & & & - & 1 x_2 & + & 6 x_3 & = & 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}\]

The only difference between the above quadratic programming and linear programming is the input of the quadratic item matrix \(Q\). We will provide example codes illustrating how MindOpt models and solves the above QP problem in different programming languages.