максимальное количество BoolVar до or-tools невозможно использовать
Стандартная задача планирования медсестер, которая используется в качестве примера для OR-Tools (см., Например, https://developers.google.com/optimization/scheduling/employee_scheduling) пытается присвоить логические значения логическим переменным в следующей строке кода:
shifts[(n, d, s)] = model.NewBoolVar('shift_n%id%is%i' % (n, d, s))
Для этой игрушечной задачи OR-Tools работает нормально, но создается только 105 логических переменных (5 медсестер, 7 дней, 3 смены $\Rightarrow 3\times 5\times7=105$ логические значения, определяющие, работает ли данная медсестра в данную смену).
Я изучаю возможность использования OR-Tools для решения более реалистичной задачи планирования в реальном мире. Для реальной проблемы, с которой я сталкиваюсь, смены назначаются с шагом 15 минут, и задействовано больше рабочих и ролей. В итоге я получаю 11 064 логических значения, которые нужно назначить.
Это слишком много, чтобы ожидать, что OR-Tools будут работать реалистично? Я обнаружил, что он быстро создает (не очень хороший) график, но затем, даже если я позволю ему поработать в течение часа, он вообще не улучшится по сравнению с первоначальным графиком, который он разработал в первые несколько секунд.
Это типичное поведение OR-Tools? есть идеи?
Ответы
На этот вопрос нет хороших ответов. Это зависит от модели, от сложности проблемы. Моя интуиция такова, что OR-Tools обычно решает до оптимальности более крупные проблемы, но некоторые гораздо более мелкие проблемы невозможно доказать или даже найти возможное решение.
OR-Tools - хороший решатель CP (он выиграл все 4 золотые медали в последних двух испытаниях minizinc). Это также достойный решатель MIP (он закрыл 5 открытых экземпляров MIPLIB 2017 и улучшил границы еще для нескольких).
Я бы предложил или повторил приведенные выше предложения:
- сравните с коммерческим решателем MIP (Gurobi, Cplex, Xpress) и испытайте удачу.
- сравните с CPLEX CP-Optimizer. Я не ожидал, что это будет лучше после обсуждений, которые я провел с академическими исследователями, которые проводили сравнение, но это может быть проблемой, когда CPO работает превосходно.
- отправьте свою модель в список рассылки пользователей or-tools и попросите помощи или комментариев, в частности, по параметрам поиска.