(socialGolfer1)

Run LPL Code  ,  PDF Document

Problem

A number of golfers, each of whom plays golf once a week, are partioned into groups of given size. One needs to schedule the groups in such a way that each player meets a maximum of other players in his groups (maximal socialization). Another formulation is found in model golfers. The model is explained in my (see Puzzle Book.)

Modeling Steps

Let m be a number of groups, n the group size and k a number of weeks. Define a set of weeks as w W = {1,,k}, a set of groups as g G = {1,,n}, and a set of players as i,j I = {1,,n m}. The binary variable xw,i,g is 1 if player i is in group g at week w.

  1. Constraint one is: each week w, each golfer i is assigned to exactly one group g:

    ∑
    xw,g,i = 1   forall w ∈ W, i ∈ I
  g
  2. Constraint two is: each week w, each group g contains exactly n golfers:

    ∑
   xw,g,i = n   forall w ∈ W, g ∈ G
 i
  3. Let Mw,g,i,j with j > i be true (1) if golfers i and j meet in group g on week w:

    Mw,g,i = xw,g,i ∧  xw,g,j   forall w ∈ W, g ∈ G, i,j ∈ I, j > i
  4. Let nMi,j be the number of meetings between golfers i and j

            ∑
nMi,j =     Mw,g,i,j   forall i,j ∈ I, j > i
         w,g
  5. Let maxMi,j be the maximum of meetings (minus one) between golfers i and j:

    maxMi,j  =  max (nMi,j - 1,0)   forall i,j ∈ I,j >  i
  6. The maximal meeting over all meetings must be minimal:

          ∑
min       maxMi,j

     i,j|j>i

Listing 1: The Complete Model implemented in LPL [2]
model socialGolver; 
  /*$C*/ 
  parameter nbGroups; groupSize; nbWeeks; 
  Read('c_4_3_3.in', nbGroups, groupSize, nbWeeks); 
  --Read('instances/c_10_8_4.in', nbGroups, groupSize, nbWeeks); 
  parameter nbGolfers := nbGroups * groupSize; 
  set w:=1..nbWeeks; 
  set g:=1..nbGroups; 
  set i,j:=1..nbGolfers; 
  binary variable x{w,g,i}; 
  constraint A{w,i}: sum{g} x[w,g,i] = 1; 
  constraint B{w,g}: sum{i} x[w,g,i] = groupSize; 
  expression meetings{w,g,i,j|j>i}: x[w,g,i] and x[w,g,j]; 
    nbMeetings{i,j|j>i}: sum{w,g} meetings[w,g,i,j]; 
    redundantMeetings{i,j|j>i}: Max(nbMeetings[i,j] -1, 0); 
  minimize obj: sum{i,j|j>i} redundantMeetings[i,j]; 
  Write('obj: %d' n', obj); 
  Write('The group of players is as follows:' n' n'); 
  Write(' %-14s' n',{w}('Week '&w)); 
  Write{g}('Group %s %-14s' n',g, 
    {w}Strreplace(Format('(%s)',{i|x}(i&',')),',)',')')); 
end

LPL generates the following model code for the LocalSolver

/ LSP file (LocalSolver.com) :: automatically generated by LPL 
use io; 
function input() { 
  groupSize = 3; 
  WW = 3; 
  GG = 4; 
  II = 12; 
} 
 
function model() { 
  x[w in 0..WW-1][g in 0..GG-1][i in 0..II-1] <- bool(); 
  for[w in 0..WW-1][i in 0..II-1] 
    constraint  sum [g in 0..GG-1] (x[w][g][i]) ==1; 
  for[w in 0..WW-1][g in 0..GG-1] 
    constraint  sum [i in 0..II-1] (x[w][g][i]) ==groupSize; 
  meetings[w in 0..WW-1][g in 0..GG-1][i in 0..II-1][j in 0..II-1 : j>i] <-  and (x[w][g][i],x[w][g][j]); 
  nbMeetings[i in 0..II-1][j in 0..II-1 : j>i] <-  sum [w in 0..WW-1][g in 0..GG-1] (meetings[w][g][i][j]) ; 
  redundantMeetings[i in 0..II-1][j in 0..II-1 : j>i] <- max (nbMeetings[i][j]-1,0); 
  obj <-  sum [i in 0..II-1][j in 0..II-1 : j>i] (redundantMeetings[i][j]) ; 
  minimize obj; 
} 
 
function param() { 
  if (lsTimeLimit == nil) lsTimeLimit = 20; 
  lsVerbosity = 2; 
} 
 
function output() { 
  if (solFileName == nil) return; 
  local solFile = io.openWrite(solFileName); 
  solFile.println(getSolutionStatus()); 
  solFile.println(obj.value); 
  solFile.print("x: "); 
  for[w in 0..WW-1][g in 0..GG-1][i in 0..II-1] solFile.print(x[w][g][i].value,","); 
  solFile.println(); 
}

Solution

For the “c_4_3_3.in” instance the output is

  obj: 0
  The group of players is as follows:

           Week 1        Week 2        Week 3
  Group 1 (2,3,9)       (5,7,9)       (2,10,11)
  Group 2 (1,4,7)       (3,4,11)      (1,8,9)
  Group 3 (5,8,10)      (1,10,12)     (3,6,7)
  Group 4 (6,11,12)     (2,6,8)       (4,5,12)

References

[1]   MatMod. Homepage for Learning Mathematical Modeling :  https://matmod.ch.

[2]   Hürlimann T. Reference Manual for the LPL Modeling Language, most recent version. https://matmod.ch/lpl/doc/manual.pdf.