Pipe-cutting example

A plumber stocks standard lengths of pipe, all of length 19 m. An order arrives for:

  • 12 lengths of 4m
  • 15 lengths of 5m
  • 22 lengths of 6m

How should these lengths be cut from standard stock pipes so as to minimize the number of standard pipes used?

First model

In [4]:
using JuMP, Gurobi, Cbc

scale = 1

N = 16*scale  # upper bound on number of pipes needed

m = Model(solver = CbcSolver())
#m = Model(solver = GurobiSolver(OutputFlag=0))

@variable(m, x[1:3,1:N] >= 0, Int)
@variable(m, z[1:N], Bin)
for j = 1:N
    @constraint(m, 4x[1,j] + 5x[2,j] + 6x[3,j] <= 19)
end
@constraint(m, sum(x[1,j] for j=1:N) >= 12*scale)
@constraint(m, sum(x[2,j] for j=1:N) >= 15*scale)
@constraint(m, sum(x[3,j] for j=1:N) >= 22*scale)
for j = 1:N
    @constraint(m, x[1,j] <= 4z[j])
    @constraint(m, x[2,j] <= 3z[j])
    @constraint(m, x[3,j] <= 3z[j])
end

# symmetry-breaking
for j = 1:N-1
    @constraint(m, z[j] >= z[j+1])
end

@objective(m, Min, sum(z[j] for j=1:N))

@time(solve(m))
  0.020686 seconds (78 allocations: 29.141 KiB)
Out[4]:
:Optimal

Second model (column enumeration)

In [5]:
# all the columns:
A = [ 0 0 1 0 2 1 2 3 4
      0 1 0 2 1 2 2 1 0
      3 2 2 1 1 0 0 0 0 ]
scale = 1000000

m = Model(solver = CbcSolver())
#m = Model(solver = GurobiSolver(OutputFlag=0))

@variable(m, x[1:9] >= 0, Int)
@constraint(m, A*x .>= [12;15;22]*scale)
@objective(m, Min, sum(x))
@time(solve(m))
  0.002343 seconds (75 allocations: 7.422 KiB)
Out[5]:
:Optimal
In [ ]: