组合优化：分配（匹配）“连续”分配

Question

我正在尝试在IBM ILOG CPLEX中建模优化问题。基本上它是经典的分配问题。我必须设置A = {a_1，...，a_n}和B = {b_1，... b_m}和n <m。 A的每个元素必须分配给B的一个元素。对于B的每个元素，最多可以分配A的一个元素。从n <m开始，B的一些元素保持空闲（没有赋予它们任何东西）。

这种建模非常简单。但是，我有另一个约束，我找不到一种模型的方法。约束条件是：必须连接B中所有具有赋值的元素。分配必须是连续的/顺序的/但是你要调用它。

Example: A = {a_1,a_2,a_3}, B = {b_1,b_2,b_3_b_4,b_5}

如果A中的某个元素被分配给b_1，则b_2和b_3也会分配。

如果A中的某个元素被分配给b_3，则b_4和b_5具有赋值或者b_2和b_4具有赋值或者b_1和b_2具有赋值。

换句话说：如果x表示将某些内容分配给B中的元素，则允许这些配置：（xxx - - ），（ - xxx - ），（ - - xxx）。

我使用决策变量x_ij，其中i代表A，j代表B. x_ij = 1 iff i分配给j。

任何人都知道如何模拟这种限制？

Answer 1

如果有对y(j)的赋值，则j为1，否则为0：

y(j) = sum(i,x(i,j)) 

（这取代了原来的赋值约束sum(i,x(i,j)) ≤ 1）

现在，限制我们在y(j)中具有模式[0,1]的次数如下：

z(j) ≥ y(j)-y(j-1)
sum(j, z(j)) ≤ 1

这将允许y中只有一个从0到1的转换。所有变量y和z都应该是二进制的（或者在0和1之间连续）。

输出小数据集。首先是纯粹的分配问题：

----     30 PARAMETER c  cost coefficients

            j1          j2          j3          j4          j5          j6          j7          j8          j9         j10

i1       0.661       0.756       0.627       0.284       0.086       0.103       0.641       0.545       0.032       0.792
i2       0.073       0.176       0.526       0.750       0.178       0.034       0.585       0.621       0.389       0.359
i3       0.243       0.246       0.131       0.933       0.380       0.783       0.300       0.125       0.749       0.069
i4       0.202       0.005       0.270       0.500       0.151       0.174       0.331       0.317       0.322       0.964
i5       0.994       0.370       0.373       0.772       0.397       0.913       0.120       0.735       0.055       0.576


----     30 VARIABLE x.L  assignment variables

            j2          j5          j6          j9         j10

i1                       1
i2                                   1
i3                                                           1
i4           1
i5                                               1

（零值未显示）。

添加这些y和z变量和约束后，我们看到：

----     54 VARIABLE x.L  assignment variables

            j5          j6          j7          j8          j9

i1                                                           1
i2                       1
i3                                               1
i4           1
i5                                   1


----     54 VARIABLE y.L  destination is used

j5 1,    j6 1,    j7 1,    j8 1,    j9 1


----     54 VARIABLE z.L  0-1 transition

j5 1

此输出的完整模型是：