# This and related files taken from http://users.iems.northwestern.edu/~4er/amplweb/NEW/LOOP2/index.html
# Modified by Prashant, Meenarli and Devanand
# ----------------------------------------
# GILMORE-GOMORY METHOD FOR
# CUTTING STOCK PROBLEM
# ----------------------------------------
reset;
option solver gurobi;
model csp.mod; #declare the model
data csp.dat; #declare the data
problem Cutting_Opt: Cut, Number, Fill; # name the master problem: variables, objective and constraints
option relax_integrality 1; # ask solver to relax integrality
option presolve 0; # set presolve to 0
problem Pattern_Gen: Use, Reduced_Cost, Width_Limit; # name the subproblem: variables, objective and constraints
option relax_integrality 0; # don't relax integrality in the subproblem (its an IP)
option presolve 1; # presolve enabled
let nPAT := 0; # initialize number of patterns to 0
for {i in WIDTHS} { # generate initial patterns
let nPAT := nPAT + 1;
let nbr[i,nPAT] := floor (roll_width/i);
let {i2 in WIDTHS: i2 <> i} nbr[i2,nPAT] := 0;
};
printf "\nIter Master Subproblem Pattern generated\n";
param iter; # iteration counter (for display)
let iter := 1;
repeat { # main loop starts
solve Cutting_Opt;
let {i in WIDTHS} price[i] := Fill[i].dual; # put the multipliers of demand constraints in Fill
solve Pattern_Gen; # solve the knapsack subproblem
printf "\n%3i%8.2f%13.2e ", iter, Number, Reduced_Cost;
if Reduced_Cost < -0.00001 then { # If reduced cost for the new pattern is less than 0,
# add this pattern to the set of the patterns.
let nPAT := nPAT + 1; # increment the pattern count
let {i in WIDTHS} nbr[i,nPAT] := Use[i]; # add the new pattern to master
}
else break; # stop if no pattern could be found with reduced cost less than 0
for {i in WIDTHS} printf "%3i", Use[i]; # print the new pattern
let iter := iter + 1; # increment iteration counter
};
printf "\n\nLP solution: %7.2f rolls", sum {j in PATTERNS} Cut[j];
printf "\n\nCut ";
printf {j in PATTERNS}: "%7.2f", Cut[j]; # print no. of times each pattern is cut
printf "\n\n";
for {i in WIDTHS} { # print item width and patterns
printf "%3i ", i;
printf {j in PATTERNS}: " %4i", nbr[i,j];
printf "\n";
}
let {j in PATTERNS} Cut[j] := ceil(Cut[j]); # round-up the LP solution
# Print LP solution by rounding it up to nearest integer
printf "\n\nRounded up to integer: %3i rolls", sum {j in PATTERNS} Cut[j];
printf "\n\nCut ";
printf {j in PATTERNS}: "%4i", Cut[j];
printf "\n\n";
for {i in WIDTHS} {
printf "%3i ", i;
printf {j in PATTERNS}: "%4i", nbr[i,j];
printf "\n";
}
# Print total waste in percetage
printf "\nWASTE = %5.2f%%\n\n\n",
100 * (1 - (sum {i in WIDTHS} i * orders[i]) / (roll_width * Number));
option Cutting_Opt.relax_integrality 0; # put integrality constraint back in master problem
option Cutting_Opt.presolve 10; # heavy presolve
solve Cutting_Opt; # solve master problem as an IP
# Print output of master IP, solved using above generated patterns
printf "IP solution using above patterns: %3i rolls", sum {j in PATTERNS} Cut[j];
printf "\n\nCut ";
printf {j in PATTERNS}: "%4i", Cut[j];
printf "\n\n";
for {i in WIDTHS} {
printf "%3i ", i;
printf {j in PATTERNS}: "%4i", nbr[i,j];
printf "\n";
}
printf "\nWASTE = %5.2f%%\n\n",
100 * (1 - (sum {i in WIDTHS} i * orders[i]) / (roll_width * Number));