计算科学 - 是否可以将非线性排名类型约束表示为等效的线性约束？ - 吾爱随笔录

是否可以将非线性排名类型约束表示为等效的线性约束？

计算科学优化线性规划凸优化

2021-12-10 15:30:18

我已经制定了一个带有二进制指示变量的线性程序，如果文档的等级，则它等于。 $z_i(a)$ $1$ $i^{th}$ $a$ $0$

线性规划中的其他变量定义如下： $z^1_{ij}(a), z^2_{ij}(a)$

\begin{array}{rcl} z_{i j}^{1} (a) \equiv z_{i} (a) \sum_{b < a} z_{j} (b), \\ z_{i j}^{2} (a) \equiv z_{i} (a) \sum_{b \geq a} z_{j} (b) . \end{array}

$\begin{eqnarray} z^1_{ij}(a) \equiv z_i(a) \sum_{b<a} z_j(b), \\ z^2_{ij}(a) \equiv z_i(a) \sum_{b\geq a} z_j(b). \end{eqnarray}$

我正在尝试将上述非线性约束转换为以下一组等效线性约束：

z_{i j}^{1} (a) + z_{i j}^{2} (a) = z_{i} (a), \forall i, j, a

$z^1_{ij}(a) + z^2_{ij}(a) = z_i(a), \forall i, j, a$

我面临的问题是，上述一组线性约束显然不等同于的定义。知道是否可以将非线性排名类型约束表示为等效的线性约束？ $z^1_{ij}(a), z^2_{ij}(a)$

2个回答

有几种方法可以将模型转换为线性约束。例如

\begin{array}{rcl} z_{i j}^{1} (a) + z_{i j}^{2} (a) & = & z_{i} (a) \forall i, j, a \\ z_{i j}^{1} (a) & \leq & 1 - \sum_{b \geq a} z_{j} (b) \forall i, j, a \\ z_{i j}^{2} (a) & \leq & 1 - \sum_{b < a} z_{j} (b) \forall i, j, a \end{array}

$\begin{eqnarray} z^1_{ij}(a) + z^2_{ij}(a) &=& z_i(a) \ \ \forall i,j,a \\ z^1_{ij}(a) &\le& 1- \sum_{b \ge a} z_j(b) \ \ \forall i,j,a \\ z^2_{ij}(a) & \le& 1- \sum_{b < a} z_j(b) \ \ \forall i,j,a \end{eqnarray}$

一般来说，只要你有一个混合整数程序，其中唯一的非线性是二进制变量的多项式，就可以使用 Fred Glover 的工作和随后的相关工作重新制定程序，使其成为一个混合整数线性程序.

看：

F.格洛弗。进一步将零一多项式规划问题简化为零一线性规划问题。运筹学，第 21 卷，第 156-161 页，1971 年。
F. 格洛弗，E. 伍尔西。将 0-1 多项式规划问题转换为 0-1 线性规划。运筹学，第 22 卷，第 180-182 页，1974 年。
F.格洛弗。改进了非线性整数问题的线性整数规划公式。管理科学，第 22 卷，第 455-460 页，1975 年。
FE托雷斯。混合整数乘积的线性化。数学编程，第 49 卷，第 427-428 页，1991 年。
O. Kettani, M. Oral。用于有效优化的非线性整数问题的等效公式。管理科学，第 36 卷，第 115-119 页，1990 年。

其它你可能感兴趣的问题

上一篇切比雪夫系数的多项式拟合下一篇C 库 - 迭代稀疏复杂线性方程求解器？