Hvordan løser man kvadratiske tildelingsproblemer ?
Når man designer f.eks. en universitetscampus er det vigtigt placere
bygningerne rigtigt i forhold til hinanden. To bygninger, mellem
hvilke der er livlig trafik, skal ikke ligge i hver sin ende af
campus.
Denne type problemer kaldes "kvadratiske tildelingsproblemer", og de
er meget svære at løse.
I projektet skal der udarbejdes et program til løsning af sådanne
problemer, og der skal foretages en empirisk undersøgelse af, hvordan
programmet håndterer, at der er "forbudte tildelinger". I
Campus-eksemplet svarer dette til, at bestemte bygninger ikke må
ligge på bestemte placeringer.
Opgavens kerne er implementering og eksperimenter med de
implementerede metoder. Der skal også udvikles en simpel grafisk
brugergrænseflade til programmet.
Opgavestiller
Professor
Jens Clausen,
IMM, 4525 3387.
Email: jc@imm.dtu.dk