Description

This problem finds a least cost shipping schedule that meets
requirements at markets and supplies at factories. We reformulte in standard
form use binary variables to determine if a variable belongs to the basis or
not. Then we use binary cuts to enumerate all feasible basic solutions in the
sort order of the objective function.

Dantzig, G B, Chapter 3.3. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.

Keywords: linear programming, transportation problem, scheduling, complete
          enumeration, micro economics

Small Model of Type : MIP

Category : GAMS Model library

Main file : allbases.gms

$title Enumerate all Feasible Basic Solutions of the Transportation Problem (ALLBASES,SEQ=396)

$onText
This problem finds a least cost shipping schedule that meets
requirements at markets and supplies at factories. We reformulte in standard
form use binary variables to determine if a variable belongs to the basis or
not. Then we use binary cuts to enumerate all feasible basic solutions in the
sort order of the objective function.

Dantzig, G B, Chapter 3.3. In Linear Programming and Extensions.
Princeton University Press, Princeton, New Jersey, 1963.

Keywords: linear programming, transportation problem, scheduling, complete
          enumeration, micro economics
$offText

Set
   i 'canning plants' / seattle,  san-diego /
   j 'markets'        / new-york, chicago, topeka /;

Parameter
   a(i) 'capacity of plant i in cases'
        / seattle    350
          san-diego  600 /

   b(j) 'demand at market j in cases'
        / new-york   325
          chicago    300
          topeka     275 /;

Table d(i,j) 'distance in thousands of miles'
              new-york  chicago  topeka
   seattle         2.5      1.7     1.8
   san-diego       2.5      1.8     1.4;

Scalar f 'freight in dollars per case per thousand miles' / 90 /;

Parameter c(i,j) 'transport cost in thousands of dollars per case';
c(i,j) = f*d(i,j)/1000;

Variable
   x(i,j)    'shipment quantities in cases'
   z         'total transportation costs in thousands of dollars'
   sslack(i) 'slack for supply constraint'
   dslack(j) 'slack for demand constraint';

Positive Variable x, sslack, dslack;

Equation
   cost      'define objective function'
   supply(i) 'observe supply limit at plant i'
   demand(j) 'satisfy demand at market j';

cost..      z =e= sum((i,j), c(i,j)*x(i,j));

supply(i).. sum(j, x(i,j)) =e= a(i) - sslack(i);

demand(j).. sum(i, x(i,j)) =e= b(j) + dslack(j);

* Basis definition
Variable
   xind(i,j) 'x basis indicator'
   sslind(i) 'sslack basis indicator'
   dslind(j) 'dslack basis indicator';

Binary Variable xind, sslind, dslind;

Equation
   defbasis     'basis definition'
   defximp(i,j) 'xind=0 => x=0'
   defsslimp(i) 'sslind=0 => ssl=0'
   defdslimp(j) 'dslind=0 => dsl=0';

defbasis.. card(i) + card(j) =e= sum((i,j), xind(i,j)) + sum(i, sslind(i)) + sum(j, dslind(j));

defximp(i,j).. x(i,j)    =l= min(a(i),b(j))*xind(i,j);

defsslimp(i).. sslack(i) =l= a(i)*sslind(i);

defdslimp(j).. dslack(j) =l= b(j)*dslind(j);

* Cut definition
$onEmpty
Set
   nb          'basis enumeration cuts' / b1*b22 /
   nba(nb)     'active cuts'            /        /
   dslcc(nb,j) 'cut coefficients'       /        /
   xcc(nb,i,j)                          /        /
   sslcc(nb,i)                          /        /;
$offEmpty

Equation defcut(nb) 'cut';
defcut(nba)..
         card(i)*card(j) + card(i) + card(j) - 1
   =g=   sum((i,j)$xcc(nba,i,j), xind(i,j)) + sum((i,j)$(not xcc(nba,i,j)), 1 - xind(i,j))
       + sum(i$sslcc(nba,i), sslind(i))     + sum(i$(not sslcc(nba,i)),     1 - sslind(i))
       + sum(j$dslcc(nba,j), dslind(j))     + sum(j$(not dslcc(nba,j)),     1 - dslind(j));

Model transport / all /;

Parameter rep;

option optCr = 0, solveLink = 5, limRow = 0, limCol = 0, solPrint = silent;

loop(nb,
   solve transport using mip minimizing z;
   xcc(nb,i,j) = round(xind.l(i,j));
   sslcc(nb,i) = round(sslind.l(i));
   dslcc(nb,j) = round(dslind.l(j));

   break$(transport.modelStat <> %modelStat.optimal%);

   rep(nb,'obj','','') = z.l;
   rep(nb,'supply.m',i,'') = supply.m(i);
   rep(nb,'demand.m',j,'') = demand.m(j);
   rep(nb,'x.l',i,j) = x.l(i,j);
   rep(nb,'x.m',i,j) = x.m(i,j);
   nba(nb) = yes;
);
abort$(card(nba) = card(nb)) 'Set nb too small. Feasible basic solutions so far:', rep;
abort$(abs(rep('b21','obj','','')-177.525) > 1e-6) 'incorrect last solution';