KI vs. klassische Optimierung: Neue Studie zum No-Three-In-Line-Problem

Ein neues Papier aus dem arXiv (2512.11469v1) vergleicht erstmals systematisch klassische Optimierungsmethoden mit modernen KI-Ansätzen für das bekannte No-Three-In-Line-Problem. Dabei geht es darum, die maximale Anzahl von Punkten auf einem n × n‑Raster zu bestimmen, sodass keine drei Punkte auf einer Geraden liegen.

Die Autoren zeigen, dass Integer Linear Programming (ILP) bis zu 19 × 19‑Rastern noch optimale Lösungen liefert, während die Rechenzeit bei größeren Gittergrößen exponentiell ansteigt. Im Gegensatz dazu setzen die KI‑Methoden PatternBoost (ein Transformer‑basiertes Lernmodell) und Proximal Policy Optimization (PPO) auf Mustererkennung und Verstärkungslernen, um approximative Lösungen zu finden.

PatternBoost erreicht bis zu 14 × 14‑Rastern die gleiche Qualität wie ILP und reduziert den Testverlust um 96 %. PPO erzielt perfekte Lösungen für 10 × 10‑Rasters, scheitert jedoch bei 11 × 11, weil die erzeugten Konfigurationen die Nebenbedingungen verletzen. Diese Ergebnisse verdeutlichen, dass klassische Optimierung nach wie vor unverzichtbar ist, wenn exakte Lösungen gefordert sind, während KI‑Methoden bei kleineren Instanzen konkurrenzfähig sind.

Die Autoren betonen, dass hybride Ansätze – die Stärken von ILP und KI kombinieren – die vielversprechendste Richtung darstellen, um die Skalierbarkeit auf größere Problemgrößen zu verbessern.