线性规划中的连续天数约束

Question

对于轮班优化问题，我在 PuLP 中定义了一个二进制变量，如下所示：

pulp.LpVariable.dicts('VAR', (range(D), range(N), range(T)), 0, 1, 'Binary')

哪里

D = 我们创建的每个计划中的 # 天（=28 或 4 周）
N = 工人数
T = 轮班工作类型 (=6)

对于第 5 种和第 6 种工作班次（索引为 4 和 5），我需要添加一个约束条件，即任何工作这些班次的工人必须连续工作 7 天......而不是任何 7 天但从星期一开始的 7 天（又名整周）。我已经尝试按如下方式定义约束，但是当我添加此约束并尝试解决问题时，我得到了一个不可行的解决方案（以前没有它就可以工作）

我知道这个限制条件（连同之前的其他限制条件）在理论上应该是可行的，因为我们手动使用相同的限制条件安排工作班次。我对约束进行编码的方式有什么问题吗？

## looping over each worker
for j in range(N):
    ## looping for every Monday in the 28 days 
    for i in range(0,D,7):
        c = None
        ## accessing only the 5th and 6th work shift type 
        for k in range(4,T):
            c+=var[i][j][k]+var[i+1][j][k]+var[i+2][j][k]+var[i+3][j][k]+var[i+4][j][k]+var[i+5][j][k]+var[i+6][j][k]
        problem+= c==7

Answer 1

如果我没理解错的话，那么你的约束要求每个工人每周必须工作第 4 班和第 5 班。这是因为 c == 7，即 c 中的 7 个二进制文件必须设置为 1。这不允许任何工人在 0 到 3 班次工作，对吗？

您需要更改约束条件，以便仅当工作人员在该范围内进行任何班次时才强制执行 c == 7。一个非常简单的方法是

v = list()
for k in range(4,T):
  v.extend([var[i][j][k], var[i+1][j][k], var[i+2][j][k], var[i+3][j][k], var[i+4][j][k], var[i+5][j][k], var[i+6][j][k]])
c = sum(v)
problem += c <= 7        # we can pick at most 7 variables from v
for x in v:
  problem += 7 * x <= c  # if any variable in v is picked, then we must pick 7 of them

这绝不是建模的最佳方式（指示变量会好得多），但它应该让您知道该怎么做。

Answer 2

只是为了提供一种替代方法，假设（正如我所读的那样）对于任何给定的一周，工人可以在 7 天内以 [0:3] 轮班的某种组合工作，或者其中一个班次 [每天 4:5]：我们可以通过定义一个新的二进制变量 Y[w][n][t] 来做到这一点，如果在第 w 周，工人 n 进行了限制性轮班 t，则该变量为 1，否则为 0。然后我们可以通过添加约束将这个变量与我们现有的变量 X 相关联，以便 X 可以取的值取决于 Y 的值。

# Define the sets of shifts
non_restricted_shifts = [0,1,2,3]
restricted_shifts = [4,5]

# Define a binary variable Y, 1 if for week w worker n works restricted shift t
Y = LpVariable.dicts('Y', (range(round(D/7)), range(N), restricted_shifts), cat=LpBinary)

# If sum(Y[week][n][:]) = 1, the total number of non-restricted shifts for that week and n must be 0
for week in range(round(D/7)):
    for n in range(N):
        prob += lpSum(X[d][n][t] for d in range(week*7, week*7 + 7) for t in non_restricted_shifts) <= 1000*(1-lpSum(Y[week][n][t] for t in restricted_shifts))

# If worker n has 7 restricted shift t in week w, then Y[week][n][t] == 1, otherwise it is 0
for week in range(round(D/7)):
    for n in range(N):
        for t in restricted_shifts:
            prob += lpSum(X[d][n][t] for d in range(week*7, week*7+7)) <= 7*(Y[week][n][t]) 
            prob += lpSum(X[d][n][t] for d in range(week*7, week*7+7)) >= Y[week][n][t]*7

一些示例输出（D=14，N=2，T=6）：

        / M T W T F S S / M T W T F S S / M T W T F S S / M T W T F S S
WORKER 0
Shifts: / 2 3 1 3 3 2 2 / 1 0 2 3 2 2 0 / 3 1 2 2 3 1 1 / 2 3 0 3 3 0 3
WORKER 1
Shifts: / 3 1 2 3 1 1 2 / 3 3 2 3 3 3 3 / 4 4 4 4 4 4 4 / 1 3 2 2 3 2 1
WORKER 2
Shifts: / 1 2 3 1 3 1 1 / 3 3 2 2 3 2 3 / 3 2 3 0 3 1 0 / 4 4 4 4 4 4 4
WORKER 3
Shifts: / 2 2 3 2 1 2 3 / 5 5 5 5 5 5 5 / 3 1 3 1 0 3 1 / 2 2 2 2 3 0 3
WORKER 4
Shifts: / 5 5 5 5 5 5 5 / 3 3 1 0 2 3 3 / 0 3 3 3 3 0 2 / 3 3 3 2 3 2 3

线性规划中的连续天数约束

consecutive days constraint in linear programming

optimization

constraints

linear-programming

pulp