• OR-Tools
  • About OR-Tools //developers.google.com
    программное обеспечение с открытым исходным кодом для комбинаторной оптимизации , которое стремится найти лучшее решение проблемы из очень большого набора возможных решений.
  • Constraint Optimization / Оптимизация ограниченийОптимизация ограничений или программирование ограничений (CP) — это название, данное для определения возможных решений из очень большого набора кандидатов, где проблема может быть смоделирована в терминах произвольных ограничений. Проблемы КП возникают во многих научных и инженерных дисциплинах. Слово «программирование» является немного неправильным, подобно тому, как «компьютер» когда-то означал «человек, который вычисляет». Здесь «программирование» относится к составлению плана, а не к программированию на компьютерном языке.CP основан на осуществимости (поиск допустимого решения), а не на оптимизации (поиск оптимального решения), и фокусируется на ограничениях и переменных, а не на целевой функции. Фактически, проблема CP может даже не иметь целевой функции — цель может просто заключаться в том, чтобы сузить широкий набор возможных решений до более управляемого подмножества путем добавления ограничений к проблеме.Примером проблемы, которая хорошо подходит для CP, является планирование сотрудников . Проблема возникает, когда компаниям, которые работают непрерывно, например, фабрикам, необходимо составлять еженедельные расписания для своих сотрудников. Вот очень простой пример: компания работает три 8-часовые смены в день и распределяет трех из четырех своих сотрудников на разные смены каждый день, а четвертой дает выходной. Даже в таком маленьком случае количество возможных расписаний огромно: каждый день их 4! = 4 · 3 · 2 · 1 = 24 возможных назначения сотрудников, поэтому количество возможных недельных расписаний составляет 24 7, что превышает 4,5 миллиарда. Обычно существуют и другие ограничения, которые сокращают количество возможных решений — например, каждый сотрудник работает хотя бы минимальное количество дней в неделю. Метод CP отслеживает, какие решения остаются возможными при добавлении новых ограничений, что делает его мощным инструментом для решения больших реальных задач планирования.

    В следующем разделе описывается решатель CP-SAT, основной решатель OR-Tools для программирования ограничений. SAT означает «satisfiability» выполнимость : решатель использует методы для решения задач SAT наряду с методами CP.

    Вот несколько примеров задач планирования, которые хорошо подходят для решателя CP-SAT:

    Расписание сотрудников
    Проблема магазина вакансий
    У CP есть широко распространенное и очень активное сообщество по всему миру со специализированными научными журналами, конференциями и арсеналом различных методов решения. CP успешно применяется при планировании, составлении графиков и многих других областях с неоднородными ограничениями.

  • Linear Optimization / Линейная оптимизацияЛинейная оптимизация (или линейное программирование ) — это название, данное вычислению наилучшего решения проблемы, моделируемой как набор линейных отношений. Эти проблемы возникают во многих научных и инженерных дисциплинах. (Слово «программирование» является немного неправильным, подобно тому, как «компьютер» когда-то означало «человека, который занимается вычислениями». Здесь «программирование» относится к составлению плана, а не к программированию на компьютерном языке.)В качестве хорошего руководства по линейной оптимизации мы рекомендуем кулинарную книгу моделирования Mosek .Google предоставляет два способа решения задач линейной оптимизации: библиотеку с открытым исходным кодом Glop и службу линейной оптимизации в скрипте Google Apps.

    Glop — это собственный линейный решатель Google, доступный в виде открытого исходного кода . Вы можете получить доступ к Glop через оболочку линейного решателя OR-Tools , которая является оболочкой для Glop, а также нескольких других сторонних решателей линейной оптимизации. Чтобы узнать, как решить простую линейную задачу с помощью Glop на всех поддерживаемых языках, см. Начало работы с OR-Tools .
    Служба линейной оптимизации в Google Apps Script позволяет разработчикам выполнять вызовы функций для решения задач линейной оптимизации. Он полагается на Glop для чисто задач линейной оптимизации, где все переменные могут принимать действительные значения. Если какие-либо переменные должны быть целыми числами, служба использует SCIP от Zuse-Institut Berlin.
    Только первый вариант требует установки OR-Tools.

  • Vehicle Routing / Маршрутизация транспортных средствОдним из наиболее важных приложений оптимизации является маршрутизация транспортных средств , цель которого состоит в том, чтобы найти лучшие маршруты для парка транспортных средств, посещающих набор местоположений. Обычно «лучший» означает маршруты с наименьшей общей протяженностью или стоимостью. Вот несколько примеров проблем с маршрутизацией:Компания по доставке посылок хочет назначить водителям маршруты для доставки.
    Компания кабельного телевидения хочет назначить маршруты для технических специалистов, чтобы они могли звонить в бытовые службы.
    Компания по обмену поездками хочет назначить водителям маршруты для посадки и высадки пассажиров.Более общая версия TSP — это проблема маршрутизации транспортных средств (VRP), в которой есть несколько транспортных средств. В большинстве случаев у VRP есть ограничения: например, транспортные средства могут быть рассчитаны на максимальный вес или объем предметов, которые они могут перевозить, или водителям может потребоваться посетить места в течение определенных временных окон, запрошенных клиентами. OR-Tools может решить многие типы VRP, включая следующие:

    Задача коммивояжера , классическая задача маршрута, в которой используется только одно транспортное средство.
    Проблема маршрутизации транспортных средств , обобщение TSP с несколькими транспортными средствами.
    VRP с ограничениями вместимости , в которых автомобили имеют максимальную вместимость для предметов, которые они могут перевозить.
    VRP с временными окнами , в которых автомобили должны посещать локации в определенные промежутки времени.
    VRP с ограниченными ресурсами , такими как пространство или персонал для погрузки и разгрузки транспортных средств в депо (отправная точка для маршрутов).
    VRP с прерванными посещениями , когда транспортные средства не обязаны посещать все места, но должны платить штраф за каждое прерванное посещение.

  • Network Flows / Сетевые потокиМногие задачи информатики можно представить в виде графа, состоящего из узлов и связей между ними. Примерами являются проблемы сетевого потока , которые связаны с транспортировкой товаров или материалов по сети, такой как железнодорожная система. Вы можете представить сетевой поток графом, узлами которого являются города, а дугами — железнодорожные линии между ними. (Их называют потоками, потому что их свойства аналогичны свойствам воды, протекающей по сети труб.)Ключевым ограничением сетевых потоков является то, что каждая дуга имеет пропускную способность — максимальное количество, которое может быть перенесено по дуге за фиксированный период времени. Задача максимального потока состоит в том, чтобы определить максимальный общий объем, который может быть транспортирован по всем дугам в сети с учетом ограничений пропускной способности.OR-Tools предоставляет несколько средств решения проблем сетевого потока в своих библиотеках графов .

Читать далее Инструменты Google OR-Tools →