Or-Tools CP-SAT: как определить целевую функцию, чтобы минимизировать количество уникальных забронированных номеров?
Я начинаю изучать ortools.sat.python/cp_model и не понимаю, как использовать model.minimize()/maximize().
Давайте рассмотрим пример простой задачи бронирования встреч по временным интервалам и комнатам:
model = cp_model.CpModel()
bookings = {}
for m in meetings:
for t in timeslots:
for r in rooms:
bookings[(m, t, r)] = model.new_bool_var(f"{m}_{t}_{r}")
# 1. each meeting shall be held once
for m in meetings:
model.add_exactly_one(bookings[(m, t, r)] for r in rooms for t in timeslots)
# 2. no overbooking: no two meetings can be booked for the same timeslot-room pair
for t in timeslots:
for r in rooms:
model.add_at_most_one(bookings[(m, t, r)] for m in meetings)
Теперь, что мне хотелось бы улучшить, так это минимизировать общее количество различных забронированных номеров. Другими словами, если можно создать весь график бронирования, например, с помощью Всего 3 комнаты (а не все 5 или 6 имеющихся), то именно такому решению следует отдать предпочтение.
Как мне это сделать?
Если бы я хотел минимизировать общее количество бронирований номера №1, я бы просто написал:
model.minimize(sum(bookings[(m, t, room_1)] for m in meetings for t in timeslots))
Чтобы подсчитать общее количество различных забронированных номеров ПОСЛЕ нахождения решения, я бы написал:
total_rooms_used = 0
for r in rooms:
room_r_bookings = sum(solver.value(bookings[(m, t, r)]) for t in timeslots for m in meetings)
if room_r_bookings > 0:
total_rooms_used += 1
print(f"Total rooms used: {total_rooms_used}")
Однако моя проблема в том, что я хочу минимизировать total_rooms_used и не знаю, как это поставить model.minimize(...)
Спасибо за ответ, однако я считаю, что включение всего кода (а также входных данных) только сделает его менее понятным. У меня не случай «что-то не работает», а скорее «во-первых, я не знаю, как это сделать». Однако я добавил дополнительные разъяснения к своему первоначальному вопросу.
Ответы 1
all_rooms_used = []
for r in rooms:
room_used = model.new_bool_var(f"room_used({r})")
all_rooms_used.append(room_used)
all_bookings = []
for m in meetings:
for t in timeslots:
model.add_implication(bookings[(m, t, r)], room_used)
all_bookings.append(bookings[(m, t, r)])
model.add_bool_or(all_bookings).only_enforce_if (room_used)
# symmetry breaking
for i in range(len(all_rooms_used) - 1):
model.add_implication(~all_rooms_used[i], ~all_rooms_used[i + 1])
model.minimize(sum(all_rooms_used))
Спасибо! Итак, для каждой комнаты вы создаете дополнительную переменную room_used, чтобы отслеживать, была ли она забронирована хотя бы один раз. И тогда вы синхронизируете его с отдельным all_bookings, имея два значения: 1. любое бронирование помещения r для любого собрания/временного интервала подразумевает, что помещение r используется; 2. если номер r используется, это означает, что его должно быть забронировано как минимум 1 раз. Наконец, минимизированная целевая функция представляет собой просто сумму списка room_used переменных. Великолепно! ПС. Не могли бы вы объяснить, что вы имели в виду под «можно нарушить симметрию»?
О нарушении симметрии: я так понимаю, вы это делаете для уменьшения пространства решений. Поскольку все комнаты идентичны, проверка одной и той же конфигурации временных интервалов и собраний для разных комбинаций комнат одного и того же количества (например, комнат A+B, комнат C+D, комнат A + D...) является избыточной; две комнаты - это две комнаты и все. Следовательно, учитывая пять комнат ABCDE, ваши выводы допускают только следующие комбинации использования комнат: A, AB, ABC, ABCD и ABCDE.
Пожалуйста, отредактируйте вопрос, чтобы в нем был воспроизводимый пример. Например, я не заметил оператора
import cp_modelв коде ОП. Идея состоит в том, что сотрудники должны иметь возможность запускать то, что запускаете вы, и видеть то, что видите вы. // Пожалуйста, укажите URL-адрес документации, описывающей «функцию потерь» (или функцию стоимости или целевую функцию), и опишите, что в настоящее время мешает вам использовать ее совет для добавления функции потерь в ваш пример кода. Это поможет нам помочь вам.