💻 computer science

FORGE: Foundational Optimization Representations from Graph Embeddings

Het artikel introduceert Forge, een framework dat een vector-gekwantiseerde graaf-autoencoder voorgetraind op diverse mixed-integer programmeringsinstanties om schaalbare, generaliseerbare representaties te creëren die de huidige state-of-the-art methoden overtreffen in het voorspellen van integriteitskloven en het sturen van zoekprocessen zonder dat daarvoor optimale oplossingslabels vereist zijn.

Oorspronkelijke auteurs: Zohair Shafi, Serdar Kadioglu

Gepubliceerd 2026-06-19

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Zohair Shafi, Serdar Kadioglu

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme, complexe puzzel probeert op te lossen. In de wereld van de informatica worden deze puzzels Combinatorische Optimalisatieproblemen genoemd. Ze zijn overal: van het uitstippelen van de meest efficiënte route voor een bezorgwagen tot het plannen van elektriciteitsnetwerken of het organiseren van een magazijn.

Traditioneel vereist het oplossen van deze puzzels krachtige, dure computerprogramma's (genaamd "solvers") die miljoenen combinaties proberen. Het is alsof je probeert een specifieke naald in een hooiberg te vinden door elk stukje hooi één voor één te controleren.

Onlangs probeerden wetenschappers Machine Learning (AI) te gebruiken om dit te versnellen. Maar er was een grote vangnet: om de AI te leren hoe hij deze puzzels moet oplossen, moest je eerst de trage, dure solvers gebruiken om duizenden puzzels perfect op te lossen, puur om een "leerboek" te maken waar de AI van kon studeren. Dit was een vicieuze cirkel: je had het trage hulpmiddel nodig om het snelle hulpmiddel te onderwijzen, wat het doel eigenlijk tenietdeed.

Maak kennis met "Forge."

De auteurs van dit paper hebben een nieuw framework ontwikkeld genaamd Forge. Zie Forge niet als een puzzeloplosser, maar als een universele vertaler of een meesterbibliothecaris voor optimalisatieproblemen.

Hier is hoe het werkt, onderverdeeld in eenvoudige analogieën:

1. Het Probleem: Elke Puzzel Ziet Er Anders Uit

Stel je een bibliotheek met puzzels voor. Sommige zijn legpuzzels, andere zijn Sudoku en weer andere zijn kruiswoordpuzzels. Eerdere AI-modellen waren als specialisten: je moest een specifieke AI trainen voor Sudoku en een andere voor kruiswoordpuzzels. Als je de Sudoku-AI een kruiswoordpuzzel gaf, was hij de weg kwijt. Ook hadden ze de "antwoordsleutel" (de perfecte oplossing) nodig om te leren, wat erg duur was om te verkrijden.

2. De Oplossing: Een "Woordenschat" voor Puzzels

De auteurs keken naar hoe AI taal (zoals chatbots) en afbeeldingen verwerkt. Ze realiseerden zich dat in plaats van de AI het antwoord op elke puzzel te leren, ze de AI konden leren om de vorm en structieve van de puzzel zelf te herkennen.

De Bipartiete Graaf: Ze veranderen elk wiskundig probleem in een kaart van stippen en lijnen (een graaf). De stippen zijn de "variabelen" (de dingen die je kunt veranderen) en de "constraints" (de regels die je moet volgen).
Vector Quantization (Het Magische Woordenboek): Dit is het geheime ingrediënt. Stel je voor dat de AI een gigantisch woordenboek heeft met 5.000 unieke woorden. Wanneer de AI naar een puzzel kijkt, probeert hij niet het hele plaatje uit het hoofd te leren. In plaats daarvan breekt hij de puzzel af in kleine stukjes en wijst aan elk stukje een "woord" toe uit zijn woordenboek.
- Een specifiek type regel krijgt dan het woord "Code 12."
- Een specifiek type variabele krijgt het woord "Code 45."
Het Resultaat: In plaats van een rommelig, complex wiskundig probleem, ziet de AI nu een eenvoudige zin gemaakt van deze codes. Dit stelt hem in staat om de globale structuur van het probleem te begrijpen zonder dat hij het uiteindelijke antwoord hoeft te weten.

3. De Training: Leren zonder Antwoorden

Dit is de grootste doorbraak. Forge werd ongesuperviseerd getraind.

De Oude Manier: "Hier is een puzzel en de perfecte oplossing. Leer hoe je van A naar B komt."
De Forge-manier: "Hier zijn 2.850 verschillende puzzels. Kijk gewoon hoe ze zijn opgebouwd. Groepeer puzzels die qua structuur op elkaar lijken. Je hoeft de oplossing niet te kennen; leer alleen de vorm van het probleem kennen."

Het is als een kind dat leert dieren te herkennen. Ze hoeven niet te weten hoe je een hond of een kat voortbrengt om te weten dat een Golden Retriever en een Poedel beide "honden" zijn. Ze leren simpelweg de visuele patronen herkennen. Forge leerde de "visuele patronen" van wiskundige problemen.

4. Wat Kan Forge Nu Doen?

Zodra Forge deze "woordenschat" had geleerd, testten de onderzoekers het op twee manieren:

A. Clustering (De Bibliotheek Sorteren)
Ze gaven Forge een heleboel puzzels die hij nog nooit eerder had gezien. Zonder te worden verteld wat het waren, slaagde Forge erin om ze in groepen te sorteren. Hij wist dat een "Set Cover"-probleem structureel vergelijkbaar was met andere "Set Cover"-problemen, zelfs als ze een andere grootte of moeilijkheidsgraad hadden. Hij deed dit beter dan eerdere methoden die probeerden de details te middelen.

B. De Solver Helpen (Het "Hint"-Systeem)
Dit is waar het praktisch wordt. De onderzoekers namen een topniveau commerciële solver (Gurobi) en gaven deze een "spiekbriefje" gegenereerd door Forge.

Taak 1: De "Gap" Gok: Forge keek naar een moeilijke puzzel en gokte hoe ver de "makkelijke" versie van het probleem afweek van de "moeilijke" versie. Op basis van deze gok creëerde het een "pseudo-cut" (een regel) om de solver te vertellen: "Hé, het antwoord ligt zeker in dit bereik, verspil geen tijd aan zoeken buiten dit gebied." Dit zorgde ervoor dat de solver veel sneller goede antwoorden vond.
Taak 2: De "Search" Gids: Forge keek naar de puzzel en zei: "Deze specifieke variabelen maken waarschijnlijk deel uit van de oplossing. Focus je eerst op hen." Dit leidde de solver efficiënter door het doolhof.

De Kern van het Verhaal

Geen "Antwoordsleutel" Nodig: Forge leerde door naar de structuur van problemen te kijken, niet door ze eerst perfect op te lossen.
Eén Model voor Alles: Eén enkel voorgetraind Forge-model werkte op veel verschillende soorten problemen (logistiek, planning, etc.) en verschillende formaten.
Echte Resultaten: Toen ze de "hints" van Forge toevoegden aan een commerciële solver, vond de solver sneller betere oplossingen, wat de prestaties in sommige gevallen met wel 85% verbeterde.

Kortom, Forge is een fundamenteel model dat AI leert om de structuur van complexe wiskundige problemen te "lezen" als een taal, waardoor het slimme hints kan geven aan solvers zonder dat het vooraf de antwoorden hoeft te leren. De auteurs hebben hun code en modellen zelfs openbaar gemaakt, zodat anderen deze "woordenschat" kunnen gebruiken om betere optimalisatietools te bouwen.

Technisch Overzicht: Forge: Fundamentele Optimalisatie-representaties vanuit Graaf-embeddings

1. Probleemstelling

Combinatorische optimalisatie (CO) problemen, met name Mixed-Integer Programming (MIP), zijn fundamenteel voor wetenschap en techniek maar blijven computationeel duur om op te lossen. Hoewel machine learning (ML) veelbelovende alternatieven biedt, lijden huidige op leren gebaseerde benaderingen onder significante beperkingen op het gebied van schaalbaarheid en generalisatie:

Data-afhankelijkheid: Training vereist doorgaans het oplossen van een groot aantal moeilijke instanties om gelabelde data te genereren, wat hoge computationele kosten met zich meebrengt en afhankelijk is van de solvers die onderzoekers juist willen versnellen.
Gebrek aan generalisatie: Bestaande methoden trainen vaak specifieke modellen voor specifieke probleemdistributies, downstream-taken of probleemgroottes. Ze falen in het generaliseren over verschillende probleemdomeinen (bijv. Set Cover versus Combinatorial Auction) of taaltypen (bijv. cut-generatie versus zoekbegeleiding).
Structurele beperkingen: De meeste CO-methoden vertrouwen op Graph Neural Networks (GNN's), die effectief lokale variabele-constraint informatie kunnen vastleggen, maar moeite hebben met het coderen van betekenisvolle globale instantiestructuren vanwege inherente lokale bias.

Het artikel stelt de noodzaak vast voor een fundamentele optimalisatie-representatie: een vooraf getraind, algemeen doelmodel dat in staat is om MIP-embeddings te genereren die generaliseren over taken, problemen en groottes, getraind op een ongesuperviseerde wijze zonder dat optimale oplossingen vereist zijn.

2. Methodologie: Het Forge-framework

Forge (Foundational Optimization Representations from Graph Embeddings) is een framework dat een vector-gekwantiseerde graaf-autoencoder voor-traint op een diverse collectie MIP-instanties. Het put inspiratie uit Foundation Models uit Natural Language Processing (NLP) en Computer Vision (CV).

Kernarchitectuur

Het framework werkt via de volgende fasen (Figuur 1):

MIP-naar-BP (Bipartite Representatie): MIP-instanties worden gerepresenteerd als bipartiete grafen waarbij knopen variabelen en constraints zijn.
- Knoopkenmerken: In tegenstelling tot eerdere werken die vertrouwen op door solvers gegenereerde kenmerken (bijv. uit branch-and-bound bomen), gebruikt Forge alleen basis input-eigenschappen: de richting van de constraint (>, <, =) en RHS-waarden voor constraints; variabele-type, grenzen en objectieve coëfficiënten voor variabelen. Dit zorgt ervoor dat het model niet afhankelijk is van het oplossen van de instantie.
BP-naar-GNN: Een GraphSAGE-gebaseerde GNN (twee lagen) verwerkt de bipartiete graaf om continue embeddings voor elke knoop te genereren.
Vector-gekwantiseerde Codeboek (De "Vocabulaire"): Om het onvermogen van de GNN om globale structuur te vatten aan te pakken, worden de continue embeddings door een vector-kwantiseerder geleid. Dit brengt elke knoop in kaart naar een discrete code uit een leerbaar codeboek van grootte $k$ $k$ (dat fungeert als een vocabulaire).
- Deze stap behoudt globale structurele informatie door een distributie van discrete codes over de instantie te creëren, analoog aan de token-distributies in taalmodellen.
Reconstructie (Autoencoder): De discrete codes worden teruggekaatst naar codewords en door decoders gestuurd om de oorspronkelijke knoopkenmerken en randgewichten te reconstrueren.
Verliesfunctie: Het model wordt ongesuperviseerd getraind om het volgende te minimaliseren:
- Reconstructieverlies (knoopkenmerken en randen).
- Codeboekverlies (het bewegen van codewords naar embeddings).
- Commitment-verlies (het bewegen van embeddings naar codewords).

Representaties

Eenmaal getraind, produceert Forge twee niveaus van representaties:

Lokaal: Discrete codewords voor individuele variabelen en constraints.
Globaal: Een instantie-niveau embedding afgeleid van de frequentiedistributie van de toegewezen codes over de gehele graaf. De dimensie van de embedding is gelijk aan de vocabulaire-grootte ($|codebook|$).

3. Belangrijkste Bijdragen

Het artikel schetst vijf primaire bijdragen:

Foundation Model Stap: Introductie van Forge, een enkel voor-getraind model dat MIP-embeddings genereert op zowel instantie- als fijnmazig niveau (variabele/constraint) zonder supervisie.
Ongesuperviseerde Generalisatie: Demonstratie dat Forge-embeddings ongeziene instanties over diverse probleemdomeinen en moeilijkheidsgraden accuraat kunnen clusteren, waarbij ze statische kenmerken en standaard GNN-readouts overtreffen.
Gesuperviseerde Aanpasbaarheid: Bewijs dat hetzelfde voor-getrainde model met minimale, goedkoop gelabelde data kan worden gefinetuned voor radicaal verschillende downstream-taken (integrality gap voorspelling en zoekbegeleiding) over uiteenlopende probleemgroottes.
Solver Integratie: Succesvolle integratie van Forge-voorspellingen in Gurobi, een commerciële solver, wat consistente verbeteringen in de primal gaps laat zien over meerdere probleemtypen.
ML Augmentatie: Verbetering van state-of-the-art (SOTA) leer-gebaseerde methoden (specifiek Li et al., 2025 en PS-Gurobi) door Forge-embeddings toe te voegen, wat significante prestatiewinsten oplevert op ongeziene instanties.

4. Experimentele Resultaten

Ongesuperviseerde Clustering

Setup: Getraind op 1.800 MIPLIB-instanties; getest op 1.000 ongeziene instanties uit D-MIPLIB en strIPlib die 21 domein-moeilijkheidscombinaties beslaan.
Metriek: Normalized Mutual Information (NMI) voor clustering-accuratesse.
Prestaties: Forge bereikte een NMI van 0,953, wat Mean Readout (0,726) en Label Propagation (0,790) aanzienlijk overtreft. Visualisaties (PaCMAP) toonden duidelijke clusters voor elk probleemtype en een helder gradiënt van makkelijk naar moeilijk, ondanks dat het model deze specifieke instanties nooit tijdens de training heeft gezien.

Taak I: Integrality Gap Voorspelling (Pseudo-Cut Generatie)

Doel: De integrality gap voorspellen om een pseudo-cut voor de root node te genereren, waardoor de LP-relaxatie grens wordt aangescherpt.
Training: Gefinetuned op 450 instanties (CA, SC, GIS) met labels gegenereerd door Gurobi (120s timeout), waarbij de volledige optimaliteit werd vermeden.
Resultaten:
- Op "zeer moeilijke" test-instanties (inclusief MVC, die ongezien was tijdens de fine-tuning), bereikte Forge gemiddelde absolute afwijkingen van 12–19% over verschillende probleemtypen.
- Impact op Solver: Integratie van Forge pseudo-cuts in Gurobi verminderde de primal gap met wel 85% (bijv. 84,52% winst op Generalized Independent Set) vergeleken met Gurohi alleen.
- Vergelijking: Presteerde beter dan de SOTA-methode van Li et al. (2025) (18,63% afwijking vs. 20,14%) op 17.500 ongeziene instanties zonder extra training.

Taak II: Zoekbegeleiding (Search Guidance)

Doel: Voorspellen welke variabelen waarschijnlijk in de optimale oplossing zitten om de branch-and-bound zoektocht te begeleiden.
Training: Gefinetuned op 700 instanties met een combinatie van Binary Cross-Entropy (BCE) en Triplet Loss. Labels werden afgeleid van haalbare oplossingen gevonden binnen 5 minuten (geen optimaliteit vereist).
Resultaten:
- Impact op Solver: Gurobi met Forge zoekbegeleiding bereikte tot wel 48,75% verbetering in de primal gap en tot wel 35% snelheidswinst in convergentietijd op middelgrote instanties.
- ML Augmentatie: Wanneer gebruikt als augmentatie voor PS-Gurobi (een SOTA leer-gebaseerde zoekbegeleidingsmethode), reduceerden Forge-embeddings de primal gap met meer dan 40% (Combinatorial Auction) en 50% (Generalized Independent Set).

5. Betekenis en Claims

Het artikel claimt dat Forge een belangrijke stap vormt richting foundation models voor optimalisatie. De betekenis ligt in:

Het Doorbreken van de Solver-Afhankelijkheid: Het leert structurele representaties zonder toegang te vereisen tot optimale oplossingen of interne solver-statussen tijdens de pre-training, wat het "kip-of-ei" probleem aanpakt waarbij solvers nodig zijn om solvers te trainen.
Universele Representatie: Het demonstreert dat een enkel model kan generaliseren over uiteenlopende probleemtypen (bijv. Set Cover, Combinatorial Auction, Vertex Cover) en taaltypen (gap voorspelling, zoekbegeleiding), een capaciteit die voorheen beperkt was tot probleem-specifieke of taak-specifieke modellen.
Praktisch Nut: Het framework is niet louter theoretisch; het integreert direct met commerciële solvers en verbetert bestaande ML-pipelines, wat directe, meetbare winsten in efficiëntie oplevert.
Open Science: De auteurs stellen trainingscode, pre-trained gewichten en embeddings beschikbaar om verder onderzoek naar representatieleer in optimalisatie te stimuleren.

De auteurs blijven bescheiden over beperkingen, waarbij zij opmerken dat de huidige schaal (3,25M parameters) klein is vergeleken met andere foundation models, de semantiek van de geleerde "vocabulaire" nog onverkend is, en de huidige integraties "one-shot" zijn in plaats van iteratief gedurende de branch-and-bound boom. Zij suggereren dat toekomstig werk deze principes kan uitbreiden naar Constraint Satisfaction Problems (CSP) en SAT.