排序约束的混合整数线性规划
Mixed Integer Linear Programming for a Ranking Constraint
我正在尝试为与特定变量的等级相关的约束编写混合整数线性规划，如下所示：
- 我有 X1、X2、X3、X4 作为决策变量。
- 有一个约束要求将i定义为X1的排名（例如，如果X1是X1、X2、X3、X4中最大的数，则i=1；如果X1是第二大数，则i=2，如果 X1 是第三大数则 i=3，否则 i=4)
如何将此约束写入混合整数线性规划？
没那么容易。这是一个尝试：
首先引入二进制变量y(i) for 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
我正在尝试为与特定变量的等级相关的约束编写混合整数线性规划，如下所示：
- 我有 X1、X2、X3、X4 作为决策变量。
- 有一个约束要求将i定义为X1的排名（例如，如果X1是X1、X2、X3、X4中最大的数，则i=1；如果X1是第二大数，则i=2，如果 X1 是第三大数则 i=3，否则 i=4)
如何将此约束写入混合整数线性规划？
没那么容易。这是一个尝试：
首先引入二进制变量y(i) for 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