纸浆人员配备优化问题：轮班组合约束

Question

我正在尝试解决人员配备优化问题，这就是我的模型。

第一个约束：每次班次都需要安排最少的员工数量。

对于示例：

班次	要求
1	1 1
2	1
3	2
4	2
5	1

秒限制：员工可以工作0班次，1个偏移或2个偏移，并且不可能发生任何变化。

让我解释一下，如果员工的工作2个班次，他们需要恰好在每个班次之间进行1个班次。

这是可能组合的列表：

换档	Mathew
1	3
2	4
3	5
1
2
3
4
5

结果：

假设这些是我的员工：

1. Robin
2. 预期的
3. George
4. Elisa

这是一个有效的解决方案看起来像

Shift	Employee
1	Robin
2	乔治
3	罗宾，马修
4	乔治，伊丽莎
5	马修

·罗宾1、3

乔治2、4

马修3，5

elisa 4

我对第一个约束没有任何问题。这更多是我在纸浆中努力实施的第二个约束。如果您能给我指针，我会很感激。

谢谢！

编辑：这是我现在拥有的代码，试图按照@AirsQuid的方式建议

# constraint 1: must schedule someone at shift 1, 2, 5
for shift, patterns in vars_by_shift.items():
    if shift == 1 or shift == 2 or shift == 5:
        prob += sum(vars_by_shift[shift]) >= 1
    elif shift == 4 or shift == 5:  # and 2 persons at shift 4 and 5
        prob += sum(vars_by_shift[shift]) >= 2

# constraint 2: agent can at most be scheduled 1 time among all patterns
for agent in agent_names:
    prob += sum(vars_by_agent[agent]) <= 1

vars_by_shift看起来像这样

{
    1: [1_3,1,robin, 1,1,robin, 1_3,1,mathew, 1,1,mathew, 1_3,1,george, 1,1,george, 1_3,1,elisa, 1,1,elisa], 
    2: [2_4,2,robin, 2,2,robin, 2_4,2,mathew, 2,2,mathew, 2_4,2,george, 2,2,george, 2_4,2,elisa, 2,2,elisa], 
    3: [3_5,3,robin, 3,3,robin, 3_5,3,mathew, 3,3,mathew, 3_5,3,george, 3,3,george, 3_5,3,elisa, 3,3,elisa], 
    4: [2_4,4,robin, 4,4,robin, 2_4,4,mathew, 4,4,mathew, 2_4,4,george, 4,4,george, 2_4,4,elisa, 4,4,elisa], 
    5: [3_5,5,robin, 5,5,robin, 3_5,5,mathew, 5,5,mathew, 3_5,5,george, 5,5,george, 3_5,5,elisa, 5,5,elisa]
}

，而vars_by_agent则像这样：

{
    'robin': [1_3,1,robin, 1,1,robin, 2_4,2,robin, 2,2,robin, 3_5,3,robin, 3,3,robin, 2_4,4,robin, 4,4,robin, 3_5,5,robin, 5,5,robin], 
    'mathew': [1_3,1,mathew, 1,1,mathew, 2_4,2,mathew, 2,2,mathew, 3_5,3,mathew, 3,3,mathew, 2_4,4,mathew, 4,4,mathew, 3_5,5,mathew, 5,5,mathew], 
    'george': [1_3,1,george, 1,1,george, 2_4,2,george, 2,2,george, 3_5,3,george, 3,3,george, 2_4,4,george, 4,4,george, 3_5,5,george, 5,5,george], 
    'elisa': [1_3,1,elisa, 1,1,elisa, 2_4,2,elisa, 2,2,elisa, 3_5,3,elisa, 3,3,elisa, 2_4,4,elisa, 4,4,elisa, 3_5,5,elisa, 5,5,elisa]
}

我在调用solve（）时得到一个不可行的解决方案（），我不确定为什么。

最终编辑：

非常感谢@AirsQuid

终于获得了有效的解决方案。

关键在于确保将其存储在不同词典中时我不会重复决策变量。

def shift_to_be_sent_to(pattern):
    shifts = []
    for shift in range(1, 6):
        if coverage_map[pattern, shift] == 1:
            shifts.append(shift)
    return shifts

最终代码可用在这里

Answer 1

离散优化的是对任务的仔细形式化，这使得可以利用形式化的各种假设。总是有一个权衡取舍，涉及平衡概括和专业化。

您的示例将允许以下专业化，如果我们稍后省略了事物，则可能是不可能的。尽管如此，让我们解决问题。

正如您已经对（广义）分配问题部分建模的那样，这意味着红衣主教（0、1或2个偏移），我们只需要在某些工人的2个偏移情况下对“禁止分配”进行建模。

这很简单：只需使用“ 启示”。

FOR EACH WORKER W

    FOR EACH SHIFT S in [1, N_SHIFTS)

        assignment(w, s) -> NOT assignment(w, s+1)

我们已经假设了一个基于二进制/逻辑的域，并且以下域：

  the logical implication a -> b

is equivalent to:

  NOT a OR b

这可以如下线性化：

(1-a) + b >= 1

因此，我们需要的只是：

FOR EACH WORKER W

    FOR EACH SHIFT S in [1, N_SHIFTS)

        (1 - assignment(w, s) ) + (1 - assignment(w, s+1)) >= 1

这可能看起来像很多约束，但是 MILP-Solver（纸浆求解器也;至少CBC，对GLPK的不太确定）具有明确的这些约束= clique-tables和co。求解器将在这里使用强大的推理！

编辑

再次阅读任务，我省略了“他们需要在每个任务之间恰好1个换开”。

好吧...我们可以从头开始或再次使用该方法：

FOR EACH WORKER W

    FOR EACH SHIFT S in [1, N_SHIFTS)

        assignment(w, s) -> assignment(w, s+2) 
        IFF sum(assignment(w, *)) == 2

这是上述工作（请注意非负右侧），但是当有0时，我们必须以某种方式停用这种含义或1个作业！

我们可以通过大-M类似的配方来实现这一点：

我们从以下方面适应右侧：

>= 1

basically meaning: ALWAYS

导致

>= sum() - 1

basically meaning: Only when sum() >= 2

：

FOR EACH WORKER W

    FOR EACH SHIFT S in [1, N_SHIFTS-1)

        (1 - assignment(w, s) ) + assignment(w, s+2) >= sum(w, *) - 1

这是：

*activated* if sum == 2
*deactivated* if sum < 2
breaks when we got 3 or more assignments -> infeasible

与上述相反，这是更具侵略性的，并且可能与未来的添加不太合作！ i_认为很明显，这会大量利用！

在更复杂的类似模型中，我是 automata 的忠实拥护者，总是会推荐这些！这种方式在基本上需要一些图形图形时，在调制时间时需要进行一些艰难的初始开发成本，并且能够同步（另一个是您的MILP模型）。

动机和背景（尽管专注于约束编程）在这里说明：

“灵活优化：护士计划
使用约束编程和自动机” ）。

一些与MILP相关的工作将提供：

Côté，Marie-Claude，Bernard Gendron和Louis-Martin Rousseau。 “通过整数编程对常规约束进行建模。”国际人工智能融合（AI）和运营研究（OR）技术的国际会议。施普林格，柏林，海德堡，2007年。

。 。

我可能会补充说， or-tools cp-sat是一个了不起的混合材料（CP） /SAT/MILP/MORE），它支持自动机构成盒子的。

Answer 2

我真的很喜欢提出的其他解决方案，这对于此类问题的更大概括非常有用。对于提出的问题的复杂性，我认为您可以使用更简单的方法来限制，该方法使用枚举以简单的方式使用可能的变化。

在您的问题描述中，每个员工只能分配8种工作模式中的1个（或根本没有分配）。这引起了一个2个索引的二进制变量：

assign[employee, pattern]

已知“模式”与每个偏移中的需求的关系，因此您将拥有一个模型 parameter ，该 配对这2件事：

fulfills[pattern, shift] = {('p1', 's1'): 1, ... }

有一点肘润滑脂和一些求和约束，您有一个具有该变量，参数，3套（员工，模式，移位）和3或4个约束的模型，

在描述的情况下，这效果很好，因为可以很容易地列举可接受的模式模式的关系：结果是1比1的配对。

编辑：有关您已发布的代码的增强...

您在正确的轨道上... Kinda ...大声笑。我认为您的方法可以成功，我的想法有些不同，这不是三重索引，但是您的工作可以工作。

您有2个问题：您对班次的限制有错字。您的换档为“ 5”，而不是“ 3”，以实现2个要求。另外，如果您查看vars_by_shift您会注意到，对于Shift 3，您没有记入1-3组合！您可能需要重新重组该部分。这是关于如何更轻松地获得与模式相关联的变化的想法。 （意识到有这样做的方法）：

示例代码：

cov_file = 'coverages.csv'

coverages = dict()
with open(cov_file, 'r') as src:
    for line in src:
        data = line.strip().split(',')
        pattern = data[0]
        shifts = [int(t) for t in data[1:]]
        coverages[pattern] = shifts

shifts = [1, 2, 3, 4]
patterns = coverages.keys()

coverage_map = dict()
for (p, s) in [(p, s) for p in patterns for s in shifts]:
    coverage_map[p, s] = 1 if s in coverages[p] else 0

print(coverage_map)

coverages.csv

A,1
B,1,3
C,2,4
D,2,3,4

产量：

{('A', 1): 1, ('A', 2): 0, ('A', 3): 0, ('A', 4): 0, ('B', 1): 1, ('B', 2): 0, ('B', 3): 1, ('B', 4): 0, ('C', 1): 0, ('C', 2): 1, ('C', 3): 0, ('C', 4): 1, ('D', 1): 0, ('D', 2): 1, ('D', 3): 1, ('D', 4): 1}