Wetenschappers hebben een innovatieve benadering ontwikkeld om de efficiëntie van solvers voor mixed-integer lineaire programmering (MILP) te verbeteren. De nieuwe methode, genaamd MILP-Evo, maakt gebruik van een gesloten lus waarin Large Language Models (LLM's) en programma-evolutie samenwerken om de interne logica van deze solvers volledig automatisch te ontwerpen.
Het oplossen van MILP-problemen is een cruciale taak binnen de computationele optimalisatie, maar het ontwerp van de bijbehorende software is traditioneel een tijdrovend proces. Hoewel machine learning in het verleden al werd ingezet om deze processen te versnellen, ontstond er vaak een probleem met de transparantie. Volgens een wetenschappelijk rapport op arxiv.org worden veel data-gestuurde methoden gekenmerkt door ondoorzichtige modellen of externe voorspellers, waardoor het voor experts moeilijk is om de gemaakte keuzes te inspecteren of aan te passen.
Van 'black-box' naar transparante logica
Om dit gebrek aan inzicht te overbruggen, richt MILP-Evo zich op het creëren van zogenaamde 'white-box' componenten. In plaats van een ondoorgrondelijk neuraal netwerk te gebruiken, genereert het systeem expliciete programma-logica die direct leesbaar en aanpasbaar is voor mensen. Voorheen werd dergelijke logica bijna uitsluitend handmatig geschreven door domeinexperts. De onderzoekers, waaronder Jinbiao Nie, stellen nu voor om dit proces te automatiseren via een zoekproces dat wordt aangestuurd door LLM's.
Het framework is technisch gerealiseerd via PySCIPOpt, waardoor de AI in staat is om code te schrijven die direct door de solver kan worden uitgevoerd. De effectiviteit van deze gegenereerde componenten wordt vervolgens end-to-end gemeten, waarbij de resultaten direct worden teruggekoppeld naar het model voor verdere optimalisatie. Zoals beschreven in de publicatie op , stelt deze methode de AI in staat om continu te leren van de directe feedback uit de solver.
De cyclus van evolutie en reflectie
Het hart van MILP-Evo is een iteratieve cyclus waarin kandidaat-programma's worden gegenereerd en vervolgens in de SCIP-omgeving worden geladen. De prestaties worden getoetst op specifieke MILP-instanties, waarna vier specifieke mechanismen de evolutie sturen:
- Selectie op basis van prestaties: Alleen de meest effectieve logica wordt behouden voor volgende generaties.
- Gerichte reparatie: Codefouten worden automatisch opgespoord en gecorrigeerd.
- Diagnostische reflectie: Het systeem analyseert de redenen achter het succes of falen van bepaalde benaderingen.
- Bewaking van diversiteit: Er wordt actief voorkomen dat het systeem vastloopt in lokale optima door de variatie in programma's te bewaken.
In de praktijk is deze aanpak toegepast op het ontwerp van een 'branching rule' en een 'cut selector'. Dit zijn twee essentiële onderdelen die bepalen hoe een solver door de complexe zoekruimte van een wiskundig probleem navigeert.
Resultaten en toekomstperspectief
De resultaten van het onderzoek tonen aan dat deze LLM-gestuurde evolutie in staat is om beleidsregels te vinden die concurrerend zijn met handmatig ontworpen versies. Dit werd aangetoond via tests over vier verschillende benchmark-families. Een groot voordeel is dat de uiteindelijke output bestaat uit leesbare programmeertaal, wat integratie in bestaande workflows aanzienlijk vereenvoudigt.
Het onderzoek, dat is gecategoriseerd onder Artificial Intelligence en Neural and Evolutionary Computing op , markeert een belangrijke stap richting autonome software-engineering voor complexe optimalisatie. Door de creativiteit van LLM's te koppelen aan een strikte evaluatielus, wordt de kloof tussen rigide handmatige logica en ondoorzichtige AI-modellen gedicht. Volgens de details in de volledige tekst op biedt dit een nieuw paradigma voor het ontwikkelen van hoogwaardige, transparante optimalisatiesoftware.