# Progressive Party Problem -- Full blown model
#
# This model can be solved on NEOS using AMPL/Feaspump
#
# 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)

param n 'number of boats' > 0;

set I := {1..n};

param nt 'number of time periods' > 0;

set T := {1..nt};

param capacity 'max number of guests' {I}  >= 0;

param crew 'crew size' {I}  > 0;

param guest_cap 'guest_capacity' {i in I}
   := if capacity[i]-crew[i]>0 then capacity[i]-crew[i] else 0;


set must_be_host := {1,2,3};

set must_be_guest := {40,41,42};

var nh   'number of host boats' >= 13 <= 13;
var x    'visit' {i in I,j in I,T:i<>j} binary;
var h    'host boat' {I} binary;
var meet 'crews meet' {i in I,j in I,T:i<j} >= 0 <= 1;

minimize obj : nh;

#
#  minimize number of host boats
#
numhostboats:
   nh = sum{i in I} h[i];

#
# there are only parties on host boats
#
host{i in I, j in I, t in T: i<>j}:
   x[i,j,t] <= h[i];

#
# max number of guest that a host boat can handle
#
cap{i in I, t in T}:
   sum{j in I: i<>j} crew[j]*x[i,j,t] <= guest_cap[i]*h[i];

#
# no idle crews: a crew is either hosting a party, or visiting
# a party
#
crewhost{j in I, t in T}:
   h[j] + sum{i in I: i<>j} x[i,j,t] = 1;

#
# max one visit to each host boat
#
visitonce{i in I, j in I: i<>j}:
   sum{t in T} x[i,j,t] <= h[i];

#
# guest crews can meet only once
# with aid of extra binary variables
#
link{i in I, j in I, jj in I, t in T: i<>j and i<>jj and j<jj}:
   meet[j,jj,t] >= x[i,j,t] + x[i,jj,t] - 1;

meetonce{j in I, jj in I: j<jj}:
   sum{t in T} meet[j,jj,t] <= 1;

#
# some boats are designated host boats
#
mustbehost{i in must_be_host}:
   h[i] = 1;

#
# some boats are designated guest boats
# (the virtual boats).
#
mustbeguest{i in must_be_guest}:
   h[i] = 0;

data;

param n := 42;
param nt := 6;

param : capacity  crew :=
    1      6        2
    2      8        2
    3     12        2
    4     12        2
    5     12        4
    6     12        4
    7     12        4
    8     10        1
    9     10        2
   10     10        2
   11     10        2
   12     10        3
   13      8        4
   14      8        2
   15      8        3
   16     12        6
   17      8        2
   18      8        2
   19      8        4
   20      8        2
   21      8        4
   22      8        5
   23      7        4
   24      7        4
   25      7        2
   26      7        2
   27      7        4
   28      7        5
   29      6        2
   30      6        4
   31      6        2
   32      6        2
   33      6        2
   34      6        2
   35      6        2
   36      6        2
   37      6        4
   38      6        5
   39      9        7
   40      0        2
   41      0        3
   42      0        4
;