nemhaus.gms : Scheduling to Minimize Interaction Cost

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.


Reference

  • Carlson, R C, and Nemhauser, G L, Scheduling to Minimize Interaction Cost. Operations Research 14, 1 (1966), 52-58.

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;