An error when solving cutting stock problem

[YP-Ye]

It seems to converge to the global optimal solution. However an error appears at last. Here is my code:

using Coluna, BlockDecomposition, JuMP
using CPLEX

sheet_sizes = [120]
items = 1:10
demands = [10 11 11 12 12 12 10 11 12 10]
widths = [92 59 97 32 38 55 80 75 108 57]
@axis(Patterns, 1:120)

coluna = optimizer_with_attributes(
    Coluna.Optimizer,
    "params" => Coluna.Params(
        solver = Coluna.Algorithm.TreeSearchAlgorithm(), # default BCP
        max_nb_processes = 10000,
        max_nb_formulations = 10000
    ),
    "default_optimizer" => CPLEX.Optimizer # GLPK for the master & the subproblems
)

model = BlockModel(coluna, bridge_constraints = false)
@variable(model, 0 <= x[i in items, s in Patterns] <= demands[i], Int)
@variable(model, y[s in Patterns], Bin)
@constraint(model, cov[i in items], sum(x[i,s] for s in Patterns) >= demands[i])
@constraint(model, knp[s in Patterns], sum(widths[i]*x[i,s] for i in items) <= sheet_sizes[1]*y[s])
@objective(model, Min, sum(y[s] for s in Patterns))

@dantzig_wolfe_decomposition(model, dec, Patterns)
subproblems = BlockDecomposition.getsubproblems(dec)
optimize!(model)

It is the output.

Coluna
Version 0.3 - https://github.com/atoptima/Coluna.jl
┌ Warning: No initial primal bound and no cost for global artificial variables.
│ Cost of global artificial variables set to 100000.0
└ @ Coluna C:\Users\Administrator\.juliapro\JuliaPro_v1.2.0-1\packages\Coluna\YZZg2\src\optimize.jl:20
┌ Warning: No initial primal bound and no cost for local artificial variables.
│ Cost of local artificial variables set to 10000.0
└ @ Coluna C:\Users\Administrator\.juliapro\JuliaPro_v1.2.0-1\packages\Coluna\YZZg2\src\optimize.jl:33
[ Info: Coluna ready to start.
[ Info: Coluna.Params(10000, 100000, 1.0e-8, 8, Inf, -Inf, 100000.0, 10000.0, false, Coluna.Algorithm.TreeSearchAlgorithm(Coluna.Algorithm.ColGenConquer(Coluna.Algorithm.ColumnGeneration(1000, 1.0e-5, 1, false), Coluna.Algorithm.SolveIpForm(600, true, true, 1), Coluna.Algorithm.PreprocessAlgorithm(), true, false), Coluna.Algorithm.StrongBranching(Coluna.Algorithm.BranchingPhase[], Coluna.Algorithm.PrioritisedBranchingRule[Coluna.Algorithm.PrioritisedBranchingRule(1.0, 1.0, Coluna.Algorithm.VarBranchingRule())], Coluna.Algorithm.MostFractionalCriterion), Coluna.Algorithm.DepthFirstStrategy(), 100000, 100, false, 0, 0, false), 10000, 10000)
***************************************************************************************
**** BaB tree root node
**** Local DB = -Inf, global bounds : [ -Inf , Inf ], time = 1.36 sec.
***************************************************************************************
[ Info: Setting up node 2 before apply
<it=  1> <et=11.22> <mst= 4.34> <sp= 4.53> <cols=120> <mlp=2310000.0000> <DB=-2489880.0000> <PB=Inf>
<it=  2> <et=12.76> <mst= 0.03> <sp= 1.50> <cols=120> <mlp=750120.0000> <DB=-1649880.0000> <PB=Inf>
<it=  3> <et=13.64> <mst= 0.00> <sp= 0.86> <cols=120> <mlp=540120.0000> <DB=-659880.0000> <PB=Inf>
<it=  4> <et=14.35> <mst= 0.01> <sp= 0.70> <cols=120> <mlp=  120.0000> <DB=    0.0000> <PB=Inf>
<it=  5> <et=15.06> <mst= 0.00> <sp= 0.71> <cols=120> <mlp=   80.5000> <DB=    0.0000> <PB=Inf>
<it=  6> <et=16.07> <mst= 0.01> <sp= 1.00> <cols=120> <mlp=   77.5000> <DB=   37.5000> <PB=Inf>
<it=  7> <et=16.77> <mst= 0.01> <sp= 0.69> <cols=120> <mlp=   73.5000> <DB=   43.5000> <PB=Inf>
<it=  8> <et=17.40> <mst= 0.01> <sp= 0.62> <cols= 0> <mlp=   71.2500> <DB=   71.2500> <PB=Inf>
[ LogLevel(1): Column Generation Algorithm has converged.
[ Info: Recording reformulation state.
[ Info: Recording master info.
[ Info: Recording sp 68 info.
[ Info: Recording sp 2 info.
[ Info: Recording sp 89 info.
[ Info: Recording sp 11 info.
[ Info: Recording sp 39 info.
[ Info: Recording sp 46 info.
[ Info: Recording sp 85 info.
[ Info: Recording sp 25 info.
[ Info: Recording sp 55 info.
[ Info: Recording sp 42 info.
[ Info: Recording sp 29 info.
[ Info: Recording sp 58 info.
[ Info: Recording sp 66 info.
[ Info: Recording sp 59 info.
[ Info: Recording sp 8 info.
[ Info: Recording sp 74 info.
[ Info: Recording sp 95 info.
[ Info: Recording sp 57 info.
[ Info: Recording sp 20 info.
[ Info: Recording sp 90 info.
[ Info: Recording sp 111 info.
[ Info: Recording sp 14 info.
[ Info: Recording sp 31 info.
[ Info: Recording sp 78 info.
[ Info: Recording sp 112 info.
[ Info: Recording sp 70 info.
[ Info: Recording sp 106 info.
[ Info: Recording sp 33 info.
[ Info: Recording sp 18 info.
[ Info: Recording sp 52 info.
[ Info: Recording sp 121 info.
[ Info: Recording sp 69 info.
[ Info: Recording sp 114 info.
[ Info: Recording sp 109 info.
[ Info: Recording sp 96 info.
[ Info: Recording sp 26 info.
[ Info: Recording sp 35 info.
[ Info: Recording sp 83 info.
[ Info: Recording sp 17 info.
[ Info: Recording sp 64 info.
[ Info: Recording sp 65 info.
[ Info: Recording sp 49 info.
[ Info: Recording sp 44 info.
[ Info: Recording sp 84 info.
[ Info: Recording sp 4 info.
[ Info: Recording sp 37 info.
[ Info: Recording sp 110 info.
[ Info: Recording sp 45 info.
[ Info: Recording sp 13 info.
[ Info: Recording sp 86 info.
[ Info: Recording sp 67 info.
[ Info: Recording sp 99 info.
[ Info: Recording sp 93 info.
[ Info: Recording sp 117 info.
[ Info: Recording sp 94 info.
[ Info: Recording sp 105 info.
[ Info: Recording sp 30 info.
[ Info: Recording sp 115 info.
[ Info: Recording sp 47 info.
[ Info: Recording sp 54 info.
[ Info: Recording sp 32 info.
[ Info: Recording sp 50 info.
[ Info: Recording sp 77 info.
[ Info: Recording sp 40 info.
[ Info: Recording sp 80 info.
[ Info: Recording sp 101 info.
[ Info: Recording sp 82 info.
[ Info: Recording sp 91 info.
[ Info: Recording sp 7 info.
[ Info: Recording sp 9 info.
[ Info: Recording sp 43 info.
[ Info: Recording sp 60 info.
[ Info: Recording sp 34 info.
[ Info: Recording sp 75 info.
[ Info: Recording sp 104 info.
[ Info: Recording sp 87 info.
[ Info: Recording sp 103 info.
[ Info: Recording sp 3 info.
[ Info: Recording sp 61 info.
[ Info: Recording sp 79 info.
[ Info: Recording sp 38 info.
[ Info: Recording sp 118 info.
[ Info: Recording sp 71 info.
[ Info: Recording sp 120 info.
[ Info: Recording sp 36 info.
[ Info: Recording sp 48 info.
[ Info: Recording sp 113 info.
[ Info: Recording sp 76 info.
[ Info: Recording sp 12 info.
[ Info: Recording sp 100 info.
[ Info: Recording sp 81 info.
[ Info: Recording sp 98 info.
[ Info: Recording sp 16 info.
[ Info: Recording sp 62 info.
[ Info: Recording sp 107 info.
[ Info: Recording sp 21 info.
[ Info: Recording sp 10 info.
[ Info: Recording sp 102 info.
[ Info: Recording sp 19 info.
[ Info: Recording sp 51 info.
[ Info: Recording sp 22 info.
[ Info: Recording sp 6 info.
[ Info: Recording sp 24 info.
[ Info: Recording sp 73 info.
[ Info: Recording sp 88 info.
[ Info: Recording sp 92 info.
[ Info: Recording sp 119 info.
[ Info: Recording sp 53 info.
[ Info: Recording sp 116 info.
[ Info: Recording sp 72 info.
[ Info: Recording sp 28 info.
[ Info: Recording sp 5 info.
[ Info: Recording sp 23 info.
[ Info: Recording sp 63 info.
[ Info: Recording sp 27 info.
[ Info: Recording sp 56 info.
[ Info: Recording sp 97 info.
[ Info: Recording sp 108 info.
[ Info: Recording sp 41 info.
[ Info: Recording sp 15 info.
ERROR: LoadError: Method run! which takes formulation and Incumbents as input returns OldOutput
            is not implemented for algorithm Coluna.Algorithm.SolveIpForm.

[guimarqu]

I think you have to add the following method in the file src/Algorithm/solveipform.jl

function run!(alg::SolveIpForm, reform::Reformulation, input::NewOptimizationInput)
    master = getmaster(reform)
    ipforminput = SolveIpFormInput(ObjValues(master))
    return run!(alg, master, ipforminput)
end

There is no bug in the tests because of the redefinition of the run! method... Would you like to PR this ?

[YP-Ye]

I think you have to add the following method in the file src/Algorithm/solveipform.jl

function run!(alg::SolveIpForm, reform::Reformulation, input::NewOptimizationInput)
    master = getmaster(reform)
    ipforminput = SolveIpFormInput(ObjValues(master))
    return run!(alg, master, ipforminput)
end

There is no bug in the tests because of the redefinition of the run! method... Would you like to PR this ?

Thank you! However, a new problem happens after adding the run! method:

MethodError: no method matching add_lp_dual_sol!(::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}, ::Nothing)
Closest candidates are:
  add_lp_dual_sol!(::Coluna.Algorithm.OptimizationState{F,S}, !Matched::Coluna.Containers.Solution{F,Coluna.MathProg.Id{Coluna.MathProg.Constraint},Float64}) where {F, S} at C:\Users\Administrator\.juliapro\JuliaPro_v1.2.0-1\packages\Coluna\YZZg2\src\Algorithm\utilities\optimizationstate.jl:240
run!(::Coluna.Algorithm.SolveLpForm, ::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, ::Coluna.Algorithm.SolveLpFormInput) at solvelpform.jl:41
macro expansion at colgen.jl:321 [inlined]
macro expansion at util.jl:213 [inlined]
cg_main_loop!(::Coluna.Algorithm.ColumnGeneration, ::Coluna.Algorithm.ColGenRuntimeData, ::Coluna.MathProg.Reformulation) at colgen.jl:320
run!(::Coluna.Algorithm.ColumnGeneration, ::Coluna.MathProg.Reformulation, ::Coluna.Algorithm.NewOptimizationInput{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}) at colgen.jl:29
run!(::Coluna.Algorithm.ColGenConquer, ::Coluna.MathProg.Reformulation, ::Coluna.Algorithm.ConquerInput) at conquer.jl:148
apply_conquer_alg_to_node!(::Coluna.Algorithm.Node, ::Coluna.Algorithm.ColGenConquer, ::Coluna.MathProg.Reformulation, ::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}) at node.jl:180
prepare_and_run_conquer_algorithm!(::Coluna.Algorithm.TreeSearchRuntimeData, ::Coluna.Algorithm.ColGenConquer, ::Coluna.MathProg.Reformulation, ::Coluna.Algorithm.Node, ::Bool) at treesearch.jl:148
run!(::Coluna.Algorithm.TreeSearchAlgorithm, ::Coluna.MathProg.Reformulation, ::Coluna.Algorithm.NewOptimizationInput{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}) at treesearch.jl:236
optimize!(::Coluna.MathProg.Reformulation, ::Coluna.Algorithm.TreeSearchAlgorithm, ::Coluna.Containers.Bound{Coluna.MathProg.Primal,Coluna.MathProg.MinSense}, ::Coluna.Containers.Bound{Coluna.MathProg.Dual,Coluna.MathProg.MinSense}) at optimize.jl:99
macro expansion at optimize.jl:64 [inlined]
macro expansion at TimerOutput.jl:214 [inlined]
optimize!(::Coluna.MathProg.Problem, ::Coluna.MathProg.Annotations, ::Coluna.Params) at optimize.jl:63
optimize!(::Coluna.Optimizer) at MOIwrapper.jl:69
optimize!(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}) at cachingoptimizer.jl:189
#optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at optimizer_interface.jl:131
#optimize! at none:0 [inlined]
#optimize! at none:0 [inlined]
optimize!(::Model) at BlockDecomposition.jl:32
#optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at optimizer_interface.jl:121
optimize! at optimizer_interface.jl:107 [inlined]
optimize!(::Model) at optimizer_interface.jl:107
top-level scope at cuttingstock2.jl:54

[guimarqu]

When the LP restricted master is solved, CPLEX finds a solution. The primal solution is retrieved but the dual stays empty. I have to check what's going on...

[guimarqu]

Moreover, I would recommand to use multiplicity if your subproblems are identical. Example here : https://github.com/atoptima/ColunaDemos.jl/blob/master/src/CuttingStock/model.jl

Unfortunately, we don't have a good way to retrieve the solution for now.

[YP-Ye]

Thank you. I try Coluna with different solvers today, it works well with Gurobi and GLPK. I think it may be a problem of CPLEX.

[guimarqu]

The last bug was in Cplex.jl. I close the issue. Thank you for the feedback !