Technische Samenvatting: Een Analyse van (Mixed-)Integer Lineaire Programmeringsformuleringen voor het Maximally Diverse Grouping Probleem

Probleemdefinitie

Het Maximally Diverse Grouping Problem (MDGP) is een klassiek NP-hard combinatorisch optimalisatieprobleem. Gegeven een verzameling items $I$ en een verzameling groepen $G$, is het doel om elk item aan precies één groep toe te wijzen zodat de totale diversiteit binnen de groepen wordt gemaximaliseerd. De diversiteit van een paar items $(i, j)$ wordt gedefinieerd door een parameter $d_{ij} \geq 0$. De totale diversiteit is de som van alle paarwijze diversiteiten voor items die aan dezelfde groep zijn toegewezen. Het probleem is onderworpen aan beperkingen op het aantal items per groep, gedefinieerd door ondergrenzen $l_g$ en bovengrenzen $u_g$ voor elke groep $g \in G$.

Toepassingen voor het MDGP omvatten het toewijzen van studenten aan groepen of cursussen, het vormen van projectteams, het creëren van reviewer-groepen en het plannen van examens. Hoewel heuristische benaderingen gebruikelijk zijn in de literatuur, waren exacte oplossingsmethoden historisch gezien beperkt tot kleine probleeminstanties.

Methodologie en Modelformuleringen

Het artikel analyseert en vergelijkt vier verschillende (mixed-)integer lineaire programmeringsformuleringen (MILP):

1. Standaard Formulering (Weitz en Lakshminarayanan, 1998):

   • Variabelen: Binaire variabelen $x_{ig}$ geven aan of item $i$ is toegewezen aan groep $g$. Hulpbinaire variabelen $y_{ijg}$ representeren of items $i$ en $j$ beide in groep $g$ zitten.
   • Mechanisme: Het doel wordt lineair gemaakt met behulp van restricties $y_{ijg} \leq x_{ig}$ en $y_{ijg} \leq x_{jg}$.
   • Zwakte: De Lineaire Programmering (LP) relaxatie is zwak. In de relaxatie kunnen items fractioneel aan alle groepen worden toegewezen ($x_{ig} = 1/|G|$), waardoor de objectieve waarde de som van alle mogelijke $d_{ij}$ paren wordt, wat een onbereikbare bovengrens is voor haalbare gehele oplossingen.

2. Papenberg en Klau Formulering (2021):

   • Variabelen: Binaire variabelen $z_{ij}$ geven aan of items $i$ en $j$ aan de zelfde groep zijn toegewezen, zonder de groep te specificeren.
   • Mechanisme: Gebruikt transitiviteitsrestricties (bijv. $-z_{ij} + z_{ik} + z_{jk} \leq 1$) om consistentie te waarborgen en een restrictie die garandeert dat elk item met precies $|I|/|G| - 1$ andere items gegroepeerd is.
   • Sterkte: Branching vindt plaats op item-item toewijzingen ($z_{ij}$), die de objectieve functie direct beïnvloeden. De LP relaxatie is aanzienlijk sterker omdat restricties het aantal paren per item beperken tot de groepsgrootte.
   • Beperking: Oorspronkelijk ontworpen voor alleen even grote groepen.

3. Gecombineerde Formulering:

   • Mechanisme: Combineert de standaard formulering met de Papenberg en Klau benadering door $z_{ij} = \sum_{g \in G} y_{ijg}$ te koppelen.
   • Bijdrage: Voegt transitiviteitsrestricties toe aan het standaard model en past de groepsgrootte-restricties aan voor variërende groottes. Het artikel bewijst dat voor even grote groepen deze formulering een LP relaxatie heeft die minstens zo sterk is als de Papenberg en Klau formulering.

4. Aangepaste Papenberg en Klau Formulering (voor variërende groepsgroottes):

   • Mechanisme: Breidt de Papenberg en Klau methode uit om variërende groepsgroottes ($l_g \neq u_g$) aan te pakken door een "dummy item" voor elke groep te introduceren.
   • Variabelen: Items worden toegewezen aan dummy items (die groepen representeren) via $z_{i, \text{dummy}}$.
   • Restricties: Transitiviteitsrestricties zijn van toepassing op alle items, inclusief de dummies. Restricties zorgen ervoor dat elk echt item aan precies één dummy groep is toegewezen, en dat de grootte van de cluster rond elke dummy voldoet aan $l_g$ en $u_g$.

Belangrijkste Bijdragen

• Vergelijkende Analyse: Het artikel biedt een theoretische en empirische vergelijking van de standaard item-groep toewijzingsformulering versus de item-item toewijzingsformulering.
• Theoretisch Inzicht: Het demonstreert dat branching op item-item toewijzingsvariabelen ($z_{ij}$) superieur is aan branching op item-groep toewijzingsvariabelen ($x_{ig}$), omdat de eerste de waarde van de objectieve functie direct beperkt en een strakkere LP relaxatie oplevert.
• Nieuwe Formuleringen: Er worden twee nieuwe formuleringen gepresenteerd om het algemene geval van variërende groepsgroottes aan te pakken, waarmee de toepasbaarheid van de sterkere item-item toewijzingslogica wordt uitgebreid.
• Symmetrie Breken: Het artikel bespreekt en draagt symmetrie-brekende restricties over naar het algemene geval voor de standaard formulering.

Computationele Resultaten

Een uitgebreide computationele studie werd uitgevoerd met CPLEX 12.9 op instanties variërend van 10 tot 30 items en 2 tot 10 groepen. Zowel scenario's met even grote groepen als scenario's met variërende groepsgroottes werden getest.

• Kwaliteit van de LP Relaxatie: De Papenberg en Klau formulering en haar aanpassingen produceerden consequent aanzienlijk strakkere bovengrenzen (kleinere gaten) vergeleken met de standaard formulering. De LP relaxatie gaten van de standaard formulering waren vaak meer dan 100%, terwijl de item-item formuleringen veel lager bleven.
• Oplossingsprestaties:
  • Even Grote Groepen: De Papenberg en Klau formulering loste bijna alle instanties sneller op tot optimaliteit dan de standaard formulering.
  • Variërende Groepsgroottes: De aangepaste Papenberg en Klau formulering (Sectie 3.4) presteerde het best, waarbij instanties met tot 30 items oploste tot optimaliteit of met kleine gaten binnen de 1800-seconden tijdlimiet.
  • Standaard Formulering: Had aanzienlijke problemen, loste vaak niet op tot optimaliteit of slaagde er niet in de gap te sluiten voor instanties met meer dan 15 items binnen de tijdlimiet.
  • Gecombineerde Formulering: Hoewel theoretisch sterk, vertoonde de gecombineerde formulering geen substantiële prestatieverbetering ten opzichte van de standaard formulering wanneer er op $x_{ig}$ variabelen wordt gebrancht, wat suggereert dat de transitiviteitsrestricties alleen onvoldoende zijn om de zwakte van de item-groep branching strategie te overwinnen.

Betekenis en Claims

Het artikel claimt dat de primaire drijfveer voor de superieure prestaties van de nieuwe formuleringen de branching strategie is. Door te brancheren op item-item toewijzingen in plaats van item-groep toewijzingen, kan de solver de zoekruimte effectiever snoeien vanwege de sterkere LP relaxatie die door transitiviteitsrestricties wordt geboden.

De studie concludeert dat voor het MDGP, vooral in situaties met variërende groepsgroottes, de aanpassing van de Papenberg en Klau formulering de meest effectieve exacte benadering is die momenteel beschikbaar is. Het slaagt erin de voordelen van de item-item toewijzingslogica uit te breiden naar algemene groepsrestricties, waarmee de beperkingen van de decennia oude standaard formulering worden overwonnen. De auteurs merken op dat hoewel de aangepaste formulering het best presteert, instanties met variërende groepsgroottes nog steeds moeilijker op te lossen zijn dan die met even grote groepen, waarschijnlijk door de verhoogde flexibiliteit in de oplossingsruimte.