Erste Schritte mit OR-Tools für C++

In den folgenden Abschnitten wird der Einstieg in die Tools OR-Tools mit C++ beschrieben:

• Was ist ein Optimierungsproblem?
• Optimierungsproblem in C++ lösen
• Weitere C++-Beispiele
• Die Art des zu lösenden Problems identifizieren

Was ist ein Optimierungsproblem?

Das Ziel der Optimierung besteht darin, aus einer Vielzahl möglicher Lösungen die beste Lösung für ein Problem zu finden. (Manchmal sind Sie damit zufrieden, jede praktikable Lösung zu finden. Das ist auch mit OR-Tools möglich.)

Hier ist ein typisches Optimierungsproblem. Angenommen, ein Versandunternehmen liefert Pakete mit einer LKW-Fuhrpark an seine Kunden. Das Unternehmen muss täglich LKWs Pakete zuweisen und dann für jeden LKW eine Route für die Zustellung der Pakete auswählen. Für jede mögliche Zuweisung von Paketen und Routen fallen Kosten an, die auf der Gesamtstrecke für die LKWs und eventuell auch auf anderen Faktoren basieren. Das Problem besteht darin, die Zuweisungen von Paketen und Routen mit den geringsten Kosten auszuwählen.

Wie alle Optimierungsprobleme weist dieses Problem folgende Elemente auf:

• Das Ziel: die Menge, die Sie optimieren möchten Im obigen Beispiel besteht das Ziel darin, Kosten zu minimieren. Zum Einrichten eines Optimierungsproblems müssen Sie eine Funktion definieren, die den Wert des Ziels für jede mögliche Lösung berechnet. Dies wird als Zielfunktion bezeichnet. Im vorherigen Beispiel würde die Zielfunktion die Gesamtkosten für eine Zuweisung von Paketen und Routen berechnen.

  Eine optimale Lösung ist eine Lösung, für die der Wert der Zielfunktion am besten ist. „Am besten“ kann entweder ein Höchstwert oder ein Minimum sein.

• Einschränkungen: Einschränkungen für die Anzahl möglicher Lösungen basierend auf den spezifischen Anforderungen des Problems. Wenn das Versandunternehmen beispielsweise keine Pakete mit einem bestimmten Gewicht LKWs zuweisen kann, würde dies eine Einschränkung der Lösungen darstellen.

  Eine praktische Lösung ist eine Lösung, die alle gegebenen Einschränkungen für das Problem erfüllt, aber nicht unbedingt optimal ist.

Der erste Schritt zur Lösung eines Optimierungsproblems besteht darin, das Ziel und die Einschränkungen zu identifizieren.

Ein Optimierungsproblem in C++ lösen

Als Nächstes geben wir ein Beispiel für ein Optimierungsproblem und zeigen, wie es in C++ eingerichtet und gelöst wird.

Beispiel für eine lineare Optimierung

Einer der ältesten und am häufigsten verwendeten Optimierungsbereiche ist die lineare Optimierung (oder lineare Programmierung), bei der die Zielfunktion und die Einschränkungen als lineare Ausdrücke geschrieben werden können. Hier ist ein einfaches Beispiel für diese Art von Problem.

3x + y unterliegt den folgenden Einschränkungen:

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

Die Zielfunktion in diesem Beispiel ist 3x + y. Sowohl die Zielfunktion als auch die Einschränkungen werden durch lineare Ausdrücke vorgegeben, was dies zu einem linearen Problem macht.

Hauptschritte zur Lösung des Problems

Die grundlegenden Schritte zum Einrichten und Lösen eines Problems sind für jede Sprache gleich:

1. Importieren Sie die erforderlichen Bibliotheken,
2. Deklariere den Solver,
3. Erstellen Sie die Variablen,
4. Definieren Sie die Einschränkungen,
5. Definieren Sie die Zielfunktion,
6. Rufen Sie den Solver auf und
7. Zeige die Ergebnisse an.

C++-Programm

In diesem Abschnitt wird ein C++-Programm beschrieben, das das Problem einrichtet und löst.

Hinweis: Das vollständige C++-Programm und die Schritte zum Ausführen finden Sie am Ende des Abschnitts.

Und so gehts:

• Importieren Sie die erforderlichen Bibliotheken.

  #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"

• Deklariere den Solver.

  // 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 ist ein Wrapper zum Lösen von Problemen mit linearer Programmierung oder Mixed Integer-Programmierung.
• Erstellen Sie die Variablen.

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

• Definieren Sie die Einschränkungen. Die ersten beiden Einschränkungen, 0 ≤ x ≤ 1 und 0 ≤ y ≤ 2, wurden bereits durch die Definitionen der Variablen festgelegt. Der folgende Code definiert die Einschränkung 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();

  Die Methode SetCoefficient legt die Koeffizienten von x und y im Ausdruck für die Einschränkung fest.
• Definieren Sie die Zielfunktion.

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

  Die Methode SetMaximization deklariert dies als ein Maximierungsproblem.
• Rufen Sie den Solver auf und zeigen Sie die Ergebnisse an.

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

Programm abschließen

Das vollständige Programm wird unten angezeigt.

// 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;
}

C++-Programm ausführen

Sie können das obige Programm wie folgt ausführen:

1. Kopieren Sie den obigen Code, fügen Sie ihn in eine neue Datei ein und speichern Sie ihn als program.cc.
2. Öffnen Sie auf der obersten Ebene des Verzeichnisses, in dem Sie OR-Tools installiert haben, ein Befehlsfenster und geben Sie

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

   ein, wobei relative/path/to/ der Pfad zu dem Verzeichnis ist, in dem Sie das Programm gespeichert haben.

Hinweis: Sie müssen den obigen Befehl auf der obersten Ebene des Verzeichnisses ausführen, in dem Sie OR-Tools installiert haben.

Das Programm gibt die Werte von x und y zurück, mit denen die Zielfunktion maximiert wird:

Solution:
x =  1.0
y =  1.0

Wenn Sie das Programm nur kompilieren möchten, ohne es auszuführen, geben Sie Folgendes ein:

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

Kompilierung im Opt-Modus

So kompilieren Sie im O3-Modus:

make DEBUG='-O3' all

Ausführbare C++-Datei ausführen

Wenn Sie ein OR-Tools-C++-Programm mit make kompilieren, wird die ausführbare Datei im Verzeichnis bin erstellt. Sie können die ausführbare Datei für das Beispielprogramm so ausführen:

cd bin && ./program

Wenn Sie Änderungen am Programm vornehmen, müssen Sie es wie oben gezeigt neu kompilieren.

Weitere C++-Beispiele

Weitere C++-Beispiele, die zeigen, wie sich verschiedene Arten von Optimierungsproblemen lösen lassen, finden Sie unter Beispiele.

Die Art des zu lösenden Problems identifizieren

Es gibt auf der Welt viele verschiedene Arten von Optimierungsproblemen. Für jede Art von Problem gibt es unterschiedliche Ansätze und Algorithmen, um eine optimale Lösung zu finden.

Bevor Sie mit dem Schreiben eines Programms zur Lösung eines Optimierungsproblems beginnen können, müssen Sie ermitteln, mit welcher Art von Problem Sie es zu tun haben, und dann einen geeigneten Resolver auswählen – einen Algorithmus zur Suche nach einer optimalen Lösung.

Nachfolgend finden Sie eine kurze Übersicht über die Arten von Problemen, die mit ODER-Tools gelöst werden können. Außerdem finden Sie Links zu den Abschnitten in diesem Leitfaden, in denen erklärt wird, wie die einzelnen Problemtypen gelöst werden können.

• Lineare Optimierung
• Optimierung der Einschränkung
• Gemischte Ganzzahloptimierung
• Zuweisung
• Planung
• Verpackung
• E-Mail-Routing
• Netzwerkflüsse

Lineare Optimierung

Wie Sie im vorherigen Abschnitt gelernt haben, besteht ein lineares Optimierungsproblem darin, dass die Zielfunktion und die Einschränkungen lineare Ausdrücke in den Variablen sind.

Der primäre Löse in OR-Tools für diese Art von Problem ist der Lösungslöser für lineare Optimierung, der tatsächlich ein Wrapper für mehrere verschiedene Bibliotheken für die lineare und gemischte Ganzzahl-Optimierung ist, einschließlich Bibliotheken von Drittanbietern.

Weitere Informationen zur linearen Optimierung

Gemischte Ganzzahloptimierung

Ein Problem mit der Optimierung von gemischten Ganzzahlen liegt vor, wenn einige oder alle Variablen Ganzzahlen sein müssen. Ein Beispiel hierfür ist das Zuweisungsproblem, bei dem eine Gruppe von Mitarbeitern einer Reihe von Aufgaben zugewiesen werden muss. Für jeden Worker und jede Aufgabe definieren Sie eine Variable, deren Wert 1 ist, wenn der jeweilige Worker der angegebenen Aufgabe zugewiesen ist, und andernfalls 0. In diesem Fall können die Variablen nur die Werte 0 oder 1 annehmen.

Weitere Informationen zur gemischten Ganzzahl-Optimierung

Einschränkungsoptimierung

Die Einschränkungsoptimierung oder Constraint Programming (CP) identifiziert aus einer sehr großen Anzahl von Kandidaten machbare Lösungen, bei denen das Problem in Bezug auf beliebige Einschränkungen modelliert werden kann. CP basiert auf Machbarkeit (Finden einer durchführbaren Lösung) und nicht auf Optimierung (Finden einer optimalen Lösung) und konzentriert sich auf die Einschränkungen und Variablen anstatt auf die objektive Funktion. Mit CP lassen sich jedoch Optimierungsprobleme lösen, indem Sie einfach die Werte der Zielfunktion für alle möglichen Lösungen vergleichen.

Weitere Informationen zur Einschränkungsoptimierung

Assignment

Bei Zuweisungsproblemen wird einer Gruppe von Agenten (z. B. Workern oder Maschinen) eine Gruppe von Aufgaben zugewiesen. Für die Zuweisung der einzelnen Agents zu einer bestimmten Aufgabe fallen feste Kosten an. Das Problem besteht darin, die Zuweisung mit den geringsten Gesamtkosten zu finden. Zuweisungsprobleme sind eigentlich ein Sonderfall von Netzwerkflussproblemen.

Weitere Informationen zu Zuweisungen

Einpacken

Beim Bin-Packen wird eine Reihe von Objekten unterschiedlicher Größe in Container mit unterschiedlichen Kapazitäten gepackt. Das Ziel besteht darin, je nach Kapazität der Container so viele Objekte wie möglich zu verpacken. Ein Sonderfall ist das Knapsack-Problem, bei dem es nur einen Container gibt.

Weitere Informationen zum Bin-Packing

Wird geplant

Bei Planungsproblemen werden Ressourcen zugewiesen, um eine Reihe von Aufgaben zu bestimmten Zeiten auszuführen. Ein wichtiges Beispiel ist das Jobgeschäftsproblem, bei dem mehrere Jobs auf mehreren Maschinen verarbeitet werden. Jeder Job besteht aus einer Abfolge von Aufgaben, die in einer bestimmten Reihenfolge ausgeführt werden müssen, wobei jede Aufgabe auf einer bestimmten Maschine verarbeitet werden muss. Das Problem besteht darin, einen Zeitplan zuzuweisen, damit alle Jobs in so kurzer Zeit wie möglich abgeschlossen werden.

Weitere Informationen zur Terminplanung

Routing

Routing-Probleme beinhalten die Suche nach den optimalen Routen für eine Fahrzeugflotte, die ein Netzwerk durchqueren kann, definiert durch einen gerichteten Graph. Das unter Was ist ein Optimierungsproblem? beschriebene Problem beim Zuweisen von Paketen zu Lieferwagen ist ein Beispiel für ein Routingproblem. Ein weiteres Problem ist das Problem der reisenden Verkäufer.

Weitere Informationen zum Routing

Netzwerkflüsse

Viele Optimierungsprobleme können durch einen gerichteten Graphen dargestellt werden, der aus Knoten und gerichteten Bögen dazwischen besteht. Beispielsweise können Transportprobleme, bei denen Waren über ein Bahnnetz transportiert werden, durch ein Diagramm dargestellt werden, in dem die Bögen Bahnlinien und die Knoten Verteilungszentren sind.

Beim Problem mit dem maximalen Fluss hat jeder Bogen eine maximale Kapazität, die über ihn transportiert werden kann. Das Problem besteht darin, die zu versendende Warenmenge über jeden Bogen so festzulegen, dass die insgesamt zu transportierende Menge so groß wie möglich ist.

Weitere Informationen zu Netzwerkflüssen