组合优化：赋值（匹配）与"consecutive"赋值

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

如果有对 j 的赋值，则令 y(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

此输出的完整模型是：

组合优化：赋值（匹配）与"consecutive"赋值

Combinatorial optimization: assignment (matching) with "consecutive" assignments

modeling

constraints

variable-assignment

matching

cplex