Matematikk og kode for beste uavhengige delnettverk

Avhandlinga tek for seg tre problem der ein skal finna den optimale delen av eit nettverk som svarer til utvalde modellar for omgrepa samanheng og uavhengigheit. Problema er enkle å formulera, men dei tok likevel over fire års doktorgradsarbeid for å oppnå små bidrag i nokre få retningar innan algoritmar og optimering. Fire år med tenking, lesing, diskusjon og koding (pluss ønsketenking og lukketreff), motivert av dei mange bruksområda som kvar av desse nettverksbyggingsproblema kan ha innan telekommunikasjon og forsyningsverksemd, anleggsplassering, fylogenetikk, og mange andre område innan operasjonsanalyse og optimering.

Arbeidet er grunnforsking. Alle tre problema kokar ned til det å plukke ut punkt og liner i eit diagram (som representerer ein graf). Likevel, dersom slike diagram modellerer t.d. kompatible par av donorar og pasientar i eit nyretransplantasjonsprogram, eller alternative transportmiddel i eit system for distribusjon av frakt, kan resultata enkelt skreddarsyast mot intelligente prototyper for å støtta avgjersler.

Interessant nok er den matematiske strukturen bak kvart av problema eit polyeder - akkurat som platonske lekamar, rett nok i ein høgare dimensjon. Dei fleste resultata omhandlar det å finna betre skildringar av dei geometriske strukturane, og er gjevne i form av teorem om moglege formuleringar av polyederet som representerer mengda av løysingar på kvart av problema.

Utover å kasta ljos over det usynlege grunnlaget, fører den polyedriske vinklinga òg til forbetra algoritmar for å handtera nettverksbyggingsproblema. Dei nye geometriske skildringane vert omsette til lineære ulikskapar i heiltalsprogrammeringsmodellar, og meir effektive rekneresultat når vi løyser vanskelegare instansar av desse optimeringsproblema.

Vi deler kildekoden til implementasjonen av alle utvikla algoritmar med omverda, og fremjer dermed attbruk, vidare forsking og nye bruksområde innan forsking og utvikling.

Avhandlinga er rettleia av prof. Dag Haugland.

Personalia

Phillippe er frå Brasil, der han fullførte MSc og BSc grader i informatikk ved Universidade Federal de Minas Gerais, etterfulgd av eit hovudfagsstudium i rein matematikk. Før det var han eit semester som gjesteforskar ved Høgskolen i Molde, og eit år ved Hokkaido University, med det prestisjetunge MEXT-stipendet frå den japanske regjeringa. Phillippe er no ingeniør ved UiB, og er glad for utsiktene til å bli norsk og permanent tene samfunnet vårt.