Premiers pas avec OR-Tools pour C++

Les sections suivantes vous aideront à vous familiariser avec les outils OR avec C++:

• Qu'est-ce qu'un problème d'optimisation ?
• Résoudre un problème d'optimisation en C++
• Autres exemples C++
• 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 la recherche d'une solution réalisable ; les outils OU peuvent également le faire.)

Voici un problème d'optimisation typique. Supposons qu’une société de livraison livre des colis à ses clients par le biais d’une flotte de camions. Chaque jour, l'entreprise doit attribuer des colis à des camions, puis choisir un itinéraire pour chaque camion afin de livrer ses colis. Chaque attribution possible de colis et d'itinéraire a un coût basé sur la distance totale des camions et éventuellement d'autres facteurs. Le problème consiste à choisir les attributions de packages et d'itinéraires ayant le coût le plus faible.

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

• L'objectif, c'est-à-dire la quantité à 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 calculerait le coût total de toute attribution de packages et d'itinéraires.

  Une solution optimale est une solution pour laquelle la valeur de la fonction objectif est la plus élevée. ("Meilleure" 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 société de livraison ne peut pas attribuer aux camions des colis supérieurs à un poids donné, cela imposerait une contrainte aux solutions.

  Une solution faisable est une solution qui répond à toutes les contraintes données pour le 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 en C++

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

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 3x + y en tenant compte 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 fournies 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. Importez les bibliothèques requises.
2. Déclarer le résolveur
3. Créez les variables,
4. Définissez les contraintes,
5. Définissez la fonction objectif,
6. Appelez le résolveur et
7. Affichez les résultats.

Programme C++

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

Remarque :Le programme C++ complet et les étapes de l'exécution sont indiqués à la fin de la section.

Procédez comme suit :

• Importez les bibliothèques requises.

  #include <cstdlib>
  #include <memory>
  
  #include "absl/flags/flag.h"
  #include "absl/log/flags.h"
  #include "ortools/base/init_google.h"
  #include "ortools/base/logging.h"
  #include "ortools/init/init.h"
  #include "ortools/linear_solver/linear_solver.h"

• Déclarez le résolveur.

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  MPSolver est un wrapper permettant 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.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");
  
  LOG(INFO) << "Number of variables = " << solver->NumVariables();

• Définissez les contraintes. Les deux premières contraintes, 0 ≤ 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, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);
  
  LOG(INFO) << "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.
  MPObjective* const objective = solver->MutableObjective();
  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.
• Appelez le résolveur et affichez les résultats.

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();
  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }
  
  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

Terminer le programme

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

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

Exécuter le programme C++

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

1. Copiez et collez le code ci-dessus dans un nouveau fichier, puis enregistrez-le sous le nom program.cc.
2. Ouvrez une fenêtre de commande au premier niveau du répertoire dans lequel vous avez installé OR-Tools, puis saisissez

   make run SOURCE=relative/path/to/program.cc

   , où relative/path/to/ est le chemin d'accès au répertoire dans lequel vous avez enregistré le programme.

Remarque :Vous devez exécuter la commande ci-dessus à partir du niveau supérieur du répertoire dans lequel vous avez installé OR-Tools.

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

Solution:
x =  1.0
y =  1.0

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

make build SOURCE=relative/path/to/program.cc

Compiler en mode option

Pour compiler en mode O3:

make DEBUG='-O3' all

Exécuter l'exécutable C++

Lorsque vous compilez un programme C++ OR-Tools avec make, l'exécutable est créé dans le répertoire bin. Vous pouvez exécuter le fichier exécutable de l'exemple de programme comme suit:

cd bin && ./program

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

Autres exemples C++

Pour obtenir plus d'exemples C++ 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 différents pour trouver une solution optimale.

Avant de pouvoir commencer à écrire un programme permettant de résoudre un problème d'optimisation, vous devez identifier le type de problème auquel vous êtes confronté, puis choisir un résolveur 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 les outils OU, 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 mixte des nombres entiers
• 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 solution de l'outil OR-Tools est celui de l'optimisation linéaire. Il s'agit d'un wrapper pour plusieurs bibliothèques permettant d'optimiser des nombres linéaires et d'entiers mixtes, y compris des bibliothèques tierces.

En savoir plus sur l'optimisation linéaire

Optimisation de nombres entiers mixtes

Dans un problème d'optimisation mixte des entiers, certaines ou toutes les variables doivent être des entiers. Le problème d'attribution, par exemple, 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 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, la CP peut être utilisée pour résoudre des problèmes d'optimisation, simplement en comparant les valeurs de la fonction objectif pour toutes les solutions réalisables.

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, auquel cas l'attribution de chaque agent à une tâche spécifique a un coût fixe. Le problème est de 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 est un cas particulier, dans lequel il n'y a qu'un seul conteneur.

En savoir plus sur le bin packing

Planification

Les problèmes de planification impliquent d'affecter des ressources pour effectuer un ensemble de tâches à des heures spécifiques. Le problème du magasin d'emploi est un exemple important, 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 laps de temps aussi court que possible.

En savoir plus sur la planification

Routage

Les problèmes de routage consistent à trouver les itinéraires optimaux 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. Un autre problème concerne les commerciaux en déplacement.

En savoir plus sur le routage

Flux réseau

De nombreux problèmes d'optimisation peuvent être représentés par un graphe orienté constitué de nœuds et d'arcs dirigés entre eux. Par exemple, des problèmes de transport (dans lesquels des marchandises sont acheminées via un réseau ferroviaire) peuvent être représentés par un graphe 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 est d'affecter la quantité de marchandises à expédier sur chaque arc afin que la quantité totale transportée soit aussi élevée que possible.

En savoir plus sur les flux réseau