KI und die schwierigen Probleme der Welt · Theoretische Informatik · arXiv · 2026-10-22
Interpretierbare Schnittebenenauswahl für die gemischt-ganzzahlige lineare Programmierung mittels genetischer Programmierung
Originaltitel: Interpretable Cutting Plane Selection for Mixed-Integer Linear Programming Using Genetic Programming
Schnittebenen sind ein zentraler Bestandteil von Solvern für die gemischt-ganzzahlige lineare Programmierung (MILP), doch aktuelle handgefertigte Schnittstrategien sind statisch, während auf neuronalen Netzen basierende gelernte Strategien nur begrenzte Interpretierbarkeit und keine Konvergenzgarantien bieten. Die Autoren schlagen GPSCS vor, das erste lernbasierte Framework, das handgefertigte Heuristiken in eine vollständig interpretierbare Strategie generalisiert: Genetische Programmierung entwickelt eine symbolische Bewertungsfunktion, die Kandidatenschnitte rangiert, und ein leichtgewichtiger, statistikbasierter Mechanismus entscheidet adaptiv, wie viele der am höchsten rangierten Schnitte in jeder Separierungsrunde hinzugefügt werden. Evaluiert in SCIP an sieben Klassen synthetischer und realer Benchmarks, deren Evaluationsinstanzen im Durchschnitt 41-mal schwieriger sind als die Trainingsinstanzen, verbessert GPSCS die durchschnittliche Lösungszeit um 6% gegenüber dem SCIP-Standard und erreicht eine zweifache Beschleunigung sowohl gegenüber einem aktuellen neuronalen Ansatz als auch gegenüber einer Baseline ohne Schnitte.