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;