matlab - 当一个变量属于一个集合时如何解决整数线性规划

Question

我正在使用整数线性规划解决优化问题，其中一个约束假设变量的值属于一组值，如下所示

 min 5*x1 + 2*x2
 s.t.
 x1,x2>0
 x1 in {2,4,-5}

我如何在 matlab 中使用 CPLEX 或 lp_solve 来表示这个问题来解决它？F,A,b 数组的值是多少？

谢谢

Answer 1

您可以将整数变量采用有限不连续的一组可能整数值的问题重写为更多变量中的二进制程序。写吧：

2 * b1 + 4 * b2 -5 * b3 - x1 = 0
b1 + b2 + b3 = 1

约束为b1, b2, b3二进制。这可能被直接支持，或者表示为

b1, b2, b3 integer
0 <= b1, b2, b3 <= 1

如果您不允许使用等式约束，请记住一对不等式约束是等价的。

 Ax = b;

是相同的

 Ax <= b
-Ax <- -b

但是解集仍然没有内点，所以内点法是行不通的。您可以通过以下方式放松：

 Ax - e <= b
-Ax - e <= -b

e并使用您的目标函数最小化。