#!/usr/bin/env python3 # CP_SAT_Statusfaelle.py """ Kapitel CP-SAT: Alle fuenf Antworten von CP-SAT - und was jede bedeutet. Der haeufigste Fehler beim Einsatz von CP-SAT im Betrieb ist eine Zeile wie if status == cp_model.OPTIMAL: ...verwerte die Loesung... Sie wirft in drei von fuenf Faellen etwas weg, das man haette gebrauchen koennen, und verschweigt in einem weiteren Fall einen Modellierungsfehler. Dieses Programm erzeugt jeden Statusfall absichtlich und zeigt die passende Reaktion: OPTIMAL beweisbar bestmoeglich -> ausfuehren FEASIBLE zulaessig, Zeit war um -> Gap pruefen, dann entscheiden INFEASIBLE kein Plan existiert -> harte Regeln lockern MODEL_INVALID das Modell ist fehlerhaft -> Programmierfehler beheben UNKNOWN nichts gefunden, Zeit war um -> mehr Zeit oder Heuristik Benoetigt: numpy, ortools """ from __future__ import annotations from dataclasses import dataclass import numpy as np from ortools.sat.python import cp_model @dataclass class Auswertung: """Was nach einem CP-SAT-Lauf tatsaechlich feststeht.""" status: str hat_loesung: bool beweisbar_optimal: bool zielwert: float | None schranke: float | None gap: float | None empfehlung: str def werte_aus(loeser: cp_model.CpSolver, status: int, mit_zielfunktion: bool) -> Auswertung: """Uebersetzt einen CP-SAT-Status in eine Handlungsempfehlung. Genau diese Funktion fehlt in den meisten Projekten. Sie ist kurz, aber sie ist der Unterschied zwischen einem Prototyp und einem System, das nachts ohne Aufsicht laeuft. """ name = loeser.StatusName(status) hat_loesung = status in (cp_model.OPTIMAL, cp_model.FEASIBLE) zielwert = schranke = gap = None if hat_loesung and mit_zielfunktion: zielwert = loeser.ObjectiveValue() schranke = loeser.BestObjectiveBound() nenner = max(abs(zielwert), 1e-9) gap = abs(zielwert - schranke) / nenner if status == cp_model.OPTIMAL: empfehlung = "Ausfuehren. Besser geht es nachweislich nicht." elif status == cp_model.FEASIBLE: empfehlung = (f"Brauchbar. Der Plan ist hoechstens {gap * 100:.2f} % " f"schlechter als das theoretisch Bestmoegliche." if gap is not None else "Brauchbar, aber nicht als optimal bewiesen.") elif status == cp_model.INFEASIBLE: empfehlung = ("KEIN Plan existiert. Das ist eine Aussage ueber Ihre " "harten Regeln, nicht ueber die Rechenzeit: Auch " "unendlich viel Zeit wuerde nichts aendern. Regeln " "lockern oder weich machen (Anhang C).") elif status == cp_model.MODEL_INVALID: empfehlung = ("Das MODELL ist fehlerhaft, nicht das Problem. " "Typisch: eine Variable mit leerem Wertebereich. " "model.Validate() nennt die Ursache.") else: # UNKNOWN empfehlung = ("Nichts gefunden - aber auch nicht widerlegt. Mehr Zeit " "geben, das Modell vereinfachen oder mit einer " "Heuristik vorbelegen (AddHint).") return Auswertung( status=name, hat_loesung=hat_loesung, beweisbar_optimal=status == cp_model.OPTIMAL, zielwert=zielwert, schranke=schranke, gap=gap, empfehlung=empfehlung, ) def loese(baue, zeitlimit: float, mit_zielfunktion: bool) -> Auswertung: modell = cp_model.CpModel() baue(modell) loeser = cp_model.CpSolver() loeser.parameters.max_time_in_seconds = zeitlimit # Fuer reproduzierbare Buchausgaben; im Betrieb weglassen. loeser.parameters.num_workers = 1 loeser.parameters.random_seed = 1 status = loeser.Solve(modell) return werte_aus(loeser, status, mit_zielfunktion) # --- Die fuenf Faelle -------------------------------------------------------- def dienstplan_loesbar(modell: cp_model.CpModel) -> None: """Vier Personen, fuenf Dienste, hoechstens zwei je Person - loesbar.""" personen, dienste = 4, 5 x = [[modell.NewBoolVar(f"x_{i}_{j}") for j in range(dienste)] for i in range(personen)] for j in range(dienste): modell.AddExactlyOne(x[i][j] for i in range(personen)) for i in range(personen): modell.Add(sum(x[i]) <= 2) def dienstplan_unloesbar(modell: cp_model.CpModel) -> None: """Dieselben fuenf Dienste, aber hoechstens EIN Dienst je Person. Vier Personen koennen zusammen hoechstens vier Dienste uebernehmen - fuer fuenf Dienste reicht das nicht. Kein Solver der Welt findet hier etwas. """ personen, dienste = 4, 5 x = [[modell.NewBoolVar(f"x_{i}_{j}") for j in range(dienste)] for i in range(personen)] for j in range(dienste): modell.AddExactlyOne(x[i][j] for i in range(personen)) for i in range(personen): modell.Add(sum(x[i]) <= 1) def modell_fehlerhaft(modell: cp_model.CpModel) -> None: """Eine Variable mit leerem Wertebereich: untere Schranke > obere. Im Alltag entsteht das durch einen Rechenfehler in den Grenzen, etwa NewIntVar(mindestbesetzung, kapazitaet, ...) bei falsch sortierten Daten. """ kaputt = modell.NewIntVar(5, 2, "leerer_bereich") modell.Add(kaputt >= 0) def lastverteilung(modell: cp_model.CpModel) -> None: """120 Auftraege auf 11 Maschinen - gross genug, dass der Optimalitaets- beweis laenger dauert als das Finden einer sehr guten Loesung.""" rng = np.random.default_rng(3) dauer = rng.integers(100, 9000, 120) n, maschinen = len(dauer), 11 obergrenze = int(dauer.sum()) x = [[modell.NewBoolVar(f"x_{i}_{k}") for k in range(maschinen)] for i in range(n)] for i in range(n): modell.AddExactlyOne(x[i]) belegung = [modell.NewIntVar(0, obergrenze, f"l_{k}") for k in range(maschinen)] for k in range(maschinen): modell.Add(belegung[k] == sum(int(dauer[i]) * x[i][k] for i in range(n))) makespan = modell.NewIntVar(0, obergrenze, "makespan") modell.AddMaxEquality(makespan, belegung) modell.Minimize(makespan) def zahlpartition(modell: cp_model.CpModel) -> None: """46 grosse Zahlen exakt in zwei gleich schwere Haelften teilen. Ein beruehmt schweres Problem: Es gibt keine Zielfunktion, entweder es geht auf oder nicht - und beides zu entscheiden dauert lange. """ rng = np.random.default_rng(1) gewichte = rng.integers(10**6, 2 * 10**6, 46) x = [modell.NewBoolVar(f"x_{i}") for i in range(len(gewichte))] modell.Add(sum(int(gewichte[i]) * x[i] for i in range(len(gewichte))) == int(gewichte.sum() // 2)) def zeige(titel: str, a: Auswertung) -> None: print(f"\n{titel}") print(f" Status {a.status}") print(f" Loesung vorhanden {'ja' if a.hat_loesung else 'nein'}") if a.zielwert is not None: print(f" Zielwert / Schranke {a.zielwert:,.0f} / {a.schranke:,.0f}" f" (Gap {a.gap * 100:.3f} %)") print(f" -> {a.empfehlung}") if __name__ == "__main__": print("=" * 78) print(" DIE FUENF ANTWORTEN VON CP-SAT") print("=" * 78) zeige("[1] Dienstplan, hoechstens 2 Dienste je Person", loese(dienstplan_loesbar, 10.0, mit_zielfunktion=False)) zeige("[2] Lastverteilung 120 Auftraege / 11 Maschinen, 0,5 s Limit", loese(lastverteilung, 0.5, mit_zielfunktion=True)) zeige("[3] Derselbe Fall mit 10 s Limit", loese(lastverteilung, 10.0, mit_zielfunktion=True)) zeige("[4] Dienstplan, hoechstens 1 Dienst je Person", loese(dienstplan_unloesbar, 10.0, mit_zielfunktion=False)) zeige("[5] Variable mit leerem Wertebereich", loese(modell_fehlerhaft, 10.0, mit_zielfunktion=False)) zeige("[6] Zahlpartition mit 46 grossen Zahlen, 2 s Limit", loese(zahlpartition, 2.0, mit_zielfunktion=False)) print("\n" + "=" * 78) print(" DIE DREI, DIE MAN NICHT VERWECHSELN DARF") print("=" * 78) print("INFEASIBLE Es gibt keine Loesung. Eine Aussage ueber Ihr MODELL.") print(" Mehr Rechenzeit aendert daran nichts.") print("UNKNOWN Es wurde keine gefunden. Eine Aussage ueber die ZEIT.") print(" Ob es eine gibt, ist offen.") print("MODEL_INVALID Das Modell ist gar kein gueltiges Modell. Eine") print(" Aussage ueber Ihren CODE - immer ein Programmierfehler.") print() print("Wer diese drei in einem 'else: return None' zusammenfasst, verliert") print("genau die Information, die zur Fehlersuche noetig waere.") print("=" * 78)