Производительность и качество
Задача оптимизатора — производить стабильные и при этом оптимальные результаты, чтобы задача получила наилучшее возможное решение.
Первый шаг на пути к этой цели — метод «разрыва» (gap concept), который используется в линейном и целочисленном программировании для оценки качества результата.
Данный метод позволяет измерить, насколько текущее значение приближено к оптимальному. Вот как он работает:
- Оптимизатор удаляет из системы уравнений все ограничения и решает её. Так он получает лучшее, но недостижимое решение.
- Оптимизатор возвращает ограничения в систему уравнений и снова решает её. При этом он измеряет разрыв между текущим решением и оптимальным, которое было найдено на предыдущем этапе. Когда разница между двумя решениями попадает в пределы заданной погрешности, оптимизация останавливается.
К сожалению, в комбинаторной оптимизации такой подход использовать нельзя, потому что в ней отсутствуют линейные уравнения, позволяющие оценить оптимум.
Единственный способ гарантировать качество работы комбинаторного оптимизатора — это тестирование, при котором используется множество наборов данных с известными результатами. Это позволяет вычислить погрешность и проанализировать качество.
Как мы тестируем движок?
Мы постоянно проверяем способность оптимизатора быстро находить оптимальные или почти оптимальные решения для реальных задач.
- В тестировании применяются публичные и собственные наборы данных. Используются задачи разной размерности. Это даёт гарантию, что оптимизатор сможет одинаково успешно справляться с разными заданиями за установленное время.
- Все тесты выполняются с использованием стандартной версии оптимизатора, не адаптированной под конкретные задачи.
Мы оцениваем производительность оптимизатора, определяя время на поиск решения, которое отклоняется от оптимального не более чем на 3-5%. Для большинства наборов данных это время составляет менее 10 минут.
