5.2.1. 混合整数线性规划建模

混合整数线性规划（Mixed Integer Linear Program，MILP）问题可以用以下数学形式表示：

\[\begin{split}\min \quad&-c^f + c^Tx \\ \mbox{s.t.} \quad&l^r \leq Ax \leq u^r, \\ & l^c \leq x \leq u^c, \\ & 部分 x \in \mathbb{Z}^{n}\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}\) 是目标函数中的系数，

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

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

  • \(部分 x \in \mathbb{Z}^{n}\) 是指变量为整数的约束。

使用 MindOpt 的步骤为：

  1. 创建优化模型；

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

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

Note

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

5.2.1.1. 混合整数线性规划问题示例

在下文中，我们将考虑下列混合整数线性规划问题：

\[\begin{split}\begin{matrix} \min & 1 x_0 & + & 1 x_1 & + & 1 x_2 & + & 1 x_3 \\ \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、x_1、x_2 为整数 \end{matrix}\end{split}\]

我们将展示如何使用 MindOpt 建模和求解这个优化问题。混合整数线性规划与线性规划的区别在于，添加变量时将其整数属性设为”是“。其建模依然可以通过以下两种形式来输入矩阵中的非零元：

  1. 按 行（约束） 排列；

  2. 按 列（变量） 排列。

具体可以参考 线性规划建模。

接下来，我们将针对不同语言分别给出示例。