Subgraph-GNNs: Theorie vs Praxis bei MILP-Branching
Graph Neural Networks (GNNs) haben sich als vielversprechende Methode für das „Learning to Branch“ in Mixed‑Integer Linear Programming (MILP) etabliert. Während klassische Message‑Passing GNNs (MPNNs) effizient arbeiten, fehlt ihnen theoretisch die Ausdruckskraft, um die komplexen Strukturen von MILP vollständig abzubilden. Auf der anderen Seite bieten höhere‑Ordnung‑GNNs wie 2‑FGNNs die nötige Expressivität, sind jedoch in der Praxis zu rechenintensiv.
