search

atoptima / Coluna.jl

Branch-and-Price-and-Cut in Julia
https://www.atoptima.com
Other
192 stars 43 forks source link

Problem with Coluna.Algorithm.ColumnGeneration #449

Closed wdscoelho closed 3 years ago

wdscoelho commented 3 years ago

Hello,

I'm experiencing a problem with Coluna.Algorithm.ColumnGeneration on my model.

If I use the following constructor :

coluna = optimizer_with_attributes( Coluna.Optimizer, "params" => Coluna.Params( solver = Coluna.Algorithm.ColumnGeneration() ), "default_optimizer" => CPLEX.Optimizer )

on the example from https://atoptima.github.io/Coluna.jl/latest/user/start/, it works fine. But with my model, I get the following error:

Coluna Version 0.3.5 | 2021-02-12 | 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 /home/wesley/.julia/packages/Coluna/OEmAD/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 /home/wesley/.julia/packages/Coluna/OEmAD/src/optimize.jl:33 Solver returned that the LP restricted master is feasible but did not return a dual solution. Please open an issue (https://github.com/atoptima/Coluna.jl/issues). Stacktrace: [1] error(::String, ::String, ::String) at ./error.jl:42 [2] cg_main_loop!(::Coluna.Algorithm.ColumnGeneration, ::Env, ::Int64, ::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}, ::Coluna.Algorithm.ReformData) at /home/wesley/.julia/packages/Coluna/OEmAD/src/Algorithm/colgen.jl:651 [3] run!(::Coluna.Algorithm.ColumnGeneration, ::Env, ::Coluna.Algorithm.ReformData, ::Coluna.Algorithm.OptimizationInput{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}) at /home/wesley/.julia/packages/Coluna/OEmAD/src/Algorithm/colgen.jl:89 [4] optimize!(::Coluna.MathProg.Reformulation, ::Env, ::Coluna.ColunaBase.Bound{Coluna.MathProg.Primal,Coluna.MathProg.MinSense}, ::Coluna.ColunaBase.Bound{Coluna.MathProg.Dual,Coluna.MathProg.MinSense}) at /home/wesley/.julia/packages/Coluna/OEmAD/src/optimize.jl:90 [5] macro expansion at /home/wesley/.julia/packages/Coluna/OEmAD/src/optimize.jl:62 [inlined] [6] macro expansion at /home/wesley/.julia/packages/TimerOutputs/dVnaw/src/TimerOutput.jl:190 [inlined] [7] optimize!(::Coluna.MathProg.Problem, ::Coluna.Annotations, ::Coluna.Params) at /home/wesley/.julia/packages/Coluna/OEmAD/src/optimize.jl:61 [8] optimize!(::Coluna.Optimizer) at /home/wesley/.julia/packages/Coluna/OEmAD/src/MOIwrapper.jl:98 [9] optimize!(::MathOptInterface.Bridges.LazyBridgeOptimizer{Coluna.Optimizer}) at /home/wesley/.julia/packages/MathOptInterface/bygN7/src/Bridges/bridge_optimizer.jl:239 [10] optimize!(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}) at /home/wesley/.julia/packages/MathOptInterface/bygN7/src/Utilities/cachingoptimizer.jl:189 [11] #optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:131 [12] #optimize! at ./none:0 [inlined] (repeats 2 times) [13] optimize!(::Model) at /home/wesley/.julia/packages/BlockDecomposition/OYIcC/src/BlockDecomposition.jl:51 [14] #optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:121 [15] optimize! at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:107 [inlined] (repeats 2 times)

I'm getting the same error with GLPK.

I'm using: Julia 1.2.0 JuMP 0.21.1 Coluna 0.3.5 Cplex 0.7.3 and ILO CPLEX 12.10 GLPK 0.13

Could you please help with this issue? Tell me with need my code. I can upload it somewhere because it is complicated enough to write it here.

Thank you in advance.

Wesley

guimarqu commented 3 years ago

Can you run your code with


using Base.CoreLogging, Logging
global_logger(ConsoleLogger(stderr, LogLevel(-3)))

and send me the output please ?

wdscoelho commented 3 years ago

I got hundreds of the following message:

LogLevel(-2): Setting members of constraint c └ @ Coluna.MathProg ~/.julia/packages/Coluna/OEmAD/src/MathProg/formulation.jl:466

and then

Solver returned that the LP restricted master is feasible but did not return a dual solution. Please open an issue (https://github.com/atoptima/Coluna.jl/issues). Stacktrace: [1] error(::String, ::String, ::String) at ./error.jl:42 [2] cg_main_loop!(::Coluna.Algorithm.ColumnGeneration, ::Env, ::Int64, ::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}, ::Coluna.Algorithm.ReformData) at /home/wesley/.julia/packages/Coluna/OEmAD/src/Algorithm/colgen.jl:651 [3] run!(::Coluna.Algorithm.ColumnGeneration, ::Env, ::Coluna.Algorithm.ReformData, ::Coluna.Algorithm.OptimizationInput{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}) at /home/wesley/.julia/packages/Coluna/OEmAD/src/Algorithm/colgen.jl:89 [4] optimize!(::Coluna.MathProg.Reformulation, ::Env, ::Coluna.ColunaBase.Bound{Coluna.MathProg.Primal,Coluna.MathProg.MinSense}, ::Coluna.ColunaBase.Bound{Coluna.MathProg.Dual,Coluna.MathProg.MinSense}) at /home/wesley/.julia/packages/Coluna/OEmAD/src/optimize.jl:90 [5] macro expansion at /home/wesley/.julia/packages/Coluna/OEmAD/src/optimize.jl:62 [inlined] [6] macro expansion at /home/wesley/.julia/packages/TimerOutputs/dVnaw/src/TimerOutput.jl:190 [inlined] [7] optimize!(::Coluna.MathProg.Problem, ::Coluna.Annotations, ::Coluna.Params) at /home/wesley/.julia/packages/Coluna/OEmAD/src/optimize.jl:61 [8] optimize!(::Coluna.Optimizer) at /home/wesley/.julia/packages/Coluna/OEmAD/src/MOIwrapper.jl:98 [9] optimize!(::MathOptInterface.Bridges.LazyBridgeOptimizer{Coluna.Optimizer}) at /home/wesley/.julia/packages/MathOptInterface/bygN7/src/Bridges/bridge_optimizer.jl:239 [10] optimize!(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}) at /home/wesley/.julia/packages/MathOptInterface/bygN7/src/Utilities/cachingoptimizer.jl:189 [11] #optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:131 [12] #optimize! at ./none:0 [inlined] (repeats 2 times) [13] optimize!(::Model) at /home/wesley/.julia/packages/BlockDecomposition/OYIcC/src/BlockDecomposition.jl:51 [14] #optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:121 [15] optimize! at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:107 [inlined] (repeats 2 times)

guimarqu commented 3 years ago

I made some changes in the log levels because it's a little bit messy.

Can you update your Coluna version by doing ] add Coluna#change_logs in the julia REPL (branch change_logs contains the changes) ? Then, can you run the code again and send me the whole ouput ? You can attach a file to your comment.

The goal is to understand why Cplex doesn't provide a dual solution after optimizing the master LP.

wdscoelho commented 3 years ago

Here's my code: https://github.com/wdscoelho/slicing_Coluna

And here's the output

Coluna Version 0.3.5 | 2021-02-12 | 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 ~/.julia/packages/Coluna/Yd1PT/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 ~/.julia/packages/Coluna/Yd1PT/src/optimize.jl:33 ┌ LogLevel(-1): Coluna ready to start. └ @ Coluna ~/.julia/packages/Coluna/Yd1PT/src/optimize.jl:58 ┌ LogLevel(-1): Coluna.Params │ global_art_var_cost: Float64 100000.0 │ local_art_var_cost: Float64 10000.0 │ solver: Coluna.Algorithm.ColumnGeneration └ @ Coluna ~/.julia/packages/Coluna/Yd1PT/src/optimize.jl:59 ┌ LogLevel(-1): Synching formulation 1 └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/optimizerwrappers.jl:41 ┌ LogLevel(-3): Nb of primal solutions: 1 └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:219 ┌ LogLevel(-3): Termination status : OPTIMAL. └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:220 ┌ LogLevel(-3): Primal status of 1 is FEASIBLE_POINT └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:223 ┌ LogLevel(-3): Var v = 10.0 └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:239 ┌ LogLevel(-3): Var local_art_of_sp_lb_3 = 1.0 └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:239 ┌ LogLevel(-3): Var local_art_of_sp_lb_2 = 1.0 └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:239 ┌ LogLevel(-3): Nb of dual solutions: 1 └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:252 ┌ LogLevel(-3): Termination status : OPTIMAL. └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:253 ┌ LogLevel(-3): Dual status of 1 is NO_SOLUTION └ @ Coluna.MathProg ~/.julia/packages/Coluna/Yd1PT/src/MathProg/MOIinterface.jl:256 Solver returned that the LP restricted master is feasible but did not return a dual solution. Please open an issue (https://github.com/atoptima/Coluna.jl/issues).

Stacktrace: [1] error(::String, ::String, ::String) at ./error.jl:42 [2] cg_main_loop!(::Coluna.Algorithm.ColumnGeneration, ::Env, ::Int64, ::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}, ::Coluna.Algorithm.ReformData) at /home/wesley/.julia/packages/Coluna/Yd1PT/src/Algorithm/colgen.jl:651 [3] run!(::Coluna.Algorithm.ColumnGeneration, ::Env, ::Coluna.Algorithm.ReformData, ::Coluna.Algorithm.OptimizationInput{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster},Coluna.MathProg.MinSense}) at /home/wesley/.julia/packages/Coluna/Yd1PT/src/Algorithm/colgen.jl:89 [4] optimize!(::Coluna.MathProg.Reformulation, ::Env, ::Coluna.ColunaBase.Bound{Coluna.MathProg.Primal,Coluna.MathProg.MinSense}, ::Coluna.ColunaBase.Bound{Coluna.MathProg.Dual,Coluna.MathProg.MinSense}) at /home/wesley/.julia/packages/Coluna/Yd1PT/src/optimize.jl:90 [5] macro expansion at /home/wesley/.julia/packages/Coluna/Yd1PT/src/optimize.jl:62 [inlined] [6] macro expansion at /home/wesley/.julia/packages/TimerOutputs/dVnaw/src/TimerOutput.jl:190 [inlined] [7] optimize!(::Coluna.MathProg.Problem, ::Coluna.Annotations, ::Coluna.Params) at /home/wesley/.julia/packages/Coluna/Yd1PT/src/optimize.jl:61 [8] optimize!(::Coluna.Optimizer) at /home/wesley/.julia/packages/Coluna/Yd1PT/src/MOIwrapper.jl:98 [9] optimize!(::MathOptInterface.Bridges.LazyBridgeOptimizer{Coluna.Optimizer}) at /home/wesley/.julia/packages/MathOptInterface/bygN7/src/Bridges/bridge_optimizer.jl:239 [10] optimize!(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}) at /home/wesley/.julia/packages/MathOptInterface/bygN7/src/Utilities/cachingoptimizer.jl:189 [11] #optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:131 [12] #optimize! at ./none:0 [inlined] (repeats 2 times) [13] optimize!(::Model) at /home/wesley/.julia/packages/BlockDecomposition/OYIcC/src/BlockDecomposition.jl:51 [14] #optimize!#97(::Bool, ::Bool, ::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}, ::typeof(optimize!), ::Model, ::Nothing) at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:121 [15] optimize! at /home/wesley/.julia/packages/JuMP/CZ8vV/src/optimizer_interface.jl:107 [inlined] (repeats 2 times) [16] create_COLUNA(::Instance) at /raid/home/wesley/Doc/Codes/Coluna/src/my_functions.jl:1583 [17] top-level scope at /raid/home/wesley/Doc/Codes/Coluna/src/Coluna_Dec.jl:23 [18] include at ./boot.jl:328 [inlined] [19] include_relative(::Module, ::String) at ./loading.jl:1094 [20] include(::Module, ::String) at ./Base.jl:31 [21] include(::String) at ./client.jl:431

guimarqu commented 3 years ago

The "LP" is solved to optimality but there is no dual solution available.

We already had this problem with CPLEX (https://github.com/atoptima/Coluna.jl/issues/315) but I don't have CPLEX anymore to reproduce.

Can you reproduce the bug with another solver e.g. GLPK, Gurobi ?

wdscoelho commented 3 years ago

Yes, same error with GLPK.

guimarqu commented 3 years ago

Can you give me a way to reproduce the bug ?

wdscoelho commented 3 years ago

Here's my code

https://github.com/wdscoelho/slicing_Coluna/

You have just to change the related parameters on function create_COLUNA(instance::Instance) in lines 1063-1071 in the my_functions.jl file.

guimarqu commented 3 years ago

Hi,

It's because you're calling the ColumnGenerationAgorithm or ColCutGenConquer and the integrality constraints are now relaxed in TreeSearchAlgorithm. So the master is a MIP instead of a LP when colgen solves it. That's what it cannot retrieve the dual sol and that's a bug !

Regression because of #438. (Needs more tests).

Thanks for the report.

wdscoelho commented 3 years ago

Hello Guillaume,

Thank you for your answer. So, maybe that's why I'm experiencing a problem to prove the optimality of a solution when using Coluna.Algorithm.TreeSearchAlgorithm.

If I try to solve the instance found in my code https://github.com/wdscoelho/slicing_Coluna, Coluna is not able to increase the lower bound (objective function = minimize). As you can see in the attached file Coluna_output.txt, Coluna finds the optimal solution within few seconds (I know its value = 140.01) but doesn't improve the lower bound in any interaction after the root node.

Could you please let me know what you think it's the problem?

Thank you in advance. Wesley

guimarqu commented 3 years ago

Hi,

You should take a look at the branch and bound tree to see what happens. You have to set the parameter branchingtreefile of TreeSearchAlgorithm.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ Le mercredi, mars 3, 2021 1:38 PM, Wesley da Silva Coelho notifications@github.com a écrit :

Hello Guillaume,

Thank you for your answer. So, maybe that's why I'm experiencing a problem to prove the optimality of a solution when using Coluna.Algorithm.TreeSearchAlgorithm.

If I try to solve the instance found in my code https://github.com/wdscoelho/slicing_Coluna, Coluna is not able to increase the lower bound (objective function = minimize). As you can see in the attached file Coluna_output.txt, Coluna finds the optimal solution within few seconds (I know its value = 140.01) but doesn't improve the lower bound in any interaction after the root node.

Could you please let me know what you think it's the problem?

Thank you in advance. Wesley

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or unsubscribe.

wdscoelho commented 3 years ago

Ah ok!

Here's a log output: Coluna_log.txt

It's very strange cause I let the solver running for hours (more than 15) and it doesn't prove the optimality. This instance takes less than 5 seconds the be solved by Cplex.

guimarqu commented 3 years ago

Ok, I think you need valid inequalities and a better branching strategy.

For the branching strategy, you have to define your own algorithm because the branching callback is not available ( #403) . You can also try the best dual bound strategy but it's broken ( #414). I wrote a comment with the steps to follow to fix the issue if you want to give it a try. If you fix it, please open a PR :)

wdscoelho commented 3 years ago

Nothing has been improved by applying the modification to the dual-bound strategy.

Could it be a matter of precision when calculating the reduced cost?

guimarqu commented 3 years ago

I do not believe precision is an issue here. It is probably a matter of using valid inequalities and branching strategies. Solver such as Cplex, Gurobi, … automatically applies a lot of valid inequalities (such as MIR or cover cuts) and has a better strategy than branching only on the most fractional solution.

Coluna is a framework not a solver. It provides algorithms to try very quickly column generation on your problem and then devices your own branch-cut-and-price algorithm to scale up and hopefully beats the commercial solver.

I saw that your root gap is quite large, you just need to improve your formulation with valid inequalities now.

wdscoelho commented 3 years ago

I see,

I have several Valid Inequalities that work very well compared to the basic model and without all cuts and pre-solving routines of Cplex, some of them have improved a lot my LP lower bound and the size of the BB tree. And still, they don't help Coluna to prove the optimality. I even tried to set a lower bound equal to the optimal value, and it doesn't work with Coluna: Coluna_log.txt.

I know that Coluna it's not a solver, but it's very strange that, even with a tiny instance of my problem, the framework is not able to converge in less than 12h (I don't know if it solves the instance at all cause I stopped the test after this time limit).

Well, thank you anyway for your answers. I'll see what I can do.

Wesley

guimarqu commented 3 years ago

Oh ok ! What is the dual bound at the root node of Coluna with and without your valid inequalities ?

For the second run, you are very unlucky because you don't find the optimal solution like you did in the first run. This is because of the primal heuristic.

I suggest you to define your model as : BlockModel(coluna, direct_model = true) to see the variables on which Coluna is branching. Moreover, there is an example of strong branching here if you want to try : https://github.com/atoptima/Coluna.jl/blob/f5f55537bce4640176283177aa8cf5a435b932c1/test/full_instances_tests.jl#L56

wdscoelho commented 3 years ago

Thank you for your help, but the strong branching didn't help. Hers's the output (after few iteractions) with one of my valid inequality Coluna_log.txt

and without it: Coluna_log.txt

Either ways, the solver doesn't improve the lower bound after leaving the root node.

guimarqu commented 3 years ago

The cut callback is not called, you shoud have a message "Robust cut separation callback adds..."

wdscoelho commented 3 years ago

I'm using only a specific valid inequality in these tests and adding it during the creation of my model. For now, I'm not using the callback.