Solver

Ein Solver ist die Softwarekategorie, die ein mathematisches Optimierungsmodell — typischerweise über ein Dateiformat wie LP, MPS, NL, OPL oder CNF, oder über eine Modellierungssprachen-/API-Anbindung — einliest und algorithmisch eine optimale (oder innerhalb einer Toleranz nahezu optimale) Lösung, primale und duale Werte, reduzierte Kosten, Sensitivitätsinformationen und einen Zulässigkeitsbericht erzeugt. Im OR-Ökosystem zerfallen Solver nach Problemklasse: lineare Programmierung (LP), gemischt-ganzzahlige lineare Programmierung (MILP), quadratische Programmierung (QP), gemischt-ganzzahlige quadratische Programmierung (MIQP), Kegel-Programmierung zweiter Ordnung (SOCP), semidefinite Programmierung (SDP), allgemeine nichtlineare Programmierung (NLP), Constraint Programming (CP) und globale Optimierung. Die algorithmischen Engines bilden Familien: für LP das Simplex-Verfahren von Dantzig (1947) und die Innere-Punkte-Familie von Karmarkar (1984) mit Barrier-Predictor-Corrector-Varianten; für MILP Branch-and-Cut (Padberg und Rinaldi 1991) auf Branch-and-Bound (Land und Doig 1960), Branch-and-Price (Barnhart et al. 1998), Presolving, Zulässigkeitsheuristiken, Gomory- und andere Schnittebenen-Schichten; für NLP Sequential Quadratic Programming, Innere-Punkte- und Trust-Region-Varianten. Solver gliedern sich in zwei große Gruppen: **kommerzielle Solver** — lizenzpflichtige Hochleistungsprodukte mit breitem Enterprise-Support und aggressiven Heuristik-Schichten; **Open-Source-Solver** — frei nutzbare Projekte, die für akademische und KMU-Anwendungen meist ausreichen und auf manchen Problemklassen 2-10x langsamer als kommerzielle Vergleichsprodukte laufen. Modelle werden über standardisierte Dateiformate (LP, MPS, NL und ähnliche) oder über algebraische Modellierungssprachen und die mathematischen Modellierungspakete wissenschaftlich-numerischer Sprachen übergeben. Vergleichsleistung wird in unabhängigen akademischen Benchmark-Reihen verfolgt. Bixby (2002) und Achterberg (2007) dokumentieren die MILP-Solver-Beschleunigung der letzten dreißig Jahre — nicht nur Hardware, sondern Presolving, Dualer Simplex, Schnittgenerierung und Heuristiken liefern eine etwa 10⁶-fache Gesamtbeschleunigung.