optimization - 排名约束的混合整数线性规划

Question

我正在尝试为与特定变量的等级相关的约束编写混合整数线性规划，如下所示：

• 我有 X1、X2、X3、X4 作为决策变量。
• 有一个约束要求将 i 定义为 X1 的秩（例如，如果 X1 是 X1、X2、X3、X4 中的最大数，则 i=1；如果 X1 是第二大数，则 i=2，如果X1 是第三大数，则 i=3，否则 i=4)

如何将此约束写入混合整数线性规划？

Answer 1

没那么容易。这是一个尝试：

首先引入二进制变量y(i)为i=2,3,4

然后我们可以写：

 x(1) >= x(i) - (1-y(i))*M   i=2,3,4
 x(1) <= x(i) + y(i)*M       i=2,3,4
 rank = 4 - sum(i,y(i))
 y(i) ∈ {0,1}                i=2,3,4

这M是一个足够大的常数（一个不错的选择是数据的最大范围）。如果您的求解器支持指标约束，您可以稍微简化一下。

一个小例子说明了它的工作原理：

----     36 VARIABLE x.L  

i1 6.302,    i2 8.478,    i3 3.077,    i4 6.992


----     36 VARIABLE y.L  

i3 1.000


----     36 VARIABLE rank.L                =            3.000