In 2018 werd er te Gent een drama ontketend: met behulp van digitale wachtrijen probeerde men het scholentoekenningsprobleem algoritmisch op te lossen. Zo voorkomt men dat ouders beginnen kamperen voor de schoolpoort om hun zoon/dochter in de meest populaire scholen in te schrijven. Het algoritme ging eerlijk aan het werk, maar toch was er zeer veel ontevredenheid. Er waren namelijk nog problemen met “wissels” (twee of meer studenten die hun voorkeur wel zouden krijgen moesten ze gewoon onderling wisselen) en dergelijke.
De vraag die vanzelf in je opkomt is natuurlijk, “hoe moeilijk kan het zijn om met een computer de perfecte oplossing te vinden?” In deze opgave kunnen jullie zelf het antwoord op deze vraag vinden, want we proberen het scholentoekenningsprobleem op te lossen met een branch-and-bound-algoritme. Een correct branch-and-bound-algoritme zal voor gegeven invoer de optimale oplossing geven door elk deel van de zoekruimte te bekijken waar mogelijks nog verbetering in schuilt.
Merk op dat we het probleem lichtelijk wijzigen van de werkelijke situatie: zo houden we geen rekening met de aparte verdeling voor indicatorleerlingen en laten we de ouders maximaal 5 scholen in volgorde opgeven.
Een School1 heeft een ID (enkel te gebruiken om te printen) en een capaciteit. De capaciteit geeft aan hoeveel studenten aan deze school kunnen inschrijven. Een Student2 heeft 5 voorkeurscholen. Een oplossing (van de vorm Map<Student, School>) kent aan elke student een school (of null) toe. Komt een student in zijn eerste voorkeursschool terecht, verdient de oplossing 16 punten. Komt hij in zijn tweede voorkeursschool terecht, verdient de oplossing 8 punten (enzovoort). Merk op dat met een student met slechts twee voorkeursscholen (null voor de andere drie) dan 8 punten te verdienen zijn door hem geen school te geven. De details vind je in de int getScore(School school) methode van Student. De totale score van een oplossing is de som van de scores voor elke toekenning.
Implementeer de interface SchoolAssignmentSolver3 in een klasse genaamd BranchAndBoundSolver. Schrijf daarvoor een methode Map<Student, School> assign(Set<School> schools, Set<Student> students) die de één van de hoogst scorende oplossingen teruggeeft, door elke student in students te mappen op een school in schools of null. Je mag uiteraard de capaciteit van de scholen niet overschrijden. Maak gebruik van een branch-and-bound-algoritme met minstens 1 bound.
Je kan gebruik maken van enkele kleine tests in SimpleTest4 die je zelf kan aanvullen.