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 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.

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

We consider the following Quadratically Constrained 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 \\ & - & \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}\]

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