如何用单纯形法动态定义约束

Question

我试图为我的问题正确地编写一个线性编程模型。我想最小化w_i的和，并且我有以下约束：

(a_i+w_i ≤ w_j) XOR (a_j+w_j ≤ w_i)
a_i and a_j are integer constants
w_i and w_j are integer variables

一般来说，当我们写系统的标准形式时，我们有方程，其中写部分表示乘积的最大或最小量，这个量定义得很好，但在我的问题中，w_i和w_j都是未知的，它们应该由我的ILP计算，所以在编写标准表单时，以及在制定与标准表单对应的第一个表时，我无法定义预算外b！我该怎么做？！

回复：我使用单纯形法所有变量都是整数

Answer 1

(1(严格来说，单纯形法只适用于连续问题。

(2(INEQ1 OR INEQ2可以通过添加二进制变量来实现。我从来没有见过INEQ1 XOR INEQ2的模特。我怀疑在你的情况下，我们可以使用INEQ1 OR INEQ2。

(3( OR通常被建模为：

a(i)+w(i) ≤ w(j) + M*δ(i,j)  
a(j)+w(j) ≤ w(i) + M*(1-δ(i,j))
δ(i,j) ∈ {0,1}

这里M是一个big-M：一个足够大的常数。通常，由于对称性，我们可以将这些约束限制在i<j的情况下。