Перейти к основному содержимому

Подсказки решателю

Подсказка — стартовое значение переменной, передаваемое решателю до начала поиска. Подсказки не являются ограничениями: решатель вправе их проигнорировать, если они противоречат ограничениям или ухудшают значение целевой функции.

Поэтому подсказки не меняют множество допустимых решений и не сужают пространство поиска. Они только направляют первые шаги в перспективную область.

Когда подсказки полезны​

Подсказки эффективны на больших смешанно-целочисленных задачах, для которых известно содержательно правдоподобное стартовое решение:

  • Перепланирование от текущего состояния. При оперативном перепланировании (production planning, scheduling) предыдущий план известен и обычно близок к новому оптимуму. Передача предыдущего плана как подсказки сокращает первую ветвь поиска.
  • Эвристическое решение. Если для задачи известна простая жадная или конструктивная эвристика, её результат подаётся как подсказка. Решатель доказывает или улучшает это решение, а не ищет первое допустимое с нуля.
  • Решение похожей задачи. В сериях задач, отличающихся параметрами (значениями коэффициентов, размерами заявок), решение предыдущей задачи часто полезно как подсказка для следующей.

Главный эффект подсказок — ускорение нахождения первого допустимого решения. Оно даёт верхнюю оценку (для задачи минимизации) и позволяет методу ветвей и границ отсекать неперспективные ветви с раннего этапа поиска.

Когда подсказки бесполезны​

  • Чистые LP-задачи. Симплекс-метод и метод внутренней точки имеют собственные механизмы инициализации и горячего старта. Передача стартовых значений через подсказки в этих алгоритмах не используется.
  • Малые задачи, решающиеся за доли секунды без подсказок. Накладные расходы на подготовку подсказок не оправданы.
  • Сильно изменившаяся задача. Если структура задачи существенно изменилась — изменены ограничения, добавлены или удалены переменные, — стартовое решение от предыдущего расчёта может не только не помочь, но и заметно ухудшить первый этап поиска.

Пример использования​

Типичный сценарий — повторное решение MIP-задачи с подсказкой по предыдущему решению (имитация регламентного перепланирования):

Решение = Модель.Решить();

// При повторном решении (перепланировании) — подсказать значения булевых индикаторов
Если Решение.РешениеНайдено() Тогда
    Для Каждого Индикатор Из ИндикаторыАктивации Цикл
        Модель.Подсказки().Добавить(
            Индикатор,
            Решение.ЗначениеПеременной(Индикатор)
        );
    КонецЦикла;
КонецЕсли;

Подсказки могут передаваться выборочно — только для булевых переменных (как в примере выше) или только для тех непрерывных переменных, от значений которых зависит структура решения. Передавать подсказки для всех переменных не обязательно и часто избыточно.

См. также​