$title Progressive Party Problem -- Full blown model
$ontext

   This model solves the 6 period model.

   Erwin Kalvelagen, june 2001 original model
   Id.             , jan  2007 minor edits

   Note: Older versions of Cplex do better than newer ones.

   Reference:
         Erwin Kalvelagen,
         On solving the progressive party problem as a MIP,
        Computers and Operations Research, Volume 30, Number 11,
         September 2003 , pp. 1713-1726 (14)

$offtext

set i 'boat or crew number' /b1*b42/;

parameter capacity(i) 'max number of guests' /
   b1   6,  b2   8,  b3  12,  b4  12,  b5  12,  b6  12,  b7  12,  b8  10,
   b9  10,  b10 10,  b11 10,  b12 10,  b13  8,  b14  8,  b15  8,  b16 12,
   b17  8,  b18  8,  b19  8,  b20  8,  b21  8,  b22  8,  b23  7,  b24  7,
   b25  7,  b26  7,  b27  7,  b28  7,  b29  6,  b30  6,  b31  6,  b32  6,
   b33  6,  b34  6,  b35  6,  b36  6,  b37  6,  b38  6,  b39  9,  b40  0,
   b41  0,  b42  0
/;

parameter crew(i) 'crew size' /
   b1   2,  b2   2,  b3   2,  b4   2,  b5   4,  b6   4,  b7   4,  b8   1,
   b9   2,  b10  2,  b11  2,  b12  3,  b13  4,  b14  2,  b15  3,  b16  6,
   b17  2,  b18  2,  b19  4,  b20  2,  b21  4,  b22  5,  b23  4,  b24  4,
   b25  2,  b26  2,  b27  4,  b28  5,  b29  2,  b30  4,  b31  2,  b32  2,
   b33  2,  b34  2,  b35  2,  b36  2,  b37  4,  b38  5,  b39  7,  b40  2,
   b41  3,  b42  4
/;

parameter guest_cap(i) 'guest_capacity';
guest_cap(i) = max(capacity(i)-crew(i),0);

set t 'time slot' /t1*t6/;

alias (i,j,ii,jj);
alias (t,tt);

set nd(i,j) 'off-diagonal';
nd(i,j)$(ord(i)<>ord(j)) = yes;

set lti(i,j) 'less-than';
lti(i,j)$(ord(i)<ord(j)) = yes;

variables
     nh             'number of host boats'
     x(i,j,t)       'crew j visits party i at time slot t'
     h(i)           'boat i is a host boat'
     meet(j,jj,t)   'crews j and jj meet at time t'
;
binary variables x,h;

equations
     obj            'objective'
     host(i,j,t)    'parties only on host boats'
     cap(i,t)       'capacity constraint'
     crewhost(j,t)  'crew is a host or is hosted (no idle crews)'
     visitonce(i,j) 'crew can only visit a boat once'
     link(i,j,jj,t) 'calculates meet(j,jj)'
     meetonce(j,jj) 'any pair of guest crews can meet only once'
;

*
* minimize number of host boats
*
obj.. nh =e= sum(i, h(i));

*
* there are only parties on host boats
*
host(nd(i,j),t).. x(i,j,t) =l= h(i);

*
* max number of guest that a host boat can handle
*
cap(i,t).. sum(nd(i,j), crew(j)*x(i,j,t))  =l= guest_cap(i)*h(i);

*
* no idle crews: a crew is either hosting a party, or visiting
* a party
*
crewhost(j,t).. h(j) + sum(nd(i,j), x(i,j,t)) =e= 1;

*
* max one visit to each host boat
*
visitonce(nd(i,j)).. sum(t, x(i,j,t)) =l= h(i);

*
* guest crews can meet only once
* with aid of extra binary variables
*
meet.lo(lti(j,jj), t) = 0;
meet.up(lti(j,jj), t) = 1;
link(i,lti(j,jj),t)$(nd(i,j) and nd(i,jj))..
    meet(j,jj,t) =g= x(i,j,t) + x(i,jj,t) - 1;

meetonce(lti(j,jj)).. sum(t, meet(j,jj,t)) =l= 1;

*
* some boats are designated host boats
*
set must_be_host(i) /b1,b2,b3/;
h.fx(must_be_host) = 1;

*
* some boats are designated guest boats
* (the virtual boats).
*
set must_be_guest(i) /b40,b41,b42/;
h.fx(must_be_guest) = 0;

*
* make sure boats with very limited guest capacity are never
* selected as host boats
* (this will include the virtual boats, so what)
* This fix is not reducing the size of the model for this dataset.
scalar mincrew 'smallest crew';
mincrew = smin(j, crew(j));
h.fx(i)$(guest_cap(i) < mincrew) = 0;

*
* it can be shows that 12 host boats is not enough
* to handle even a single period. Try to find a schedule
* with 13 boats.
*
nh.fx = 13;

model m  /all/;


* increase iteration and time limit
option iterlim=1000000;
option reslim=100000;

option mip=cplex;

*
* cplex option file
*
$onecho > cplex.opt
heurfreq -1
mipinterval 1
startalg 1
subalg 1
mipemphasis 4
fraccuts -1
$offecho
m.optfile=1;

solve m using mip minimizing nh;

display nh.l,h.l,x.l;

*
* sanity check
*
parameter meetcount(j,jj);
meetcount(nd(j,jj)) = sum((i,t), x.l(i,j,t)*x.l(i,jj,t));
abort$sum((j,jj)$(meetcount(j,jj) > 1.5),1) "meeting condition is not met";