组合优化：“连续”赋值的赋值(匹配)

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当i被赋值给j。

有谁知道如何对这个限制进行建模？

Answer 1

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

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

(这将替换原始的赋值约束sum(i,x(i,j)) ≤ 1)

现在，限制模式0,1在y(j)中的次数，如下所示：

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

此输出的完整模型为：

​

​