如何解决有约束的赋值问题？

Question

假设有 N 个人，有 M 个任务，并且有一个成本矩阵，它告诉何时将任务分配给一个人需要多少成本。

假设我们可以为一个人分配多个任务。

这意味着如果成本最低，我们可以将所有任务分配给一个人。我知道这个问题可以使用各种技术来解决。其中一些在下面。

• 位掩码
• 匈牙利算法
• 最小成本最大流量
• 蛮力（所有排列 M！）

问题：但是如果我们设置一个约束，比如只能将连续的任务分配给一个人，会怎么样。 

    T1   T2   T3
P1   2    2    2
P2   3    1    4

答案：6而不是5

解释：

我们可能认为 , P1->T1, P2->T2, P1->T3 = 2+1+2 =5 可以是答案但不是因为（T1和T3是连续的所以不能分配给P1）

P1->T1, P1->T2, P1-T3 = 2+2+2 = 6

如何解决这个问题？

Answer 1

您可以使用ILP解决此问题。

这是一个类似 OPL 的伪代码：

**input: 
two integers N, M        // N persons, M tasks
a cost matrix C[N][M] 

**decision variables: 
X[N][M][M]     // An array with values in {0, 1}
               // X[i][j][k] = 1 <=> the person i performs the tasks j to k 
                              

**constraints:
// one person can perform at most 1 sequence of consecutive tasks
for all i in {1, N}, sum(j in {1, ..., M}, k in {1, ..., M}) X[i][j][k] <= 1

// each task is performed exactly once
for all t in {1, M}, sum(i in {1, ..., N}, j in {1, ..., t}, k in {t, ..., M}) X[i][j][k] = 1

// impossible tasks sequences are discarded
for all i in {1, ..., N}, for all j in {1, ..., M}, sum(k in {1, ..., j-1}) X[i][j][k] = 0

**objective function:
minimize sum(i, j, k) X[i][j][k] * (sum(t in {j, ..., k}) C[t])

我认为 ILP 可能是这里的首选工具，因为更常见的是，不能使用它来解决调度和生产计划问题。
如果您没有编写 LP 程序的经验，请不要担心，这比看起来要容易得多，而且这个问题非常容易上手。

还有一个专门解决此类问题和解决方案的 stackexchange，即OR stack Exchange。