添加 'at least one day off' 约束

Question

我在下面简化了我正在尝试做的事情的例子。我有一个每周计划和一些不同的 'slots' 来填补，我正在最大化分配给每个槽的每个人的给定值。

我正在尝试添加一个约束条件，表示他们每人休息一天。我见过类似的问题，但我无法将它们翻译成这个问题，因此不胜感激。

我的想法是，我可以取每个人每天的最大值，即在他们当前分配的任何一天都为 1，然后对所有天数求和并尝试使其小于或等于到 2（共 3 天）。

from ortools.sat.python import cp_model

model = cp_model.CpModel()

assignments = {}

people = ['Max','Josh']

days = {
    'Monday':['7','8','9','10'],
    'Tuesday':['6','7','8','9','10'],
    'Wednesday':['7','8','9','10']
}

default_thing_we_like = 50

thing_we_like_per_employee_per_slot = {
    ('Max','Monday','7'): 100,
    ('Max','Tuesday','7'): 150,
    ('Max','Wednesday','7'): 200,
}

# make vars
for person in people:
    for day in days:
        for hour in days[day]:
            assignments[(person,day,hour)] = model.NewBoolVar(f'{person}-{day}-{hour}')

# fill each spot
for day in days:
    for hour in days[day]:
        model.Add(sum(assignments[(person,day,hour)] for person in people) == 1)

# everyone should get at least one of these days off
for person in people:
    for day in days:
        model.Add(sum(max(assignments.get((person,day,hour),0) for hour in days[day]) for day in days) <= 2)

solver = cp_model.CpSolver()

model.Maximize(sum(thing_we_like_per_employee_per_slot.get((person, day, hour),default_thing_we_like) * assignments[(person,day,hour)]
                                                    for hour in days[day]
                                                    for day in days
                                                    for person in people
                                                    ))


solution_printer = cp_model.ObjectiveSolutionPrinter()
status = solver.SolveWithSolutionCallback(model, solution_printer)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    ret_slots = []
    for person in people:
        print(f"{person} is working: ")
        for day in days:
            for hour in days[day]:
                if (solver.Value(assignments[(person,day,hour)])):
                    print(f"{day} at {hour} with",thing_we_like_per_employee_per_slot.get((person, day, hour),default_thing_we_like),"things we like.")
else:
    print("uh oh")

我得到的结果运行是这样的：

Solution 0, time = 0.00 s, objective = 900
Max is working: 
Monday at 7 with 100 things we like.
Monday at 9 with 50 things we like.
Tuesday at 6 with 50 things we like.
Tuesday at 7 with 150 things we like.
Tuesday at 8 with 50 things we like.
Tuesday at 9 with 50 things we like.
Tuesday at 10 with 50 things we like.
Wednesday at 7 with 200 things we like.
Wednesday at 8 with 50 things we like.
Wednesday at 9 with 50 things we like.
Wednesday at 10 with 50 things we like.
Josh is working: 
Monday at 8 with 50 things we like.
Monday at 10 with 50 things we like.

它将 Max 分配给所有 3 天。

Answer 1

您不能将 max, min, or, and 与 ortools 创建的变量一起使用。

要对这些类型的约束进行建模，只需创建中间变量会更容易。

works_day = {
    (person, day): model.NewBoolVar(f"{person}-{day}")
    for person in people
    for day in days
}

for person in people:
    for day in days:
        for hour in days[day]:
            assignments[(person, day, hour)] = model.NewBoolVar(
                f"{person}-{day}-{hour}"
            )
            model.AddImplication(
                assignments[(person, day, hour)], works_day[person, day]
            )

for person in people:
    model.Add(sum(works_day[person, day] for day in days) <= 2)

添加 'at least one day off' 约束

Adding 'at least one day off' constraint

python

or-tools