Description
Activities can be scheduled on different facilities. If two activities are scheduled on the same facility, an interaction cost occurs. This has originally be formulated as a 0/1 quadratic programming problem. In addition, an MIP formulations is explored and the models are solved for all possible facilities.
Small Model of Types : MIP nlp
Category : GAMS Model library
Main file : nemhaus.gms
$title Scheduling to Minimize Interaction Cost (NEMHAUS,SEQ=194)
$onText
Activities can be scheduled on different facilities. If two activities
are scheduled on the same facility, an interaction cost occurs. This
has originally be formulated as a 0/1 quadratic programming problem.
In addition, an MIP formulations is explored and the models are solved
for all possible facilities.
Carlson, R C, and Nemhauser, G L, Scheduling to Minimize Interaction Cost.
Operations Research 14 (1966), 52-58.
Keywords: nonlinear programming, mixed integer linear programming, scheduling,
assignment problem
$offText
$eolCom //
Set
i 'activities'
jj 'facilities'
j(jj) 'dynamic subset of facilities';
Alias (i,k);
Parameter a(i,k) 'cost of scheduling activity i and k on same facility';
Variable
z 'total interaction cost'
x(i,jj) 'activity i scheduled on facility j'
y(i,jj,k) 'product of x*x'
xb(i,jj) '0-1 version of x';
Binary Variable xb;
Positive Variable x, y;
Equation
zdef 'objective definition'
sch(i) 'schedule all activities'
bzdef 'objective definition'
bsch(i) 'schedule for binary version'
ydef(i,jj,k) 'definition of product';
Model
one 'QP formulation' / zdef, sch /
two 'MIP formulation' / bzdef, bsch, ydef /;
zdef.. z =e= sum((i,j,k), x(i,j)*a(i,k)*x(k,j));
sch(i).. sum(j, x(i,j)) =e= 1;
bzdef.. z =e= sum((i,j,k), a(i,k)*y(i,j,k));
bsch(i).. sum(j, xb(i,j)) =e= 1;
ydef(i,j,k)$a(i,k).. y(i,j,k) =g= xb(i,j) + xb(k,j) - 1;
* original data
Set
i 'j' / act-1*act-5 /
jj / fac-1*fac-5 /;
Table a(i,k) 'interaction cost'
act-1 act-2 act-3 act-4 act-5
act-1 2 4 3
act-2 6 2 3
act-3 2 6 5 3
act-4 4 2 5 3
act-5 3 3 3 3 ;
$onText
note the local solution to the NLP in case of
4 facilities:
local optimum interaction cost = 1.5
(act-1,act-2).fac-1 1.0000
(act-3,act-5).fac-2 0.5000
(act-4 ).fac-3 1.0000
(act-3,act-5).fac-4 0.5000
global optimum interaction cost = 0.0
(act-1,act-2).fac-1 1.0000
(act-3 ).fac-2 1.0000
(act-4 ).fac-3 1.0000
(act-5 ).fac-4 1.0000
$offText
* 20 activities data set
$onText
Set
i 'j' / a-01*a-20 /
jj / f-01*f-20 /;
Table a(i,k) 'interaction cost'
a-01 a-02 a-03 a-04 a-05 a-06 a-07 a-08 a-09 a-10 a-11 a-12 a-13 a-14 a-15 a-16 a-17 a-18 a-19 a-20
a-01 8 4 18 8 3 19 4 17 6 9 7 6 10 5 7
a-02 8 4 7 1 5 11 10 4 10 2 7 4 13 4 7
a-03 4 3 1 5 9 16 5 15 4 4 9 3 7 14
a-04 3 2 3 4 11 1 9 3 2 9 1 7 5 6 3
a-05 4 2 4 9 17 13 1 1 14 2 12 7 1 4
a-06 7 1 3 4 5 13 1 2 6 2 1 13 4
a-07 1 5 4 5 10 9 14 4 4 5 8 4 5 5 1
a-08 18 5 9 11 9 5 13 7 3 6 5 12 4 7 5
a-09 8 11 16 1 10 9 2 10 10 3 7 3 3 11 4 7
a-10 3 17 13 9 5 9 14 6 14 8 2 1 7 4 1 3
a-11 19 5 9 13 1 14 13 2 14 6 11 11 11 9 5 4
a-12 4 10 15 3 1 2 4 7 10 6 6 6 11 6 10 8 4 6 9
a-13 17 4 4 2 1 6 10 14 11 6 16 7 17 5
a-14 6 10 9 14 2 4 3 3 8 11 5 10 10 3 9 6
a-15 9 2 1 2 1 5 6 7 2 11 6 16 5 12 18 13 8 9
a-16 7 7 4 7 12 13 8 5 3 1 11 10 7 10 12 14 5 5 11
a-17 6 4 9 5 4 12 3 7 8 17 10 18 14 8 2
a-18 10 13 3 7 5 4 11 4 9 4 3 13 5 6
a-19 5 4 7 6 1 5 7 4 1 5 6 5 9 8 5 8 3
a-20 7 7 14 3 4 4 1 5 7 3 4 9 6 9 11 2 6 3 ;
$offText
* make random data
$onText
sets i / a-01*a-20 /
jj / f-01*f-20 /;
a(i,k) = max(0,uniform(-5 ,10));
a(i,k) = round(a(i,k) + a(k,i));
a(i,i) = 0;
$offText
a(i,k)$(ord(i) > ord(k)) = 0; // exploit symmetry
// set some global options
option limCol = 0 // no activity listing
limRow = 0 // no row listing
resLim = 10 // set max running time for solver
optCr = 0.001 // set mip relative criterion
solPrint = off; // turn solprint off
Parameter objval(jj,*) 'objective values';
Scalar more;
// expand facilities until we have no conflicts
j(jj) = no;
more = 1;
loop(jj$more,
j(jj) = yes;
solve one using nlp min z;
objval(jj,'nlp') = z.l;
more = z.l;
solve two using mip min z;
objval(jj,'mip') = z.l;
more = more or z.l;
);
display objval;