This notebook contains course material from CBE40455 by Jeffrey Kantor (jeff at nd.edu); the content is available on Github. The text is released under the CC-BY-NC-ND-4.0 license, and code is released under the MIT license.
This IPython notebook demonstrates the formulation and solution of stock cutting problems using GLPK/Mathprog.
The stock cutting problem is to minimize the waste associated with cutting up stock materials to produce a set of products. Examples of the one dimensional problem include cutting lengths of steel bar into a set of products, cutting wide paper rolls into smaller ones, and cutting dimensioned lumber to meet the production needs of furniture shops.
In large scale applications the stock cutting problem begins with a base set of cutting patterns. Each cutting pattern breaks a piece of stock into a set of products. The base calculation is to find a mix of cutting patterns to meet product requirements. A secondary problem is solved to find additional cutting patterns with the potential to reduce costs. The solution then proceeds iteratively with new patterns are generated 'on the fly' coupled with a branch and bound search to find an optimal solution. This approach is called 'column generation.'
As demonstrated below, for small scale problems the stock cutting problem can be formulated as an assignment of product pieces to stock pieces. For this example the data consists of a list of product types, lengths and demand. The example incorporates multiple types of raw materials. The objective is to maximize the number of pieces of stock material that are left uncut.
An aspect of this problem is the high degree of solution symmetry. The number of equivalent solutions is a combinatorial function of the number of identical pieces of raw of materials. In these cases a solver may quickly find a solution but then need to search many equivalent solutions to verify optimality. This example uses a weighted objective to separate otherwise equivalent solutions.
To repeat, this approach will not work for larger problems due to the excessive number of binary variables required and high degree of solution symmetry. Consult the cspsol project for a solution method using column generation and glpk api.
!apt-get install glpk-utils -qq
%%writefile input.dat
data;
param bigM := 20;
param: PRODUCTS: pLength demand :=
'7m' 7 3
'6m' 6 2
'4m' 4 6
'3m' 3 1 ;
param: RAWMATERIALS: rLength avail :=
'15m' 15 3
'10m' 10 3 ;
end;
Overwriting input.dat
%%script glpsol -m /dev/stdin -d input.dat -y output.txt
# Stock Cutting Problem
# Products
set PRODUCTS;
param pLength{PRODUCTS};
param demand{PRODUCTS};
# Raw Materials
set RAWMATERIALS;
param rLength{RAWMATERIALS};
param avail{RAWMATERIALS};
# Big M should be greater than the length of any stock piece
param bigM;
check {r in RAWMATERIALS} : bigM > rLength[r];
# Create indexed sets enumerating all production pieces
set Q{p in PRODUCTS} := 1..demand[p] ;
# Create indexed sets enumerating all raw material pieces
set S{r in RAWMATERIALS} := 1..avail[r];
# y[p,q,r,s] = 1 assigns (product p, piece q) to (raw material r, piece s)
var y{p in PRODUCTS, q in Q[p], r in RAWMATERIALS, s in S[r]} binary;
# u[r,s] = 1 indicates use of (raw material r, piece s)
var u{r in RAWMATERIALS, s in S[r]} binary;
# w[r,s] is the remainder left over from (raw material r, piece s)
var w{r in RAWMATERIALS, s in S[r]} >= 0;
# Assign product (p,q) only once to the set of all raw materials (r,s)
s.t. A{p in PRODUCTS, q in Q[p]} : sum{r in RAWMATERIALS, s in S[r]} y[p,q,r,s] = 1;
# Cut enough pieces to exactly meet the demand for each product
s.t. B{p in PRODUCTS} : sum{q in Q[p], r in RAWMATERIALS, s in S[r]} y[p,q,r,s] = demand[p];
# Do not exceed the length each piece of raw material
s.t. C{r in RAWMATERIALS, s in S[r]} :
sum{p in PRODUCTS, q in Q[p]} pLength[p]*y[p,q,r,s] + w[r,s] = rLength[r];
# Determine if a piece (r,s) of raw material is used.
s.t. D{r in RAWMATERIALS, s in S[r]} : bigM*u[r,s] >= sum{p in PRODUCTS, q in Q[p]} y[p,q,r,s];
minimize Pieces : sum{r in RAWMATERIALS, s in S[r]} rLength[r]*s*u[r,s];
solve;
table products {p in PRODUCTS} OUT "CSV" "Products.csv" "Table" :
p~Product, pLength[p]~Length, demand[p]~Demand;
table rawmaterials {r in RAWMATERIALS} OUT "CSV" "Raw_Materials.csv" "Table" :
r~Raw_Materials, rLength[r]~Length, avail[r]~Available;
printf "Cutting Plan\n";
for {r in RAWMATERIALS} : {
printf " Raw Material %s \n", r;
for {s in S[r]} : {
printf " Piece %s-%d : Remainder = %5.2f : Cut product pieces ", r,s, w[r,s];
for {p in PRODUCTS} : {
for {q in Q[p] : y[p,q,r,s]} : {
printf "%s-%d ", p, q;
}
}
printf "\n";
}
printf "\n";
}
printf "Production Plan\n";
for {p in PRODUCTS} : {
printf " Product %s \n", p;
for {q in Q[p]} : {
printf " Piece %s-%d : Cut from stock piece ", p, q;
for {r in RAWMATERIALS} : {
for {s in S[r] : y[p,q,r,s]} : {
printf "%s-%d ", r, s;
}
}
printf "\n";
}
printf "\n";
}
end;
GLPSOL: GLPK LP/MIP Solver, v4.65 Parameter(s) specified in the command line: -m /dev/stdin -d input.dat -y output.txt Reading model section from /dev/stdin... 86 lines were read Reading data section from input.dat... input.dat:16: warning: final NL missing before end of file 16 lines were read Checking (line 16)... Generating A... Generating B... Generating C... Generating D... Generating Pieces... Model has been successfully generated GLPK Integer Optimizer, v4.65 29 rows, 84 columns, 306 non-zeros 78 integer variables, all of which are binary Preprocessing... 6 constraint coefficient(s) were reduced 28 rows, 78 columns, 294 non-zeros 78 integer variables, all of which are binary Scaling... A: min|aij| = 1.000e+00 max|aij| = 1.200e+01 ratio = 1.200e+01 GM: min|aij| = 8.091e-01 max|aij| = 1.236e+00 ratio = 1.528e+00 EQ: min|aij| = 6.547e-01 max|aij| = 1.000e+00 ratio = 1.528e+00 2N: min|aij| = 3.750e-01 max|aij| = 1.500e+00 ratio = 4.000e+00 Constructing initial basis... Size of triangular part is 24 Solving LP relaxation... GLPK Simplex Optimizer, v4.65 28 rows, 78 columns, 294 non-zeros 0: obj = 0.000000000e+00 inf = 3.650e+01 (2) 27: obj = 2.961309524e+01 inf = 6.328e-15 (0) * 61: obj = 1.920138889e+01 inf = 1.031e-15 (0) OPTIMAL LP SOLUTION FOUND Integer optimization begins... Long-step dual simplex will be used + 61: mip = not found yet >= -inf (1; 0) Solution found by heuristic: 140 Solution found by heuristic: 120 + 18758: >>>>> 1.050000000e+02 >= 1.050000000e+02 0.0% (11; 14610) + 18758: mip = 1.050000000e+02 >= tree is empty 0.0% (0; 14643) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.9 secs Memory used: 0.7 Mb (690133 bytes) Writing products... Writing rawmaterials... Model has been successfully processed
f = open("output.txt")
print(f.read())
f.close()
Cutting Plan Raw Material 15m Piece 15m-1 : Remainder = 0.00 : Cut product pieces 7m-1 4m-5 4m-6 Piece 15m-2 : Remainder = 0.00 : Cut product pieces 7m-3 4m-1 4m-4 Piece 15m-3 : Remainder = 15.00 : Cut product pieces Raw Material 10m Piece 10m-1 : Remainder = 0.00 : Cut product pieces 6m-2 4m-3 Piece 10m-2 : Remainder = 0.00 : Cut product pieces 6m-1 4m-2 Piece 10m-3 : Remainder = 0.00 : Cut product pieces 7m-2 3m-1 Production Plan Product 7m Piece 7m-1 : Cut from stock piece 15m-1 Piece 7m-2 : Cut from stock piece 10m-3 Piece 7m-3 : Cut from stock piece 15m-2 Product 6m Piece 6m-1 : Cut from stock piece 10m-2 Piece 6m-2 : Cut from stock piece 10m-1 Product 4m Piece 4m-1 : Cut from stock piece 15m-2 Piece 4m-2 : Cut from stock piece 10m-2 Piece 4m-3 : Cut from stock piece 10m-1 Piece 4m-4 : Cut from stock piece 15m-2 Piece 4m-5 : Cut from stock piece 15m-1 Piece 4m-6 : Cut from stock piece 15m-1 Product 3m Piece 3m-1 : Cut from stock piece 10m-3
import pandas
pandas.read_csv("Products.csv")
Product | Length | Demand | |
---|---|---|---|
0 | 7m | 7 | 3 |
1 | 6m | 6 | 2 |
2 | 4m | 4 | 6 |
3 | 3m | 3 | 1 |
pandas.read_csv("Raw_Materials.csv")
Raw_Materials | Length | Available | |
---|---|---|---|
0 | 15m | 15 | 3 |
1 | 10m | 10 | 3 |