Составление списка медсестер с помощью решателя ограничений ortools
Я прошел через учебник от google и, кажется, понимаю большую часть кода. Моя проблема в том, что они выбирают решения только на основе жестких ограничений. В большинстве статей также используются мягкие ограничения, и у каждого ограничения есть свой коэффициент. Сумма всех ограничений, каждое из которых умножается на их коэффициент, дает стоимость списка, поэтому цель состоит в том, чтобы минимизировать это значение. У меня вопрос, как я могу добавить это в код?
# Create the decision builder.
db = solver.Phase(shifts_flat, solver.CHOOSE_FIRST_UNBOUND,
solver.ASSIGN_MIN_VALUE)
# Create the solution collector.
solution = solver.Assignment()
solution.Add(shifts_flat)
collector = solver.AllSolutionCollector(solution)
solver.Solve(db, [collector])
Я не уверен, что делает конструктор решений (или его параметры), ни solver.Assignment(), ни solver.AllSolutionCollector(solution).
Единственное, что я нашел, это это, но я не уверен, как его использовать. (может, вместо переуступки вызвать в solver.Minimize(cost, ?)?)
model.Minimize(obj_var) все еще есть, но выглядит он довольно упрощенно (без факторов?). Вероятно, вам нужно вручную овеществлять все ваши ограничения (с потенциальным штрафом), а затем вызвать minimize на этих обобщенных условиях.
Вы можете получить дополнительную помощь в официальном Форум. Немного прочитав его + средство отслеживания проблем предоставит вам некоторую информацию (например: теперь мы все время используем CP на основе SAT; но не все примеры преобразованы; ищите суффикс _sat).
Пожалуйста, посмотрите github.com/google/or-tools/blob/master/ortools/sat/doc/index .md. Составляю список модельных конструкций.
Одно мне непонятно. Почему я не могу использовать решатель MIP? Думаю, это правильный подход. Я в основном хочу минимизировать затраты, установив некоторые целочисленные (логические) переменные. Если я правильно понимаю, решатель SAT находит решение, используя только жесткие ограничения. (или я ошибаюсь?)
Ты неправ. Решающая программа SAT поддерживает полу-реифицируемое ограничение: логическое => ограничение. Это в сочетании с добавлением этого логического значения к цели позволяет реализовать мягкие ограничения. Основное различие между решателем SAT и решателем MIP заключается в выразительной силе решателя. Решатели MIP поддерживают линейные неравенства. Наши решатели CP-SAT поддерживают планирование и сложные целочисленные ограничения: см. Методы добавления в части CpModel: github.com/google/or-tools/blob/…
Обратите внимание, что если модель естественным образом выражается как линейная задача для логической переменной, вполне вероятно, что решатели MIP превзойдут по производительности решатель CP-SAT.
Ответы 1
0
Если вы посмотрите на:
https://github.com/google/or-tools/blob/stable/examples/python/shift_scheduling_sat.py
Данные определяют запросы сотрудников:
https://github.com/google/or-tools/blob/stable/examples/python/shift_scheduling_sat.py#L219
Модель напрямую создает по одной переменной типа bool для каждого кортежа (сотрудник, день, смена).
Таким образом, добавить это к цели просто:
# Employee requests
for e, s, d, w in requests:
obj_bool_vars.append(work[e, s, d])
obj_bool_coeffs.append(w)
Это используется в коде минимизации:
# Objective
model.Minimize(
sum(obj_bool_vars[i] * obj_bool_coeffs[i]
for i in range(len(obj_bool_vars))) + sum(
obj_int_vars[i] * obj_int_coeffs[i]
for i in range(len(obj_int_vars))))
or-tools довольно большой, а документация довольно скудная. Из того, что я собрал (воспринимайте это с недоверием): 1: Существует как минимум 3 очень разных основных процедуры принятия решений: CP-Solver, CP-Solver на основе SAT и решатели LP / 01-MIP / MIP (с различные бэкенды; например, or-tools Bop vs. Cbc). 2: Ваша ссылка
this` является частью MIP-интерфейса, и вы не можете ее использовать. Нет автоматического преобразования, и MIP сложнее публиковать. 3: CP-Solver несколько устарел и заменен решателем на основе SAT (некоторые примеры изменены; но документация несколько устарела). Для CP на основе SAT пройдите через ...