Premiers pas avec OR-Tools pour .Net

Les sections suivantes vous aideront à faire vos premiers pas avec OR-Tools pour .Net:

• Qu'est-ce qu'un problème d'optimisation ?
• Résoudre un problème d'optimisation dans .Net
• Autres exemples .Net
• Identifier le type de problème que vous souhaitez résoudre

Qu'est-ce qu'un problème d'optimisation ?

L'objectif de l'optimisation est de trouver la meilleure solution à un problème parmi un grand nombre de solutions possibles. (Parfois, vous serez satisfait de trouver une solution réalisable ; les outils OU peuvent également le faire.)

Voici un problème d'optimisation classique. Supposons qu’une société de livraison livre des colis à ses clients à l’aide d’une flotte de camions. Chaque jour, l'entreprise doit attribuer des colis à des camions, puis choisir un itinéraire pour chacun d'eux. Chaque attribution de colis et d'itinéraire possible a un coût, basé sur la distance totale de transport des camions et éventuellement sur d'autres facteurs. Le problème consiste à choisir les attributions de packages et d'itinéraires qui génèrent le moins de coûts.

Comme tous les problèmes d'optimisation, ce problème comporte les éléments suivants:

• L'objectif, c'est-à-dire la quantité que vous souhaitez optimiser. Dans l'exemple ci-dessus, l'objectif est de minimiser les coûts. Pour définir un problème d'optimisation, vous devez définir une fonction qui calcule la valeur de l'objectif pour toute solution possible. C'est ce qu'on appelle la fonction d'objectif. Dans l'exemple précédent, la fonction d'objectif calcule le coût total de toute attribution de packages et de routes.

  Une solution optimale est une solution pour laquelle la valeur de la fonction objectif est la meilleure. ("Excellentes" peut être une valeur maximale ou minimale.)

• Les contraintes : restrictions sur l'ensemble des solutions possibles, en fonction des exigences spécifiques du problème. Par exemple, si la compagnie de transport ne peut pas attribuer de colis dont le poids est supérieur à un poids donné aux camions, cela imposera une contrainte sur les solutions.

  Une solution faisable satisfait à toutes les contraintes données du problème, sans nécessairement être optimale.

Pour résoudre un problème d'optimisation, la première étape consiste à identifier l'objectif et les contraintes.

Résoudre un problème d'optimisation dans .Net

Nous allons ensuite donner un exemple de problème d'optimisation, et montrer comment le configurer et le résoudre dans .Net.

Exemple d'optimisation linéaire

L'un des domaines d'optimisation les plus anciens et les plus utilisés est l'optimisation linéaire (ou programmation linéaire), dans laquelle la fonction objectif et les contraintes peuvent être écrites sous forme d'expressions linéaires. Voici un exemple simple de ce type de problème.

Maximisez la 3x + y sous réserve des contraintes suivantes:

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

Dans cet exemple, la fonction objectif est 3x + y. La fonction objectif et les contraintes sont données par des expressions linéaires, ce qui en fait un problème linéaire.

Principales étapes pour résoudre le problème

Pour chaque langage, les étapes de base pour configurer et résoudre un problème sont les mêmes:

1. Importer les bibliothèques requises
2. Déclarer le résolveur
3. Créez les variables,
4. Définir les contraintes,
5. Définissez la fonction objectif,
6. J'appelle le résolveur et
7. Affichez les résultats.

Programme .Net

Cette section présente un programme .Net qui configure et résout le problème.

Remarque :Le programme.Net complet et les étapes à suivre pour l'exécuter sont indiqués à la fin de la section.

Procédez comme suit :

• Importez les bibliothèques requises.

  using System;
  using Google.OrTools.LinearSolver;

• Déclarez le résolveur.

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

  MPSolver est un wrapper qui permet de résoudre tous les problèmes de programmation linéaire ou de programmation composée d'entiers mixtes.
• Créez les variables.

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

• Définissez les contraintes. Les deux premières contraintes, 0 &leq x ≤ 1 et 0 ≤ y ≤ 2, sont déjà définies par les définitions des variables. Le code suivant définit la contrainte 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());

  La méthode SetCoefficient définit les coefficients de x et y dans l'expression de la contrainte.
• Définissez la fonction objectif.

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

  La méthode setMaximization déclare qu'il s'agit d'un problème de maximisation. (La méthode C++ sous-jacente est SetMaximization.
• Appelez le résolveur et affichez les résultats.

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

Terminer le programme

Le programme complet est présenté ci-dessous.

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

Exécuter le programme .Net

Vous pouvez exécuter le programme ci-dessus comme suit:

1. Copiez et collez le code ci-dessus dans le nouveau fichier, puis enregistrez-le sous le nom BasicExample.cs. dans le sous-répertoire examples/dotnet du répertoire où vous avez installé OR-Tools.
2. Dans le même répertoire, créez un fichier nommé BasicExample.csproj et ajoutez le code suivant :

   <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. En haut du répertoire dans lequel vous avez installé OR-Tools, ouvrez une fenêtre de commande et saisissez :

   make run SOURCE=examples/dotnet/BasicExample.cs

Remarque :Vous devez exécuter les programmes .Net à partir du niveau supérieur du répertoire dans lequel vous avez installé OR-Tools.

Il est possible d'enregistrer et d'exécuter des programmes .Net dans un répertoire différent de celui de examples/dotnet/, mais cela est un peu plus délicat. En effet, vous devez modifier la ligne suivante du fichier csproj, présentée ci-dessus :

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

pour obtenir le bon chemin d'accès au répertoire packages.

La solution la plus simple consiste à placer vos programmes .Net dans le répertoire examples/dotnet/.

Le programme renvoie les valeurs de x et y qui maximisent la fonction objectif:

Solution:
x =  1.0
y =  1.0

Pour compiler simplement le programme sans l'exécuter, saisissez la commande suivante:

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

Si vous apportez des modifications au programme, vous devrez le recompiler comme indiqué ci-dessus.

Autres exemples .Net

Pour obtenir d'autres exemples .Net illustrant comment résoudre différents types de problèmes d'optimisation, consultez la section Exemples.

Identifier le type de problème que vous souhaitez résoudre

Il existe de nombreux types de problèmes d'optimisation différents dans le monde. Pour chaque type de problème, il existe différentes approches et algorithmes pour trouver une solution optimale.

Avant de pouvoir commencer à écrire un programme de résolution d'un problème d'optimisation, vous devez identifier le type de problème auquel vous êtes confronté, puis choisir un solvateur approprié, c'est-à-dire un algorithme permettant de trouver une solution optimale.

Vous trouverez ci-dessous un bref aperçu des types de problèmes résolus par l'outil OR-Tools, ainsi que des liens vers les sections de ce guide qui expliquent comment résoudre chaque type de problème.

• Optimisation linéaire
• Optimisation des contraintes
• Optimisation de nombres entiers mixtes
• Devoir
• Planification
• Emballage
• Routage
• Flux réseau

Optimisation linéaire

Comme vous l'avez appris dans la section précédente, un problème d'optimisation linéaire est un problème dans lequel la fonction objectif et les contraintes sont des expressions linéaires dans les variables.

Pour ce type de problème, le principal résolveur dans les outils OU pour ce type de problème est le résolveur d'optimisation linéaire, qui est en réalité un wrapper pour plusieurs bibliothèques d'optimisation linéaire et d'optimisation d'entiers mixtes, y compris des bibliothèques tierces.

En savoir plus sur l'optimisation linéaire

Optimisation de nombres entiers mixtes

Un problème d'optimisation mixte des nombres entiers est un problème dans lequel certaines ou toutes les variables doivent être des entiers. C'est le cas, par exemple, du problème d'attribution dans lequel un groupe de nœuds de calcul doit être affecté à un ensemble de tâches. Pour chaque nœud de calcul et tâche, définissez une variable dont la valeur est 1 si le nœud de calcul donné est attribué à la tâche donnée, et 0 dans le cas contraire. Dans ce cas, les variables ne peuvent accepter que les valeurs 0 ou 1.

En savoir plus sur l'optimisation de nombres entiers mixtes

Optimisation des contraintes

L'optimisation des contraintes, ou programmation de contraintes (CP), identifie des solutions réalisables parmi un très grand nombre de candidats, où le problème peut être modélisé en fonction de contraintes arbitraires. Le CP est basé sur la faisabilité (trouver une solution réalisable) plutôt que sur l'optimisation (trouver une solution optimale), et se concentre sur les contraintes et les variables plutôt que sur la fonction objectif. Cependant, le CP peut être utilisé pour résoudre des problèmes d'optimisation, simplement en comparant les valeurs de la fonction objectif pour toutes les solutions possibles.

En savoir plus sur l'optimisation des contraintes

Assignment

Les problèmes d'attribution impliquent l'affectation d'un groupe d'agents (par exemple, des nœuds de calcul ou des machines) à un ensemble de tâches pour lequel l'attribution de chaque agent à une tâche spécifique a un coût fixe. Le problème consiste à trouver l'attribution dont le coût total est le plus faible. Les problèmes d'attribution sont en fait un cas particulier de problèmes de flux réseau.

En savoir plus sur l'attribution

Conditionnement

Le bin packing consiste à empaqueter un ensemble d'objets de différentes tailles dans des conteneurs de capacités différentes. L'objectif est d'empaqueter autant d'objets que possible, en fonction des capacités des conteneurs. Le problème Knapsack, qui ne comporte qu'un seul conteneur, est un cas particulier.

En savoir plus sur le bin packing

Planification

Les problèmes de planification impliquent l'affectation de ressources pour effectuer un ensemble de tâches à des heures spécifiques. Un exemple important est le problème lié à l'atelier, dans lequel plusieurs tâches sont traitées sur plusieurs machines. Chaque tâche consiste en une séquence de tâches, qui doivent être exécutées dans un ordre donné, et chaque tâche doit être traitée sur une machine spécifique. Le problème consiste à attribuer une planification afin que toutes les tâches soient terminées dans un intervalle de temps aussi court que possible.

En savoir plus sur la planification

Itinéraires

Les problèmes de calcul d'itinéraire consistent à trouver les meilleurs itinéraires pour qu'un parc de véhicules traverse un réseau, défini par un graphe orienté. Le problème d'attribution de colis aux camions de livraison, décrit dans la section Qu'est-ce qu'un problème d'optimisation ?, est un exemple de problème d'itinéraire. Le problème du vendeur en déplacement est un autre.

En savoir plus sur le routage

Flux réseau

De nombreux problèmes d'optimisation peuvent être représentés par un graphe orienté composé de nœuds et d'arcs dirigés entre eux. Par exemple, des problèmes de transport (lorsque des marchandises sont expédiées via un réseau ferroviaire) peuvent être représentés par un graphique dans lequel les arcs représentent des lignes ferroviaires et les nœuds sont des centres de distribution.

Dans le problème de flux maximal, chaque arc a une capacité maximale pouvant être transportée. Le problème consiste à affecter la quantité de marchandises à expédier selon chaque arc afin que la quantité totale transportée soit aussi importante que possible.

En savoir plus sur les flux réseau