• Ganzzahloptimierung

Lineare Optimierungsprobleme, bei denen einige Variablen Ganzzahlen sein müssen, werden als Mixed Integer Programs (MIPs) bezeichnet.

Diese Variablen können auf verschiedene Arten auftreten:

  • Ganzzahlvariablen, die die Anzahl von Artikeln wie Autos oder Fernsehgeräten darstellen. Die Aufgabe besteht darin zu entscheiden, wie viele der einzelnen Artikel hergestellt werden sollen, um den Gewinn zu maximieren.
    In der Regel können solche Probleme als standardmäßige lineare Optimierungsprobleme eingerichtet werden, wobei die zusätzlichen Anforderungen erfüllt sein müssen, dass die Variablen Ganzzahlen sein müssen. Im nächsten Abschnitt wird ein Beispiel für diese Art von Problem gezeigt.

  • Boolesche Variablen, die Entscheidungen mit 0–1-Werten darstellen.
    Nehmen wir als Beispiel ein Problem, bei dem Worker Aufgaben zugewiesen werden (siehe Zuweisung). Für diese Art von Problem können Sie die booleschen Variablen xi,j definieren, die gleich 1 sind, wenn der Worker i der Aufgabe j zugewiesen ist, andernfalls mit 0.

Als Einstieg in die Optimierung von Ganzzahlen empfehlen wir das Cookbook zur Modellierung von Mosek.

Tools

Google bietet mehrere Möglichkeiten zur Lösung von MIP-Problemen:

  • MPSolver: Ein Wrapper für mehrere MIP-Resolver von Drittanbietern, die Standard-Branch-and-Bound-Techniken verwenden.
  • CP-SAT-Resolver: Ein Einschränkungsprogrammierungsprogramm, der SAT-Methoden (Erfüllbarkeit) verwendet.
  • Ursprünglicher CP Solver: Ein Einschränkungs-Programmier-Löser.

Welchen Matherechner sollte ich verwenden?

Es gibt keine unverzichtbare Regel für die Entscheidung, ob ein MIP-Resolver oder der CP-SAT-Resolver verwendet wird. Zur groben Orientierung:

  • MIP-Belöser eignen sich besser für Probleme, die als Standard-LP eingerichtet werden können, jedoch mit beliebigen Ganzzahlvariablen wie im ersten Beispiel oben eingerichtet werden können.
  • Der CP-SAT-Beheber eignet sich besser für Probleme, bei denen die meisten Variablen boolesch sind, wie im zweiten Beispiel oben.

Bei typischen MIPs, die sowohl ganzzahlige als auch boolesche Variablen haben, gibt es oft keinen deutlichen Unterschied in der Geschwindigkeit zwischen den beiden Solvern, sodass Ihre Wahl von Ihrer persönlichen Präferenz hängt.

Beispiele, die sowohl den MIP- als auch den CP-SAT-Belöser verwenden, finden Sie unter Zuweisungsproblem lösen und in den anderen Zuweisungsabschnitten.

Eine weitere Möglichkeit zum Lösen von Ganzzahlen-Programmierproblemen ist die Verwendung eines Netzwerkfluss-Resolvers.
Ein Beispiel finden Sie unter Zuweisung als Problem mit min. Kostenfluss.
Bei einem Problem, das als Netzwerkfluss eingerichtet werden kann, kann die Min.-Cost-Flow-Lösung schneller sein als der MIP- oder CP-SAT-Belöser. Allerdings können nicht alle MIPs auf diese Weise eingerichtet werden.