An individual project associated to CMA

Fellow:
Mr. Truls Flatberg

Project Title (Norwegian):
Heltallsoptimering i dynamiske modeller

Prosject leader:
Professor Geir Dahl

Source / project number:
The Research Council of Norway, 134514/410

Duration:
... - February 1, 2004

Truls Flatberg defended his thesis on March 31, 2004.

Abstract (Norwegian):
I en rekke anvendelser innenfor bl.a. transport, planlegging og geometri forekommer optimeringsproblemer med heltallige eller diskrete variabler. Slike problemer er beregningsmessig vanskelig. Kompleksiteten skyldes primært heltallskravene på variablene idet de tilhørende lineære optimeringsproblemene kan løses effektivt.
I dette prosjektet vil man studere en slik klasse av heltalls lineær programmeringsproblemer (HLP) som involverer partisjonering av diskrete mengder. Prosjektets mål er
(i) å analysere denne strukturen matematisk, finne nye gyldige ulikheter som gir bedre approksimasjoner, og
(ii) utvikle effektive løsningsalgoritmer basert på analysen i av HLP problemet i punkt(i). Arbeidet er basert på metoder fra kombinatorisk optimering og polyedrisk kombinatorikk.