Erste Schritte mit OR-Tools für Java

Die folgenden Abschnitte enthalten eine Einführung in OR-Tools für Java:

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 mit der Suche nach einer praktikablen Lösung zufrieden. Mit OR-Tools ist das auch möglich.)

Hier 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 auswählen, auf der die Pakete zugestellt werden. Für jede mögliche Zuweisung von Paketen und Routen fallen Kosten an, die auf der Gesamtreisestrecke der Lkw und möglicherweise auch auf anderen Faktoren basieren. Das Problem besteht darin, die Zuweisungen der Pakete und Routen mit den geringsten Kosten auszuwählen.

Wie alle Optimierungsprobleme weist auch dieses Problem folgende Elemente auf:

  • Das Ziel: die Menge, die Sie optimieren möchten Im obigen Beispiel besteht das Ziel darin, die 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 Objective-Funktion die Gesamtkosten aller 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öchst- oder Mindestwert sein.

  • Die 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 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.

Optimierungsproblem in Java lösen

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

Beispiel für eine lineare Optimierung

Einer der ältesten und am weitesten verbreiteten Bereiche der Optimierung 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.

Die 3x + y-Maximierung 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 Matherechner,
  3. Erstellen Sie die Variablen,
  4. Definieren Sie die Einschränkungen,
  5. Definieren Sie die Zielfunktion,
  6. Rufen Sie den Solver auf und
  7. Zeigen Sie die Ergebnisse an.

Java-Programm

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

Und so gehts:

  • Importieren Sie die erforderlichen Bibliotheken. 
    import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
  • Deklariere den Matherechner. 
    // Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
    MPSolver ist ein Wrapper zum Lösen von Problemen mit der linearen Programmierung oder der Programmierung von gemischten Ganzzahlen.
  • Erstellen Sie die Variablen. 
    // Create the variables x and y.
MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

System.out.println("Number of variables = " + solver.numVariables());
  • Definieren Sie die Einschränkungen. Die ersten beiden Einschränkungen, 0 ≤ x ≤ 1 und 0 ≤ y ≤ 2, werden bereits durch die Definitionen der Variablen festgelegt. Der folgende Code definiert die Einschränkung x + y ≤ 2: 
    // Create a linear constraint, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);

System.out.println("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 objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 1);
objective.setMaximization();
    Mit der Methode setMaximization wird dies als Maximierungsproblem deklariert.
  • Rufen Sie den Solver auf und zeigen Sie die Ergebnisse an. 
    solver.solve();
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());

Programm abschließen

Das vollständige Programm sehen Sie unten.

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    solver.solve();

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());
  }

  private BasicExample() {}
}

Java-Programm ausführen

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

  1. Kopieren Sie den obigen Code, fügen Sie ihn in die neue Datei ein und speichern Sie ihn als my_program.java.
  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/my_program.java
    ein, wobei relative/path/to/ der Pfad zu dem Verzeichnis ist, in dem Sie das Programm gespeichert 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/my_program.java

Weitere Java-Beispiele

Weitere Java-Beispiele, die veranschaulichen, wie sich verschiedene Arten von Optimierungsproblemen lösen lassen, finden Sie unter Beispiele.

Den Typ des Problems identifizieren, den Sie lösen möchten

Es gibt weltweit viele verschiedene Arten von Optimierungsproblemen. Für jede Art von Problem gibt es verschiedene 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 einen kurzen Überblick über die Arten von Problemen, die mit OR-Tools gelöst werden, sowie Links zu den Abschnitten in diesem Leitfaden, in denen erklärt wird, wie Sie die einzelnen Problemtypen lösen können.

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 Solver in OR-Tools für diese Art von Problem ist der lineare Optimierungslöser, der in Wirklichkeit ein Wrapper für mehrere verschiedene Bibliotheken für die lineare und gemischte Ganzzahloptimierung 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 ist das Zuweisungsproblem, bei dem eine Gruppe von Workern 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, andernfalls 0. In diesem Fall können die Variablen nur die Werte 0 oder 1 annehmen.

Weitere Informationen zur Optimierung mit gemischten Ganzzahlen

Einschränkungsoptimierung

Mit der Einschränkungsoptimierung oder Einschränkungsprogrammierung (Constraint Programming, CP) werden aus einer sehr großen Anzahl von Kandidaten realisierbare Lösungen identifiziert, bei denen das Problem in Bezug auf willkürliche 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 anstelle der Zielfunktion. CP kann jedoch verwendet werden, um Optimierungsprobleme zu lösen, indem einfach die Werte der Zielfunktion für alle möglichen Lösungen verglichen werden.

Weitere Informationen zur Einschränkungsoptimierung

Assignment

Bei Zuweisungsproblemen wird eine Gruppe von Agents (z. B. Worker oder Maschinen) einer Reihe von Aufgaben zugewiesen. Dabei fallen feste Kosten dafür an, dass jeder Agent einer bestimmten Aufgabe zugewiesen wird. 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 Packing wird eine Reihe von Objekten unterschiedlicher Größe in Container mit unterschiedlichen Kapazitäten verpackt. Das Ziel besteht darin, so viele Objekte wie möglich zu packen, abhängig von den Kapazitäten der Container. 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 Jobshop-Problem, bei dem mehrere Jobs auf mehreren Rechnern verarbeitet werden. Jeder Job besteht aus einer Abfolge von Aufgaben, die in einer bestimmten Reihenfolge und auf einer bestimmten Maschine ausgeführt werden müssen. Das Problem besteht darin, einen Zeitplan zuzuweisen, damit alle Jobs in so kurzer Zeit wie möglich abgeschlossen werden.

Weitere Informationen zur Terminplanung

Routen

Bei Routenproblemen werden die optimalen Routen für eine Fahrzeugflotte ermittelt, um ein Netzwerk zu durchqueren. Diese werden durch einen gerichteten Graphen definiert. Das unter Was ist ein Optimierungsproblem? beschriebene Problem der Zuweisung von Paketen zu Lieferwagen ist ein Beispiel für ein Routingproblem. Ein weiteres Problem ist das Problem der Vertriebsmitarbeiter auf Reisen.

Weitere Informationen zum Routing

Netzwerkflüsse

Viele Optimierungsprobleme können durch einen gerichteten Graphen dargestellt werden, der aus Knoten und gerichteten Bögen zwischen ihnen besteht. Beispielsweise können Transportprobleme, bei denen Waren über ein Bahnnetz versendet werden, durch eine Grafik dargestellt werden, in der 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 Menge der zu versendenden Waren über jeden Bogen so festzulegen, dass die Gesamtmenge für den Transport so groß wie möglich ist.

Weitere Informationen zu Netzwerkflüssen