5.5.1. 混合整数二次规划建模

混合整数二次规划（Mixed Integer Quadratic Programming，MIQP）问题可以用以下数学形式表示：

\[\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} \end{matrix}\end{split}\]

其中

• \(x \in \mathbb{R}^{n}\) 是决策变量，

• \(l^c \in \mathbb{R}^{n}\) 和 \(u^c \in \mathbb{R}^{n}\) 分别为 \(x\) 的下界和上界，

• \(c^f \in \mathbb{R}\) 是目标函数中的常量，

• \(c \in \mathbb{R}^{n}\) 是目标函数中线性项的系数向量，

• \(Q \in \mathbb{R}^{n\times n}\) 是目标函数中二次项的系数矩阵，

• \(A \in \mathbb{R}^{m \times n}\) 是约束矩阵，

• \(l^r \in \mathbb{R}^{m}\) 和 \(u^r \in \mathbb{R}^{m}\) 分别为是约束的下界和上界，

• \(部分 x_k \in \mathbb{Z}\) 是指 \(x\) 变量中部分元素为整数的约束。

Note

目前 MindOpt 支持求解混合整数凸二次目标(约束)规划，因此要求目标函数中的二次项系数 \(Q_0\) 与约束中的二次项系数 \(\{Q_i \mid i=1,2,\cdots,m\}\) 均为 半正定矩阵 。当用户以 \(\geq\) 的形式输入二次约束时，则要求对应二次项系数为 半负定矩阵 。

使用 MindOpt 的步骤为：

1. 创建优化模型；

2. 输入优化问题并设置算法参数；

3. 求解优化问题并获取解。

Note

MindOpt 仅存储中的问题系数中的 非零元；因此，使用时只需要输入 非零元 在约束矩阵中的 行列位置 (row/column index) 以及对应的 非零数值 (nonzero value）。

5.5.1.1. MIQP题示例

在下文中，我们将考虑下列混合整数二次目标规划问题：

\[\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}\]

我们将分别给出不同编程语言下的示例，来展示如何使用 MindOpt 建模和求解这个优化问题。