feasopt1.gms : An Infeasible Transportation Problem analyzed with Cplex option FeasOpt

Description

This problem finds a least cost shipping schedule that meets
requirements at markets and supplies at factories where demand
exceeds supply using the feature FeasOpt implemented by Copt,
Cplex, and Gurobi.


Small Model of Type : LP


Category : GAMS Model library


Main file : feasopt1.gms

$title An Infeasible Transportation Problem analyzed with option FeasOpt (FEASOPT1,SEQ=314)

$onText
This problem finds a least cost shipping schedule that meets
requirements at markets and supplies at factories where demand
exceeds supply using the feature FeasOpt implemented by Copt,
Cplex, and Gurobi.


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

Keywords: linear programming, transportation problem, scheduling, solver option feasOpt,
          computing minimal relaxation, infeasible problem
$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';

Positive Variable x;

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), 1e-3*c(i,j)*x(i,j));

supply(i).. sum(j, x(i,j)) =l= a(i);

demand(j).. sum(i, x(i,j)) =g= b(j);

Model transport / all /;

option limRow = 0, limCol = 0, solvelink = 5;

Set fom 'feasible relaxation modes' / 0*5 /;
set s 'solvers' / cplex, gurobiold, gurobi, copt /;
set h 'headers' / mstat, sstat, objective, numinfeas, suminfeas, sumsqrinfeas, 
                  demand, supply, mstatrelax, sstatrelax, objrelax /;

* Increase demand by 20% to make model infeasible
b(j) = 1.2*b(j);

Parameter a_(i), b_(j) save original supply and demand;
a_(i) = a(i); b_(j) = b(j)

file fopt / cplex.opt /;
parameter rep(s,fom,h);
loop(s,
   put fopt;
   put_utility 'solver' / '*' / s.tl;
   put_utility 'ren' / s.tl:0:0 '.opt';
   loop(fom,
       transport.optfile = 1;
       a(i) = a_(i); b(j) = b_(j);
*      Allow distribution of relaxation on supply side only
       putClose fopt / 'feasOpt 1' / 'feasOptMode ' fom.tl / 'demand.feaspref 0';
       solve transport using lp minimizing z;
       abort$(sum((i,j), x.infeas(i,j))) 'no variable infeasibilities';
       rep(s,fom,'demand') = sum(j, demand.infeas(j));
*      Allow distribution of relaxation on demand side only
       putClose fopt / 'feasOpt 1' / 'feasOptMode ' fom.tl / 'supply.feaspref 0';
       solve transport using lp minimizing z;
       abort$(sum((i,j), x.infeas(i,j))) 'no variable infeasibilities';
       rep(s,fom,'supply') = sum(i, supply.infeas(i));
*      Allow distribution of relaxation optimally over all constraints
       putClose fopt / 'feasOpt 1' / 'feasOptMode ' fom.tl;
       solve transport using lp minimizing z;
       rep(s,fom,'mstat') = transport.modelstat;
       rep(s,fom,'sstat') = transport.solvestat;
       rep(s,fom,'objective') = transport.objval;
       rep(s,fom,'numinfeas') = transport.numinfes;
       rep(s,fom,'suminfeas') = transport.suminfes;
       rep(s,fom,'sumsqrinfeas') = sum(i, sqr(max(0,supply.l(i)-a(i)))) +
                                   sum(j, sqr(max(0,b(j) - demand.l(j))));
* Adjust supply and demand according to relaxation and expect a feasible model 
       a(i) = a(i) + supply.infeas(i);
       b(j) = b(j) - demand.infeas(j);
       transport.optfile = 0;
       solve transport using lp minimizing z;
       rep(s,fom,'mstatrelax') = transport.modelstat;
       rep(s,fom,'sstatrelax') = transport.solvestat;
       rep(s,fom,'objrelax') = transport.objval;
   )
)
display rep;

Table expected(fom,h)
  mstat sstat demand supply objective suminfeas numinfeas sumsqrinfeas mstatrelax sstatrelax objrelax
0     4     1      0      0        NA   130.000        NA           NA          1          1       NA
1     4     1      0      0   0.15525   130.000        NA           NA          1          1  0.15525
2     4     1      0      0        NA        NA         1           NA          1          1       NA
3     4     1      0      0   0.09675        NA         1           NA          1          1  0.09675
4     4     1      0      0        NA        NA        NA     3380.000          1          1       NA
5     4     1      0      0   0.17130        NA        NA     3380.000          1          1  0.17130
;

Set skip(s,fom,h) 'known incorrect behavior' / gurobiold.5.supply /;
Parameter prec(h) 'precision for rounding'/ #h 4/, result(s,fom,h); prec('sumsqrinfeas') = 1;
result(s,fom,h)$(expected(fom,h) <> NA and not skip(s,fom,h)) = round(abs(expected(fom,h) - rep(s,fom,h)),prec(h));
abort$card(result) result;