Производительность и качество
Возможности

Производительность и качество

Задача оптимизатора — производить стабильные и при этом оптимальные результаты, чтобы задача получила наилучшее возможное решение.

Первый шаг на пути к этой цели — метод «разрыва» (gap concept), который используется в линейном и целочисленном программировании для оценки качества результата.

Данный метод позволяет измерить, насколько текущее значение приближено к оптимальному. Вот как он работает:

  • Оптимизатор удаляет из системы уравнений все ограничения и решает её. Так он получает лучшее, но недостижимое решение.
  • Оптимизатор возвращает ограничения в систему уравнений и снова решает её. При этом он измеряет разрыв между текущим решением и оптимальным, которое было найдено на предыдущем этапе. Когда разница между двумя решениями попадает в пределы заданной погрешности, оптимизация останавливается.

К сожалению, в комбинаторной оптимизации такой подход использовать нельзя, потому что в ней отсутствуют линейные уравнения, позволяющие оценить оптимум.

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

Как мы тестируем движок?

Мы постоянно проверяем способность оптимизатора быстро находить оптимальные или почти оптимальные решения для реальных задач.

  • В тестировании применяются публичные и собственные наборы данных. Используются задачи разной размерности. Это даёт гарантию, что оптимизатор сможет одинаково успешно справляться с разными заданиями за установленное время.
  • Все тесты выполняются с использованием стандартной версии оптимизатора, не адаптированной под конкретные задачи.

Мы оцениваем производительность оптимизатора, определяя время на поиск решения, которое отклоняется от оптимального не более чем на 3-5%. Для большинства наборов данных это время составляет менее 10 минут.