A plumber stocks standard lengths of pipe, all of length 19 m. An order arrives for:
How should these lengths be cut from standard stock pipes so as to minimize the number of standard pipes used?
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)
:Optimal
# 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)
:Optimal