Zacznij korzystać z OR-Tools dla domeny .Net

Poniższe sekcje ułatwią Ci rozpoczęcie korzystania z OR-Tools dla domeny .Net:

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 nie uda Ci się znaleźć dowolnego możliwego rozwiązania; możesz też użyć LUB-Tools).

Oto typowy problem optymalizacyjny. Załóżmy, że firma transportowa dostarcza przesyłki do klientów flotą ciężarówek. Każdego dnia firma musi przypisywać paczki do ciężarówek, a potem wybrać dla każdej z nich trasę dostawy przesyłek. Każde możliwe przypisanie paczek i tras wiąże się z kosztami wynikającymi z całkowitej odległości przebytej przez ciężarówki i ewentualnie innych czynników. Problem polega na tym, by wybrać przypisania pakietów i tras o najmniejszych kosztach.

Podobnie jak wszystkie problemy optymalizacyjne, ten problem obejmuje następujące elementy:

  • Cel – liczba, którą chcesz zoptymalizować. W powyższym przykładzie celem jest ograniczenie kosztów. Aby skonfigurować problem optymalizacyjny, musisz zdefiniować funkcję, która oblicza wartość celu dla dowolnego możliwego rozwiązania. Jest to tzw. funkcja celu. W poprzednim przykładzie funkcja celu obliczyła łączny koszt dowolnego 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 dotyczące zbioru możliwych rozwiązań określonych na podstawie konkretnych wymagań danego problemu. Jeśli na przykład firma transportowa nie może przypisać ciężarówkom paczek o określonej wadze powyżej określonej wagi, będzie to nakładało ograniczenia na rozwiązania.

    Możliwe rozwiązanie to takie, które spełnia wszystkie podane ograniczenia problemu i niekoniecznie jest optymalne.

Pierwszym krokiem w rozwiązaniu problemu z optymalizacją jest określenie celu i ograniczeń.

Jak rozwiązać problem optymalizacyjny w domenie .Net

Następnie podajemy przykład problemu z optymalizacją, a potem pokazujemy, jak go skonfigurować i rozwiązać w domenie .Net.

Przykład optymalizacji liniowej

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

Maksymalizuj wartość 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

W przypadku każdego języka podstawowe czynności związane z konfigurowaniem i rozwiązywaniem zadania są takie same:

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

Program .Net

W tej sekcji omówiono program .Net, który konfiguruje i rozwiązuje ten problem.

Aby to zrobić:

  • Zaimportuj wymagane biblioteki.
    using System;
using Google.OrTools.LinearSolver;
  • Zadeklaruj rozwiązanie. 
    // Create the linear solver with the GLOP backend.
Solver solver = Solver.CreateSolver("GLOP");
if (solver is null)
{
    return;
}
    Kod MPSolver służy do rozwiązywania wszystkich problemów z programowaniem liniowym lub programowaniem za pomocą mieszanej liczb 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, 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());
    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 określa, że jest to problem z maksymalizacją. (Podstawową metodą C++ jest SetMaximization.
  • Wywołaj rozwiązanie i wyświetl wyniki.
    solver.Solve();
Console.WriteLine("Solution:");
Console.WriteLine("Objective value = " + solver.Objective().Value());
Console.WriteLine("x = " + x.SolutionValue());
Console.WriteLine("y = " + y.SolutionValue());

Dokończ program

Pełny program znajdziesz poniżej.

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

Uruchamianie programu .Net

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

  1. Skopiuj i wklej powyższy kod do nowego pliku i zapisz go jako BasicExample.cs. w podkatalogu examples/dotnet katalogu, w którym zainstalowano Narzędzia OR.
  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, otwórz okno polecenia i wpisz:
    make run SOURCE=examples/dotnet/BasicExample.cs

Programy .Net można zapisywać i uruchamiać w katalogu innym niż examples/dotnet/, ale jest to nieco trudniejsze: trzeba zmodyfikować następujący wiersz pliku csproj:

../../../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 uruchamiania, wpisz:

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

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

Więcej przykładów witryn .Net

Więcej przykładów rozwiązania .Net, które ilustrują różne rodzaje problemów optymalizacyjnych, znajdziesz w przykładach.

Identyfikowanie typu problemu do rozwiązania

Istnieje wiele różnych rodzajów problemów z optymalizacją. W przypadku każdego typu problemu stosowane są inne metody i algorytmy pomagające znaleźć optymalne rozwiązanie.

Zanim zaczniesz pisać program, który pomoże Ci rozwiązać problem optymalizacyjny, musisz określić, z jakim typem problemu masz do czynienia, a następnie wybrać odpowiednie rozwiązanie – algorytm do znajdowania optymalnego rozwiązania.

Poniżej znajduje się krótki przegląd problemów, które rozwiązuje algorytm LUB narzędzia. Poniżej znajdziesz linki do sekcji, w których wyjaśniamy, jak rozwiązywać poszczególne problemy.

Optymalizacja liniowa

Jak pisaliśmy w poprzedniej sekcji, liniowy problem optymalizacji polega na tym, że funkcja celu i ograniczenia są wyrażeniami liniowymi w zmiennych.

Podstawowym rozwiązaniem w narzędziach z operatorem LUB w przypadku tego typu zadań jest liniowe rozwiązanie do optymalizacji, które w rzeczywistości jest kodem kilku różnych bibliotek do optymalizacji liniowej i mieszanych całkowite, w tym bibliotek zewnętrznych.

Więcej informacji o optymalizacji liniowej

Optymalizacja z użyciem liczby całkowitej (mieszane)

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 przypisaniami, w którym grupę instancji roboczych trzeba przypisać 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, lub 0 w innym przypadku. W tym przypadku zmienne mogą przyjąć tylko wartości 0 lub 1.

Więcej informacji o optymalizacji na podstawie liczb mieszanych

Optymalizacja ograniczeń

Optymalizacja ograniczeń (CP) wskazuje możliwe rozwiązania spośród bardzo dużej grupy potencjalnych problemów, które można modelować na podstawie dowolnych ograniczeń. Wskaźnik CP jest oparty na wykonalności (znajdowaniu możliwego rozwiązania), a nie na optymalizacji (znajdowaniu optymalnego rozwiązania), i skupia się na ograniczeniach i zmiennych, a nie na funkcji celu. Za pomocą CP można jednak rozwiązywać problemy optymalizacyjne, porównując wartości funkcji celu dla wszystkich możliwych rozwiązań.

Więcej informacji o optymalizacji ograniczeń

Projekt

Problemy z przypisaniami obejmują przypisanie grupy agentów (np. pracowników lub maszyn) do zbioru zadań, przy czym każdy agent ma stały koszt do wykonania określonego zadania. Problem polega na wskazaniu projektu o najniższym łącznym koszcie. Szczególnym wyjątkiem są problemy z przepływem sieci.

Więcej informacji o przypisywaniu

Pakowanie

Pakowanie bind polega na spakowaniu 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 Knapsack, który ma tylko jeden kontener.

Więcej informacji o pakowaniu pojemników

Planuję

Problemy z planowaniem obejmują przypisywanie zasobów do wykonywania zestawu zadań w określonym czasie. Ważnym przykładem jest problem ze sklepem 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 z nich 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 przedziale czasu.

Więcej informacji o planowaniu

Routing

Problemy z wyznaczaniem tras obejmują znajdowanie optymalnych tras dla floty pojazdów, które mają przemierzyć sieć, określone za pomocą wykresu skierowanego. Przykładem problemu z wyznaczaniem tras jest przydzielenie paczek do ciężarówek dostawczych, opisany w sekcji Co to jest problem z optymalizacją?. Inny problem to problem podróżujących sprzedawców.

Więcej informacji o routingu

Przepływy w sieci

Wiele problemów z optymalizacją można przedstawić za pomocą grafu skierowanego składającego się z węzłów i łuków 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 dystrybucji.

W przypadku zadania 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ść transportowanych towarów była jak największa.

Więcej informacji o przepływach w sieci