linear-programming - 线性规划中的系数减少会导致结果不一致

Question

我对线性规划问题的约束系数减少后得到的结果有点困惑。

问题是:

maximize z = x1 + x2 + x3 + x4 + x5 + x6
subject to: 6*x1 + 3*x2 - 5*x3 + 2*x4 + 7*x5 - 4*x6 <= 15
where:
      1<=x1<=2 continuos
      1<=x2<=2 continuos
      1<=x3<=2 continuos
      1<=x4<=2 continuos
      1<=x5<=2 continuos
      1<=x6<=2 continuos

系数减少后，约束将是:

subject to: 3*x1 + 3*x2 - 3*x3 + 2*x4 + 3*x5 - 3*x6 <= 8

如《应用整数编程》一书(Der-San Chen - Robert G.Batson - Yu Dang)第 96 页所述(第 97 页有一点错误。x1 系数为 3)不是 1)。

之后，我尝试将问题提交给 ampl，无论是否减少系数。但我得到了两个不同的结果:

[without coefficients reduction]
CPLEX 12.6.1.0: optimal integer solution; objective 11.57142857
display x;
x1  2
x2  2
x3  2
x4  2
x5  1.57
x6  2

[with coefficients reduction]
CPLEX 12.6.1.0: optimal integer solution; objective 11.33333333
display x;
x1  2
x2  2
x3  2
x4  2
x5  1.33
x6  2

为什么？即使 x5 的结果略有不同，该解决方案是否仍可以被认为是正确的？ 我使用了三种不同的求解器(minos、gurobi、cplex)，但它们在问题上输出相同的结果。

Answer 1

如果您指的是4.4.3中的技术，那么很清楚这里的问题是什么。

Suppose we are given a constraint of the form
    a1*y1+ a2*y2 + ... + ai*yi < b
    where yi = 0 or 1

您不允许使用此技术，因为您的系数是连续的(在 [1,2] 中)，而不是此处所需的二进制!