Kapitel 10: Spaltengenerierung — das Modell umbauen statt die Lösung raten

#!/usr/bin/env python3

# Spaltengenerierung.py
"""
Kapitel Dekomposition: Das Modell umbauen, statt die Loesung zu raten.

Eine Papierfabrik liefert Rollen von 5.600 mm Breite. Die Kunden bestellen
schmalere Breiten, und aus jeder Mutterrolle werden mehrere davon geschnitten.
Gesucht ist der Schnittplan, der mit den wenigsten Mutterrollen auskommt.

Der naheliegende Modellansatz - "welches Stueck kommt auf welche Rolle?" -
fuehrt in eine Sackgasse: Er braucht eine Binaervariable je Stueck-und-Rolle,
und weil alle Rollen gleich sind, ist er hochgradig symmetrisch. Der Solver
probiert dieselbe Loesung in tausend Umbenennungen durch.

Die Spaltengenerierung dreht die Frage um:

    Nicht "welches Stueck auf welche Rolle",
    sondern "wie oft schneide ich welches MUSTER".

Damit verschwindet die Symmetrie - aber es entsteht ein neues Problem: Die Zahl
der moeglichen Muster waechst kombinatorisch. Man kann sie nicht aufschreiben.
Der Trick besteht darin, sie auch nicht aufzuschreiben, sondern nur die wenigen
zu erzeugen, die tatsaechlich gebraucht werden - und zwar mit Hilfe der
Schattenpreise aus dem Kapitel LP.

Das Programm zeigt vier Dinge:

  1. Die beiden Formulierungen desselben Problems und ihre Groesse.
  2. Wie schnell die Musterzahl waechst - und wie wenige davon genuegen.
  3. Die Schleife selbst: Master-LP, Dualwerte, Rucksack, neue Spalte.
  4. Wann sich der Aufwand lohnt und wann nicht. Die Antwort haengt an einer
     einzigen Kennzahl der Instanz, und sie erklaert nebenbei, warum eine
     Faustregel bei manchen Zuschnittproblemen schon optimal ist.

Benoetigt: numpy, scipy
"""

from __future__ import annotations

import numpy as np
from scipy.optimize import linprog

ROLLENBREITE = 5600

# Zwei Instanzen mit demselben Bedarf, aber verschiedenen Breiten. Der
# Unterschied ist die eine Kennzahl, um die es in Teil 4 geht.
BEDARF = [22, 25, 12, 14, 18, 18, 20, 10, 12, 14, 16, 18, 20]
BREIT = [1380, 1520, 1560, 1710, 1820, 1880, 1930, 2000, 2050, 2100, 2140,
         2150, 2200]
SCHMAL = [380, 520, 560, 710, 820, 880, 930, 1000, 1050, 1100, 1140,
          1150, 1200]


# --- Die Musterzahl ---------------------------------------------------------

def zaehle_muster(breiten, rollenbreite: int = ROLLENBREITE) -> int:
    """Wie viele zulaessige Schnittmuster gibt es ueberhaupt?

    Nur zum Zeigen - in einem produktiven Programm wuerde man das nie
    ausrechnen, weil die Zahl bei realistischen Instanzen jede Vorstellung
    sprengt. Genau das ist der Punkt.
    """
    speicher: dict[tuple[int, int], int] = {}

    def ab(i: int, rest: int) -> int:
        if i == len(breiten):
            return 1
        if (i, rest) in speicher:
            return speicher[(i, rest)]
        summe = sum(ab(i + 1, rest - anzahl * breiten[i])
                    for anzahl in range(rest // breiten[i] + 1))
        speicher[(i, rest)] = summe
        return summe

    return ab(0, rollenbreite)


# --- Die beiden Bausteine der Schleife --------------------------------------

def loese_master(muster, bedarf, ganzzahlig: bool = False):
    """Restringiertes Master: Wie oft schneide ich jedes bekannte Muster?

        min  sum_p x_p           unter   sum_p a_ip * x_p >= bedarf_i

    Als LP gerechnet liefert es zusaetzlich die DUALWERTE - und die sind der
    eigentliche Ertrag: Der Dualwert zu Breite i sagt, was ein zusaetzliches
    Stueck dieser Breite an Rollen kostet. Es ist derselbe Schattenpreis wie
    im Kapitel LP, nur dass er hier nicht berichtet, sondern weiterverarbeitet
    wird.
    """
    matrix = -np.array(muster, dtype=float).T        # >= wird zu <= mit Minus
    ergebnis = linprog(np.ones(len(muster)),
                       A_ub=matrix, b_ub=-np.array(bedarf, dtype=float),
                       bounds=(0, None),
                       integrality=(1 if ganzzahlig else 0), method="highs")
    if not ergebnis.success:
        raise SystemExit(f"Master nicht loesbar: {ergebnis.message}")
    dual = None if ganzzahlig else -ergebnis.ineqlin.marginals
    return ergebnis.fun, ergebnis.x, dual


def bestes_neues_muster(dual, breiten, rollenbreite: int = ROLLENBREITE):
    """Pricing: Gibt es ein Muster, das sich noch lohnt?

    Gesucht ist das Muster mit dem groessten Gesamtwert zu den aktuellen
    Schattenpreisen - unter der Bedingung, dass es in die Rolle passt. Das ist
    ein RUCKSACKPROBLEM (Kapitel MILP, Rucksack.py): Preise sind der Nutzen,
    Breiten das Gewicht, die Rollenbreite die Kapazitaet. Hier mit dynamischer
    Programmierung geloest, weil die Breiten ganzzahlig sind.

    Bei Gleichstand wird bewusst der KLEINSTE Index bevorzugt (>-Vergleich mit
    Toleranz statt >=). Sonst haengt das erzeugte Muster von der Reihenfolge
    der Gleitkommaoperationen ab, und das Programm liefert von Lauf zu Lauf
    verschiedene Ausgaben.
    """
    wert = np.zeros(rollenbreite + 1)
    herkunft = [-1] * (rollenbreite + 1)
    for platz in range(rollenbreite + 1):
        for i, breite in enumerate(breiten):
            if breite <= platz and wert[platz - breite] + dual[i] > wert[platz] + 1e-9:
                wert[platz] = wert[platz - breite] + dual[i]
                herkunft[platz] = i

    muster = [0] * len(breiten)
    platz = rollenbreite
    while herkunft[platz] >= 0:
        i = herkunft[platz]
        muster[i] += 1
        platz -= breiten[i]
    return float(wert[rollenbreite]), muster


def spaltengenerierung(breiten, bedarf, rollenbreite: int = ROLLENBREITE):
    """Die Schleife. Startbasis: je ein Muster mit nur einer Breite.

    Abbruch, wenn kein Muster mehr einen Wert ueber 1 hat: Eine zusaetzliche
    Rolle kostet 1, also lohnt sich ein neues Muster nur, wenn es zu den
    aktuellen Preisen mehr als 1 wert ist. Das ist das Kriterium der
    reduzierten Kosten.
    """
    anzahl = len(breiten)
    muster = [[0] * anzahl for _ in range(anzahl)]
    for i in range(anzahl):
        muster[i][i] = rollenbreite // breiten[i]

    runden = 0
    while True:
        zielwert, _, dual = loese_master(muster, bedarf)
        wert, neu = bestes_neues_muster(dual, breiten, rollenbreite)
        runden += 1
        if wert <= 1 + 1e-6:
            return muster, zielwert, runden
        muster.append(neu)


def first_fit(breiten, bedarf, rollenbreite: int = ROLLENBREITE) -> int:
    """Die Faustregel: groesstes Stueck zuerst, auf die erste passende Rolle."""
    stuecke = sorted([b for b, menge in zip(breiten, bedarf)
                      for _ in range(menge)], reverse=True)
    rollen: list[list[int]] = []
    for stueck in stuecke:
        for rolle in rollen:
            if sum(rolle) + stueck <= rollenbreite:
                rolle.append(stueck)
                break
        else:
            rollen.append([stueck])
    return len(rollen)


def auswerten(name: str, breiten, bedarf) -> dict:
    muster, schranke, runden = spaltengenerierung(breiten, bedarf)
    ganz, _, _ = loese_master(muster, bedarf, ganzzahlig=True)
    return {"name": name, "muster_gesamt": zaehle_muster(breiten),
            "muster_erzeugt": len(muster), "runden": runden,
            "schranke": schranke, "ganzzahlig": int(round(ganz)),
            "first_fit": first_fit(breiten, bedarf),
            "stuecke_je_rolle": ROLLENBREITE / np.mean(breiten)}


if __name__ == "__main__":
    print("=" * 84)
    print("  SPALTENGENERIERUNG: NUR DIE MUSTER ERZEUGEN, DIE MAN BRAUCHT")
    print("=" * 84)
    print(f"Mutterrolle {ROLLENBREITE:,} mm, {len(BREIT)} bestellte Breiten, "
          f"{sum(BEDARF)} Zuschnitte.\n")

    # --- 1. Zwei Formulierungen ------------------------------------------
    stuecke = sum(BEDARF)
    # Wie viele Rollen braucht man hoechstens? Die Faustregel liefert eine
    # brauchbare Obergrenze - mehr Rollen als das wird niemand benoetigen.
    rollen_obergrenze = first_fit(BREIT, BEDARF)
    print("1. Zwei Modelle fuer dieselbe Aufgabe\n")
    print(f"  {'Formulierung':<34} {'Binaervariablen':>16} {'symmetrisch?':>16}")
    print("  " + "-" * 70)
    print(f"  {'Stueck -> Rolle (naheliegend)':<34} "
          f"{stuecke * rollen_obergrenze:>16,} {'ja':>16}")
    print(f"  {'wie oft welches Muster':<34} "
          f"{'eine je Muster':>16} {'nein':>16}")
    print(f"\n  Der naheliegende Ansatz braucht eine Variable je Stueck und Rolle:")
    print(f"  {stuecke} Zuschnitte x {rollen_obergrenze} Rollen (Obergrenze aus der Faustregel)")
    print(f"  = {stuecke * rollen_obergrenze:,} Binaervariablen.")
    print("\n  Schlimmer als die Zahl ist die Symmetrie: Alle Mutterrollen sind")
    print("  gleich, also beschreibt jede Loesung dieselbe Schnittvorschrift in")
    print("  unzaehligen Umbenennungen. Branch-and-Bound probiert sie einzeln")
    print("  durch und kommt nicht voran - der Suchbaum waechst, ohne dass sich")
    print("  die Schranke bewegt.")
    print("\n  Das Mustermodell hat je Muster genau eine Variable und kennt keine")
    print("  einzelnen Rollen mehr. Damit ist die Symmetrie weg. Sein Problem ist")
    print("  ein anderes - und zwar das folgende.")

    # --- 2. Die Musterzahl ------------------------------------------------
    print("\n" + "-" * 84)
    print("2. Warum man die Muster nicht aufschreiben kann\n")
    gross = auswerten("breite Zuschnitte (1.380-2.200 mm)", BREIT, BEDARF)
    schmal = auswerten("schmale Zuschnitte (380-1.200 mm)", SCHMAL, BEDARF)

    print(f"  {'Instanz':<36} {'Muster':>12} {'davon erzeugt':>14} {'Anteil':>9}")
    print("  " + "-" * 76)
    for fall in (gross, schmal):
        anteil = fall["muster_erzeugt"] / fall["muster_gesamt"]
        print(f"  {fall['name']:<36} {fall['muster_gesamt']:>12,} "
              f"{fall['muster_erzeugt']:>14} {anteil:>8.1%}")

    print(f"\n  Schon das Halbieren der Breiten laesst die Musterzahl von "
          f"{gross['muster_gesamt']:,} auf")
    print(f"  {schmal['muster_gesamt']:,} springen - Faktor "
          f"{schmal['muster_gesamt'] / gross['muster_gesamt']:.0f}. Bei einer echten "
          f"Papierfabrik mit")
    print("  vierzig Breiten und Millimeterschritten sind es mehr, als sich")
    print("  speichern liesse.")
    print(f"\n  Gebraucht werden davon {schmal['muster_erzeugt']} - "
          f"{schmal['muster_erzeugt'] / schmal['muster_gesamt']:.2%} der Gesamtzahl.")

    # --- 3. Die Schleife --------------------------------------------------
    print("\n" + "-" * 84)
    print("3. Die Schleife an der breiten Instanz\n")
    print(f"  Startbasis: {len(BREIT)} triviale Muster (je Rolle nur eine Breite)")
    print(f"  Runden bis kein Muster mehr lohnt: {gross['runden']}")
    print(f"  Muster am Ende: {gross['muster_erzeugt']}")
    print(f"  LP-Schranke: {gross['schranke']:.4f} Rollen")
    print(f"\n  Die LP-Schranke ist eine ZUSAGE: Weniger als "
          f"{np.ceil(gross['schranke'] - 1e-9):.0f} Rollen sind")
    print("  nicht moeglich - unabhaengig davon, wie clever man weiterschneidet.")
    print("  Genau diese Aussage fehlt einer Heuristik (Kapitel Metaheuristiken).")

    # --- 4. Wann es sich lohnt --------------------------------------------
    print("\n" + "-" * 84)
    print("4. Wann sich der Aufwand lohnt - und wann nicht\n")
    print(f"  {'Instanz':<36} {'Faustregel':>11} {'exakt':>8} {'Schranke':>10} "
          f"{'Ersparnis':>11}")
    print("  " + "-" * 80)
    for fall in (gross, schmal):
        ersparnis = (fall["first_fit"] - fall["ganzzahlig"]) / fall["first_fit"]
        print(f"  {fall['name']:<36} {fall['first_fit']:>11} "
              f"{fall['ganzzahlig']:>8} {fall['schranke']:>10.2f} "
              f"{ersparnis:>10.0%}")

    print(f"\n  Bei den breiten Zuschnitten spart die Spaltengenerierung "
          f"{gross['first_fit'] - gross['ganzzahlig']} von")
    print(f"  {gross['first_fit']} Rollen. Bei den schmalen spart sie NICHTS - dort ist die")
    print("  Faustregel bereits optimal.")
    print(f"\n  Der Unterschied haengt an einer einzigen Kennzahl:\n")
    print(f"  {'Instanz':<36} {'Stuecke je Rolle (etwa)':>24}")
    print("  " + "-" * 62)
    for fall in (gross, schmal):
        print(f"  {fall['name']:<36} {fall['stuecke_je_rolle']:>24.1f}")

    print("\n  Passen nur zwei bis drei Stuecke auf eine Rolle, entscheidet jede")
    print("  einzelne Zuordnung viel, und eine kurzsichtige Regel verschenkt")
    print("  ganze Rollen. Passen sechs oder mehr darauf, gleichen sich die")
    print("  Fehler aus - die Reste sind klein gegen die Rollenbreite, und die")
    print("  Faustregel trifft es fast immer.")

    print("\n" + "=" * 84)
    print("  WAS MAN DARAUS MITNIMMT")
    print("=" * 84)
    print("1. Der Perspektivwechsel ist die eigentliche Arbeit: nicht 'welches")
    print("   Stueck wohin', sondern 'wie oft welches Muster'. Damit verschwindet")
    print("   die Symmetrie, die das naheliegende Modell unloesbar macht.")
    print("2. Der Preis dafuer ist eine unaufschreibbare Zahl von Variablen. Die")
    print("   Spaltengenerierung zahlt ihn nicht, sondern erzeugt nur die wenigen")
    print("   Spalten, die die Dualwerte als lohnend ausweisen.")
    print("3. Das Teilproblem ist ein Rucksack - ein Verfahren, das die Leser")
    print("   dieses Buchs schon kennen. Neu ist allein die Schleife.")
    print("4. Und die unbequeme Erkenntnis: Ob sich das alles lohnt, entscheidet")
    print("   die Instanz, nicht die Methode. Bei sechs Stuecken je Rolle ist die")
    print("   Faustregel so gut wie das Optimum - und der Ertrag der")
    print("   Spaltengenerierung liegt dann allein in der SCHRANKE, die beweist,")
    print("   dass man aufhoeren kann zu suchen.")
    print("=" * 84)