Zacznij korzystać z OR-Tools dla domeny .Net

Poniższe sekcje pomogą Ci zacząć korzystać z narzędzi OR-Tools dla domeny .Net:

• Czym jest problem z optymalizacją?
• Rozwiązywanie problemu z optymalizacją w domenie .Net
• Więcej przykładów z domeną .Net
• Określanie typu problemu, który chcesz rozwiązać

Co to jest problem z optymalizacją?

Celem optymalizacji jest znalezienie najlepszego rozwiązania problemu spośród dużej liczby możliwych rozwiązań. Czasami uda Ci się znaleźć odpowiednie rozwiązanie, ale LUB-Tools może to zrobić.

Oto typowy problem optymalizacyjny. Załóżmy, że firma transportowa dostarcza swoje paczki do klientów flotą ciężarówek. Każdego dnia firma musi nadawać paczki do ciężarówek, a potem wybierać trasę dla każdej ciężarówki. Każde możliwe przypisanie paczek i tras wiąże się z kosztem zależnym od łącznej odległości pokonanej przez ciężarówki, a ewentualnie także z innymi czynnikami. Problem polega na tym, by wybrać przypisania pakietów i tras, które mają jak najmniejsze koszty.

Podobnie jak wszystkie problemy optymalizacyjne, ten problem wyróżnia się następującymi elementami:

• Cel – liczba, którą chcesz zoptymalizować. W przykładzie powyżej celem jest minimalizacja kosztów. Aby skonfigurować problem optymalizacyjny, musisz zdefiniować funkcję, która oblicza wartość celu dla każdego możliwego rozwiązania. Jest to tzw. funkcja celu. W poprzednim przykładzie funkcja celu obliczyła łączny koszt każdego przypisania pakietów i tras.

  Rozwiązanie optymalne to takie, dla którego wartość funkcji celu jest najlepsza. („Najwyższa” może być wartością maksymalną lub minimalną).

• Ograniczenia – ograniczenia zbioru możliwych rozwiązań zależne od konkretnych wymagań danego problemu. Jeśli na przykład firma transportowa nie może przypisać ciężarówkom przesyłek powyżej określonej wagi, nałoży to ograniczenie na dostępne rozwiązania.

  Rozwiązanie wykonalne to takie, które spełnia wszystkie podane ograniczenia zadania i nie jest optymalne.

Pierwszym krokiem do rozwiązania problemu optymalizacyjnego jest określenie celu i ograniczeń.

Rozwiązywanie problemu optymalizacyjnego w domenie .Net

Następnie podajemy przykład problemu optymalizacyjnego oraz pokazujemy, jak skonfigurować i rozwiązać ten problem w domenie .Net.

Przykład optymalizacji liniowej

Jednym z najstarszych i najpopularniejszych obszarów optymalizacji jest optymalizacja liniowa (programowanie liniowe), w której funkcję celu i ograniczenia można zapisywać jako wyrażenia liniowe. Oto prosty przykład problemu tego typu.

Maksymalizuj 3x + y pod warunkiem, że:

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

W tym przykładzie funkcja celu to 3x + y. Zarówno funkcja celu, jak i ograniczenia są określone za pomocą wyrażeń liniowych, co sprawia, że problem jest liniowy.

Główne kroki rozwiązywania problemu

Podstawowe kroki konfigurowania i rozwiązywania problemu są takie same w każdym języku:

1. Zaimportuj wymagane biblioteki.
2. zadeklarować rozwiązanie,
3. Tworzymy zmienne,
4. Zdefiniuj ograniczenia,
5. Zdefiniuj funkcję celu,
6. Wywołaj rozwiązanie rozwiązania
7. Wyświetl wyniki.

Program .Net

W tej części omawiamy program z rozszerzeniem .Net, który pomaga skonfigurować i rozwiązać problem.

Uwaga: pełny program.Net i instrukcje uruchomienia go znajdziesz na końcu tej sekcji.

Aby to zrobić:

• Zaimportuj wymagane biblioteki.

  using System;
  using Google.OrTools.Init;
  using Google.OrTools.LinearSolver;

• Zadeklaruj rozwiązanie.

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

  Wartość MPSolver to kod służący do rozwiązywania dowolnych problemów z programowaniem liniowym lub programowaniem opartym na mieszanych liczbach całkowitych.
• Utwórz zmienne.

  // 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());

• Określ ograniczenia. Pierwsze 2 ograniczenia (0 ≤ x ≤ 1 i 0 ≤ y ≤ 2) są już ustawione w definicjach zmiennych. Ten kod definiuje ograniczenie x + y ≤ 2:

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

  Metoda SetCoefficient określa współczynniki x i y w wyrażeniu ograniczenia.
• Zdefiniuj funkcję celu.

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

  Metoda setMaximization wskazuje na problem z maksymalizacją. Podstawową metodą C++ jest SetMaximization.
• Wywołaj rozwiązanie rozwiązania i wyświetl wyniki.

  Console.WriteLine("Solving with " + solver.SolverVersion());
  Solver.ResultStatus resultStatus = solver.Solve();
  Console.WriteLine("Status: " + resultStatus);
  if (resultStatus != Solver.ResultStatus.OPTIMAL)
  {
      Console.WriteLine("The problem does not have an optimal solution!");
      if (resultStatus == Solver.ResultStatus.FEASIBLE)
      {
          Console.WriteLine("A potentially suboptimal solution was found");
      }
      else
      {
          Console.WriteLine("The solver could not solve the problem.");
          return;
      }
  }
  
  Console.WriteLine("Solution:");
  Console.WriteLine("Objective value = " + solver.Objective().Value());
  Console.WriteLine("x = " + x.SolutionValue());
  Console.WriteLine("y = " + y.SolutionValue());

Ukończ program

Pełny program znajdziesz poniżej.

using System;
using Google.OrTools.Init;
using Google.OrTools.LinearSolver;

public class BasicExample
{
    static void Main()
    {
        Console.WriteLine("Google.OrTools version: " + OrToolsVersion.VersionString());

        // Create the linear solver with the GLOP backend.
        Solver solver = Solver.CreateSolver("GLOP");
        if (solver is null)
        {
            Console.WriteLine("Could not create solver GLOP");
            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, x + y <= 2.
        Constraint constraint = solver.MakeConstraint(double.NegativeInfinity, 2.0, "constraint");
        constraint.SetCoefficient(x, 1);
        constraint.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();

        Console.WriteLine("Solving with " + solver.SolverVersion());
        Solver.ResultStatus resultStatus = solver.Solve();

        Console.WriteLine("Status: " + resultStatus);
        if (resultStatus != Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine("The problem does not have an optimal solution!");
            if (resultStatus == Solver.ResultStatus.FEASIBLE)
            {
                Console.WriteLine("A potentially suboptimal solution was found");
            }
            else
            {
                Console.WriteLine("The solver could not solve the problem.");
                return;
            }
        }

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

        Console.WriteLine("Advanced usage:");
        Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds");
        Console.WriteLine("Problem solved in " + solver.Iterations() + " iterations");
    }
}

Uruchamianie programu .Net

Powyższy program możesz uruchomić w ten sposób:

1. Skopiuj powyższy kod i wklej go do nowego pliku i zapisz go jako BasicExample.cs. w podkatalogu examples/dotnet katalogu, w którym zainstalowano OR-Tools.
2. W tym samym katalogu utwórz nowy plik BasicExample.csproj i dodaj ten kod:

   <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. Na najwyższym poziomie katalogu, w którym zainstalowano narzędzia OR-Tools, otwórz okno polecenia i wpisz:

   make run SOURCE=examples/dotnet/BasicExample.cs

Uwaga: programy .Net musisz uruchamiać na najwyższym poziomie katalogu, w którym zainstalowano OR-Tools.

Programy .Net można zapisywać i uruchamiać w innym katalogu niż examples/dotnet/, ale jest to nieco trudniejsze: musisz zmodyfikować w pliku csproj poniższy wiersz:

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

aby uzyskać prawidłową ścieżkę do katalogu packages.

Najprostszym rozwiązaniem jest umieszczenie programów .Net w katalogu examples/dotnet/.

Program zwraca wartości x i y, które maksymalizują funkcję celu:

Solution:
x =  1.0
y =  1.0

Aby skompilować program bez jego uruchamiania, wpisz:

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

Jeśli wprowadzisz zmiany w programie, musisz go ponownie skompilować w sposób przedstawiony powyżej.

Więcej przykładów z domeną .Net

Więcej przykładów witryn z rozszerzeniem .net, które ilustrują sposoby rozwiązywania różnych rodzajów problemów optymalizacyjnych, znajdziesz w przykładach.

określenie rodzaju problemu, który chcesz rozwiązać;

Istnieje wiele różnych rodzajów problemów z optymalizacją. W przypadku każdego rodzaju problemu stosowane są różne podejścia i algorytmy do znalezienia optymalnego rozwiązania.

Zanim zaczniesz pisać program rozwiązania problemu optymalizacyjnego, musisz określić rodzaj problemu, z jakim masz do czynienia, a następnie wybrać odpowiedni rozwiązania, czyli algorytm umożliwiający znalezienie optymalnego rozwiązania.

Poniżej znajdziesz krótkie omówienie problemów, które rozwiązują za pomocą LUB Narzędzia, oraz linki do sekcji w tym przewodniku, które wyjaśniają, jak rozwiązywać poszczególne rodzaje problemów.

• Optymalizacja liniowa
• Optymalizacja ograniczeń
• Optymalizacja przy użyciu liczb całkowitych o mieszanych liczbach
• Projekt
• Harmonogram
• Pakowanie
• Routing
• Przepływy sieci

Optymalizacja liniowa

Jak wiesz z poprzedniej sekcji, liniowy problem optymalizacji to taki, w którym funkcja celu i ograniczenia są wyrażeniami liniowymi w zmiennych.

Głównym rozwiązaniem w narzędziach LUB w przypadku tego typu zadań jest rozwiązanie do optymalizacji liniowej, które jest kodekiem kilku różnych bibliotek do optymalizacji liniowej i mieszanej liczby całkowitej, w tym bibliotek zewnętrznych.

Więcej informacji o optymalizacji liniowej

Optymalizacja z mieszaną liczbą całkowitą

Problem z optymalizacją mieszaną liczb całkowitych polega na tym, że niektóre lub wszystkie zmienne muszą być liczbami całkowitymi. Przykładem może być problem z przypisywaniem, w którym trzeba przypisać grupę instancji roboczych do zbioru zadań. Dla każdej instancji roboczej i zadania definiujesz zmienną, której wartość wynosi 1, jeśli dana instancja robocza jest przypisana do danego zadania, a 0 w innym przypadku. W tym przypadku zmienne mogą przyjmować tylko wartości 0 lub 1.

Więcej informacji o optymalizacji przy użyciu mieszanej liczby całkowitej

Optymalizacja ograniczeń

Optymalizacja ograniczeń, czyli programowanie ograniczeń (CP), wskazuje możliwe rozwiązania na podstawie bardzo dużej grupy propozycji, w przypadku których problem można modelować na podstawie dowolnych ograniczeń. Wskaźnik KPI opiera się na wykonalności (znajdowaniu możliwego rozwiązania), a nie na optymalizacji (znajdowaniu optymalnego rozwiązania). Koncentruje się na ograniczeniach i zmiennych, a nie na funkcji celu. Celu optymalizacyjnego można jednak używać do rozwiązywania problemów optymalizacyjnych. W tym celu wystarczy porównać wartości funkcji celu dla wszystkich możliwych rozwiązań.

Więcej informacji o optymalizacji ograniczeń

Projekt

Problemy z przypisaniem obejmują przypisanie grupy agentów (np. instancji roboczych lub maszyn) do zbioru zadań, przy czym istnieje stały koszt przypisania każdego agenta do konkretnego zadania. Problem polega na znalezieniu projektu o najniższym całkowitym koszcie. Są one szczególnym przypadkiem problemów z przepływem sieci.

Więcej informacji o przypisywaniu

Pakowanie

Pakowanie w kopercie to problem z pakowaniem zestawu obiektów o różnych rozmiarach do pojemników o różnej pojemności. Celem jest zapakowanie jak największej liczby obiektów w zależności od pojemności kontenerów. Szczególnym przypadkiem jest problem plecaka, w którym występuje tylko jeden kontener.

Więcej informacji o pakowaniu

Planuję

Problemy z planowaniem obejmują przypisywanie zasobów w celu wykonania zestawu zadań w określonym czasie. Ważnym przykładem jest problem w miejscu pracy, w którym wiele zadań jest przetwarzanych na kilku maszynach. Każde zadanie składa się z sekwencji zadań, które należy wykonać w określonej kolejności, a każde zadanie musi zostać wykonane na określonej maszynie. Problem polega na tym, że musisz tak ustawić harmonogram, aby wszystkie zadania zostały wykonane w jak najkrótszym czasie.

Więcej informacji o planowaniu

Routing

Problemy z wyznaczaniem tras obejmują znajdowanie optymalnych tras dla floty pojazdów, które mogą przemierzyć sieć, wyznaczone na wykresie kierującym. Przykładem problemu z wyznaczaniem tras jest przypisywanie paczek do ciężarówek, opisane w części Czym jest problem z optymalizacją?. Innym problemem jest problem podróżujących sprzedawców.

Więcej informacji o routingu

Przepływy w sieci

Wiele problemów optymalizacyjnych można przedstawić za pomocą grafu skierowanego, który składa się z węzłów i łuków kierunkowych między nimi. Na przykład problemy transportowe, w ramach których towary są dostarczane przez sieć kolejową, można przedstawić za pomocą wykresu, na którym łuki to linie kolejowe, a węzły to centra dystrybucyjne.

W zadaniu maksymalnego przepływu każdy łuk ma maksymalną pojemność, którą można przez niego przenieść. Problem polega na przypisaniu liczby towarów do wysyłki dla każdego łuku tak, aby łączna ilość przewożonych towarów była jak największa.

Więcej informacji o przepływach w sieci