Начало работы с OR-Tools для .Net

Следующие разделы помогут вам начать работу с OR-Tools для .Net:

• Что такое проблема оптимизации?
• Решение задачи оптимизации в .Net
• Дополнительные примеры .Net
• Определение типа проблемы, которую вы хотите решить

Что такое проблема оптимизации?

Цель оптимизации — найти лучшее решение проблемы из большого множества возможных решений. (Иногда вам будет достаточно найти любое осуществимое решение; OR-Tools тоже может это сделать.)

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

Как и все задачи оптимизации, эта задача имеет следующие элементы:

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

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

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

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

Первым шагом в решении задачи оптимизации является определение цели и ограничений.

Решение задачи оптимизации в .Net

Далее мы приведем пример задачи оптимизации и покажем, как ее настроить и решить в .Net.

Пример линейной оптимизации

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

Максимизируйте 3x + y при следующих ограничениях:

1. 0 ≤ x ≤ 1
2. 0 ≤ y ≤ 2
3. x + y ≤ 2

Целевая функция в этом примере — 3x + y . И целевая функция, и ограничения задаются линейными выражениями, что делает эту задачу линейной.

Основные шаги решения проблемы

Для каждого языка основные этапы постановки и решения задачи одинаковы:

1. Импортируйте необходимые библиотеки,
2. Объявите решатель,
3. Создайте переменные,
4. Определите ограничения,
5. Определить целевую функцию,
6. Вызовите решатель и
7. Отобразите результаты.

.Net-программа

В этом разделе рассматривается программа .Net, которая устанавливает и решает проблему.

Примечание. Полная программа .Net и шаги по ее запуску показаны в конце раздела.

Вот шаги:

• Импортируйте необходимые библиотеки.

  using System;
  using Google.OrTools.LinearSolver;

• Объявите решатель.

  // Create the linear solver with the GLOP backend.
  Solver solver = Solver.CreateSolver("GLOP");
  if (solver is null)
  {
      return;
  }

  MPSolver — это оболочка для решения любых задач линейного или смешанного целочисленного программирования .
• Создайте переменные.

  // Create the variables x and y.
  Variable x = solver.MakeNumVar(0.0, 1.0, "x");
  Variable y = solver.MakeNumVar(0.0, 2.0, "y");
  
  Console.WriteLine("Number of variables = " + solver.NumVariables());

• Определите ограничения. Первые два ограничения, 0 ≤ x ≤ 1 и 0 ≤ y ≤ 2 , уже установлены определениями переменных. Следующий код определяет ограничение x + y ≤ 2 :

  // Create a linear constraint, 0 <= x + y <= 2.
  Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
  ct.SetCoefficient(x, 1);
  ct.SetCoefficient(y, 1);
  
  Console.WriteLine("Number of constraints = " + solver.NumConstraints());

  Метод SetCoefficient устанавливает коэффициенты x и y в выражении для ограничения.
• Определите целевую функцию.

  // Create the objective function, 3 * x + y.
  Objective objective = solver.Objective();
  objective.SetCoefficient(x, 3);
  objective.SetCoefficient(y, 1);
  objective.SetMaximization();

  Метод setMaximization объявляет это проблемой максимизации. (Основной метод C++ — SetMaximization .
• Вызовите решатель и отобразите результаты.

  solver.Solve();
  Console.WriteLine("Solution:");
  Console.WriteLine("Objective value = " + solver.Objective().Value());
  Console.WriteLine("x = " + x.SolutionValue());
  Console.WriteLine("y = " + y.SolutionValue());

Полная программа

Полная программа представлена ​​ниже.

using System;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            return;
        }

        // Create the variables x and y.
        Variable x = solver.MakeNumVar(0.0, 1.0, "x");
        Variable y = solver.MakeNumVar(0.0, 2.0, "y");

        Console.WriteLine("Number of variables = " + solver.NumVariables());

        // Create a linear constraint, 0 <= x + y <= 2.
        Constraint ct = solver.MakeConstraint(0.0, 2.0, "ct");
        ct.SetCoefficient(x, 1);
        ct.SetCoefficient(y, 1);

        Console.WriteLine("Number of constraints = " + solver.NumConstraints());

        // Create the objective function, 3 * x + y.
        Objective objective = solver.Objective();
        objective.SetCoefficient(x, 3);
        objective.SetCoefficient(y, 1);
        objective.SetMaximization();

        solver.Solve();

        Console.WriteLine("Solution:");
        Console.WriteLine("Objective value = " + solver.Objective().Value());
        Console.WriteLine("x = " + x.SolutionValue());
        Console.WriteLine("y = " + y.SolutionValue());
    }
}

Запуск программы .Net

Вы можете запустить приведенную выше программу следующим образом:

1. Скопируйте и вставьте приведенный выше код в новый файл и сохраните его как BasicExample.cs . в подкаталоге examples/dotnet каталога, в котором вы установили OR-Tools.
2. В том же каталоге создайте новый файл BasicExample.csproj и добавьте следующий код:

   <Project Sdk="Microsoft.NET.Sdk">
     <PropertyGroup>
       <OutputType>Exe</OutputType>
       <LangVersion>7.3</LangVersion>
       <TargetFramework>netcoreapp3.1</TargetFramework>
       <EnableDefaultItems>false</EnableDefaultItems>
       <!-- see https://github.com/dotnet/docs/issues/12237 -->
       <RollForward>LatestMajor</RollForward>
       <RestoreSources>../../../temp_dotnet/packages;$(RestoreSources);https://api.nuget.org/v3/index.json</RestoreSources>
       <AssemblyName>Google.OrTools.BasicExample</AssemblyName>
       <IsPackable>true</IsPackable>
     </PropertyGroup>
   
     <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
       <DebugType>full</DebugType>
       <Optimize>true</Optimize>
       <GenerateTailCalls>true</GenerateTailCalls>
     </PropertyGroup>
   
     <ItemGroup>
       <Compile Include="BasicExample.cs" />
       <PackageReference Include="Google.OrTools" Version="9.1.*" />
     </ItemGroup>
   </Project>
   

3. На верхнем уровне каталога, в котором вы установили OR-Tools, откройте командное окно и введите:

   make run SOURCE=examples/dotnet/BasicExample.cs

Примечание. Вы должны запускать программы .Net с верхнего уровня каталога, в котором вы установили OR-Tools.

Можно сохранять и запускать программы .Net в другом каталоге, чем examples/dotnet/ , но это немного сложнее: вы должны изменить следующую строку файла csproj , показанного выше:

../../../packages;$(RestoreSources);https://api.nuget.org/v3/index.json

чтобы указать правильный путь к каталог packages .

Самое простое решение — поместить ваши .Net-программы в каталог examples/dotnet/ .

Программа возвращает значения x и y , которые максимизируют целевую функцию:

Solution:
x =  1.0
y =  1.0

Чтобы просто скомпилировать программу, не запуская ее, введите:

make build SOURCE=relative/path/to/SimpleProgram.cs

Если вы внесете изменения в программу, вам придется перекомпилировать ее, как показано выше.

Дополнительные примеры .Net

Дополнительные примеры .Net, иллюстрирующие решение различных типов задач оптимизации, см. в разделе Примеры .

Определение типа проблемы, которую вы хотите решить

В мире существует множество различных типов задач оптимизации. Для каждого типа задач существуют разные подходы и алгоритмы поиска оптимального решения.

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

Ниже вы найдете краткий обзор типов проблем, которые решает OR-Tools, а также ссылки на разделы этого руководства, в которых объясняется, как решить каждый тип проблем.

• Линейная оптимизация
• Оптимизация ограничений
• Смешанно-целочисленная оптимизация
• Назначение
• Планирование
• Упаковка
• Маршрутизация
• Сетевые потоки

Линейная оптимизация

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

Основным решателем в OR-Tools для задач такого типа является решатель линейной оптимизации, который на самом деле является оболочкой для нескольких различных библиотек для линейной и смешанно-целочисленной оптимизации , включая сторонние библиотеки.

Узнайте больше о линейной оптимизации

Смешанно-целочисленная оптимизация

Задача смешанной целочисленной оптимизации — это задача, в которой некоторые или все переменные должны быть целыми числами. Примером может служить задача назначения , в которой группе работников необходимо назначить набор задач. Для каждого работника и задачи вы определяете переменную, значение которой равно 1, если данный работник назначен данной задаче, и 0 в противном случае. В этом случае переменные могут принимать только значения 0 или 1.

Узнайте больше о смешанно-целочисленной оптимизации.

Оптимизация ограничений

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

Узнайте больше об оптимизации ограничений

Назначение

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

Узнать больше о задании

Упаковка

Бин-упаковка — это задача упаковки набора предметов разного размера в контейнеры разной вместимости. Цель — упаковать как можно больше объектов с учетом вместимости контейнеров. Особым случаем является задача о рюкзаке , в которой контейнер всего один.

Узнайте больше об упаковке в мусорные контейнеры

Планирование

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

Узнайте больше о планировании

Маршрутизация

Задачи маршрутизации включают в себя поиск оптимальных маршрутов для парка транспортных средств, пересекающих сеть, определенную ориентированным графом. Проблема назначения посылок грузовикам доставки, описанная в разделе «Что такое задача оптимизации?» , является одним из примеров проблемы маршрутизации. Другая проблема – это задача коммивояжера .

Узнать больше о маршрутизации

Сетевые потоки

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

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

Узнайте больше о сетевых потоках