allbases.gms : Enumerate all Feasible Basic Solutions of the Transportation Problem

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';
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170
GAMS is a registered trademark of GAMS Software GmbH in the European Union