Het ellipsoïdealgoritme en een toepassing daarvan op de Lovász-theta-functie (Engelse titel

Abstract

In dit onderzoek is het ellipsoïdealgoritme bestudeerd. Het ellipsoïdealgoritme is een algoritme dat het optimum van een lineaire doelfunctie over een gegeven deelverzameling van Rn tot op een epsilon nauwkeurig kan bepalen. De gegeven verzameling moet hierbij compact, convex en volledig dimensionaal zijn. Dit algoritme kan in polynomiale tijd uitgevoerd worden. Daarom is het dan ook van groot theoretisch belang gebleken; zeer veel problemen zijn te schrijven in een vorm die oplosbaar is met het ellipsoïdealgoritme. In dit verslag wordt een bewijs van de correctheid van het ellipsoïdealgoritme gegeven, het bewijs dat behandeld wordt is oorspronkelijk gegeven door Grötschel, Lovász en Schrijver. Vervolgens zal het belang van het algoritme gedemonstreerd door voor een aantal problemen te laten zien dat ze te schrijven zijn in een vorm die oplosbaar is met het ellipsoïdealgoritme. Allereerst bekijken we een 'eenvoudige' klasse van compacte, convexe verzamelingen: polytopen. Hierbij zal ook de vergelijking worden getrokken met het welbekende SIMPLEX algoritme. Vervolgens zal een veel interessanter probleem beschouwd worden: de Lovász-theta-functie. De Lovász-theta-functie is een functie die aan een graaf een getal toekent. Dit getal kan van grote waarde zijn aangezien het een bovengrens op de Shannon-capaciteit van een graaf geeft. De Shannon-capaciteit van een graaf is over het algemeen erg lastig te berekenen. Dit probleem zal in veel detail worden behandeld, aangezien ook de implementatie van het onderdeel van dit project is. Tot slot zal er dan ook nog aandacht besteed worden aan deze implementatie, in het bijzonder aan de problemen die hierbij ontstonden en de oplossing daarvan. Het grootste probleem bleek zoals verwacht de enorme precisie die in theorie vereist is.