OR-Tools — это программное обеспечение с открытым исходным кодом для комбинаторной оптимизации , которое стремится найти наилучшее решение проблемы из очень большого набора возможных решений. Вот несколько примеров проблем, которые решает OR-Tools:
- Маршрутизация транспортных средств: найдите оптимальные маршруты для парков транспортных средств, которые забирают и доставляют посылки с учетом ограничений (например, «этот грузовик не может вместить более 20 000 фунтов» или «все доставки должны быть выполнены в течение двух часов»).
- Планирование: найдите оптимальное расписание для сложного набора задач, некоторые из которых необходимо выполнить раньше других, на фиксированном наборе компьютеров или других ресурсов.
- Упаковка в ящики: упакуйте как можно больше предметов разного размера в фиксированное количество ящиков с максимальной вместимостью.
В большинстве случаев подобные проблемы имеют огромное количество возможных решений — слишком много, чтобы компьютер мог найти их все. Чтобы преодолеть это, OR-Tools использует современные алгоритмы, чтобы сузить набор поиска, чтобы найти оптимальное (или близкое к оптимальному) решение.
OR-Tools включает в себя решатели для:
- Программирование ограничений
- Набор приемов поиска допустимых решений проблемы, выраженный в виде ограничений (например, помещение нельзя использовать для двух мероприятий одновременно, или расстояние до посевов должно быть меньше длины шланга, но не более пяти). Телепередачи можно записывать сразу).
- Линейное и смешанное целочисленное программирование
- Линейный оптимизатор Глопа находит оптимальное значение линейной целевой функции, учитывая набор линейных неравенств в качестве ограничений (например, назначение людей на работу или поиск наилучшего распределения набора ресурсов при минимальных затратах). Glop и программное обеспечение для программирования смешанных целых чисел SCIP также доступны через Службу оптимизации сценариев Google Apps.
- Маршрут транспортного средства
- Специализированная библиотека для определения лучших маршрутов транспортных средств с учетом ограничений.
- Алгоритмы графов
- Код для поиска кратчайших путей в графах, потоков с минимальной стоимостью, максимальных потоков и назначений линейной суммы.
В следующем разделе вы быстро начнете использовать OR-Tools.