Combinatorische grenzen voor heuristische zoekalgoritmen

De meeste exacte algoritmen voor combinatorische optimalisatie genereren een optimaliteitsgarantie of geven de afstand tot een ondergrens op het optimum, wanneer ze een oplossing geven voor een minimalisatieprobleem. Jammergenoeg blijken veel reële problemen te uitdagen voor deze algoritmen om effectief een oplossing te berekenen. Heuristieken, zoals local search gebaseerde methoden, voorzien geen optimaliteitsbewijzen of -grenzen. Niettemin preseteren ze vaak beter wanneer aanvaardbare oplossingen voor moeilijke problemen nodig zijn.Dit project zal heuristische zoekalgoritmen verbeteren door middel van nieuwe begrenzingsmethoden, geïnspireerd door `linear programming' relaxaties en `valid inequalities'. Het behelst twee parallelle onderzoekslijnen: een gefocust op exacte methoden om algemene heuristische methoden te bekomen en een tweede gericht op heuristische datastructuren om `local search neighbourhoods' te reduceren.  De nieuwe methodologieën zullen tot stand komen tijdens het onderzoek van twee industriële gevalsstudies: een rittenplanningsprobleem met laadvoorwaarden en een taakplanningsprobleem voor magazijnoperatoren. De beoogde academische resultaten omvatten nieuwe ondergrensmethoden voor heuristische zoekalgoritmen en efficiëntere local search heuristieken door het ontwikkelen van `neighbourhood'-filters.De onderzoeksgroep ontwikkelt op deze manier betere algoritmen en breidt zijn industriele toepassingsmogelijkheden aanzienlijk uit.

Trefwoorden:Combinatorial optimization

Disciplines:Operations-onderzoek en mathematisch programmeren