search

atoptima / Coluna.jl

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

Using coluna.jl with Mosek and MSK_RES_ERR_UPPER_BOUND_IS_A_NAN #793

Closed hlefebvr closed 1 year ago

hlefebvr commented 1 year ago

Describe the bug When using a branch-and-price algorithm to solve Generalized Assignment Problem instances with Mosek as an external solver, an error is thrown.

ERROR: LoadError: Mosek.MosekError(1391, "The upper bound specified is not a number (nan).")

This error relates to error MSK_RES_ERR_UPPER_BOUND_IS_A_NAN (https://docs.mosek.com/10.0/opt-server/response-codes.html).

This, I guess, happens when a bound is set to a non numerical value (e.g., +inf ?). Since every variable is bounded in GAP, I suspect this to come from artificial variables. Indeed, the stack shows that solve_master is being called before the error is thrown, as well as enforce_bounds_in_optimizer.

Here is the complete trace.

Coluna
Version 0.5.3 | https://github.com/atoptima/Coluna.jl
***************************************************************************************
**** B&B tree root node
**** Local DB = -Inf, global bounds: [ -Inf , Inf ], time = 5.13 sec.
***************************************************************************************
ERROR: LoadError: Mosek.MosekError(1391, "The upper bound specified is not a number (nan).")
Stacktrace:
  [1] putvarbound(task::Mosek.Task, j::Int32, bkx::Mosek.Boundkey, blx::Float64, bux::Float64)
    @ Mosek ~/.julia/packages/Mosek/5QnPP/src/msk_functions.jl:3408
  [2] add_variable_constraint
    @ ~/.julia/packages/MosekTools/mFLX9/src/constraint.jl:246 [inlined]
  [3] add_constraint(m::MosekTools.Optimizer, xs::MathOptInterface.VariableIndex, dom::MathOptInterface.Interval{Float64})
    @ MosekTools ~/.julia/packages/MosekTools/mFLX9/src/constraint.jl:464
  [4] enforce_bounds_in_optimizer!(form::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, optimizer::Coluna.MathProg.MoiOptimizer, var::Coluna.MathProg.Variable)
    @ Coluna.MathProg ~/.julia/packages/Coluna/65ad5/src/MathProg/MOIinterface.jl:81
  [5] add_to_optimizer!(form::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, optimizer::Coluna.MathProg.MoiOptimizer, var::Coluna.MathProg.Variable)
    @ Coluna.MathProg ~/.julia/packages/Coluna/65ad5/src/MathProg/MOIinterface.jl:118
  [6] sync_solver!(optimizer::Coluna.MathProg.MoiOptimizer, f::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster})
    @ Coluna.MathProg ~/.julia/packages/Coluna/65ad5/src/MathProg/optimizerwrappers.jl:61
  [7] optimize_with_moi!(optimizer::Coluna.MathProg.MoiOptimizer, form::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, algo::Coluna.Algorithm.MoiOptimize, result::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/basic/subsolvers.jl:89
  [8] optimize_lp_form!(algo::Coluna.Algorithm.SolveLpForm, optimizer::Coluna.MathProg.MoiOptimizer, form::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, result::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/basic/solvelpform.jl:66
  [9] macro expansion
    @ ~/.julia/packages/Coluna/65ad5/src/Algorithm/basic/solvelpform.jl:83 [inlined]
 [10] macro expansion
    @ ~/.julia/packages/TimerOutputs/4yHI4/src/TimerOutput.jl:237 [inlined]
 [11] run!(algo::Coluna.Algorithm.SolveLpForm, ::Env{Coluna.MathProg.VarId}, form::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, input::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense}, optimizer_id::Int64)
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/basic/solvelpform.jl:76
 [12] solve_master!(master::Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, cg_optstate::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense}, restr_master_solve_alg::Coluna.Algorithm.SolveLpForm, restr_master_optimizer_id::Int64, env::Env{Coluna.MathProg.VarId})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/colgen.jl:664
 [13] macro expansion
    @ ~/.julia/packages/Coluna/65ad5/src/Algorithm/colgen.jl:868 [inlined]
 [14] macro expansion
    @ ./timing.jl:382 [inlined]
 [15] cg_main_loop!(algo::Coluna.Algorithm.ColumnGeneration, env::Env{Coluna.MathProg.VarId}, phase::Int64, cg_optstate::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense}, reform::Coluna.MathProg.Reformulation)
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/colgen.jl:867
 [16] run!(algo::Coluna.Algorithm.ColumnGeneration, env::Env{Coluna.MathProg.VarId}, reform::Coluna.MathProg.Reformulation, input::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/colgen.jl:269
 [17] run_colgen!(ctx::Coluna.Algorithm.ColCutGenContext, colgen::Coluna.Algorithm.ColumnGeneration, env::Env{Coluna.MathProg.VarId}, reform::Coluna.MathProg.Reformulation, node_state::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/conquer.jl:172
 [18] run_colcutgen!(ctx::Coluna.Algorithm.ColCutGenContext, env::Env{Coluna.MathProg.VarId}, reform::Coluna.MathProg.Reformulation, node_state::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/conquer.jl:211
 [19] run_colcutgen_conquer!(ctx::Coluna.Algorithm.ColCutGenContext, env::Env{Coluna.MathProg.VarId}, reform::Coluna.MathProg.Reformulation, input::Coluna.Algorithm.ConquerInputFromBaB)
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/conquer.jl:365
 [20] run!(algo::Coluna.Algorithm.ColCutGenConquer, env::Env{Coluna.MathProg.VarId}, reform::Coluna.MathProg.Reformulation, input::Coluna.Algorithm.ConquerInputFromBaB)
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/conquer.jl:395
 [21] children(space::Coluna.Algorithm.BaBSearchSpace, current::Coluna.Algorithm.Node, env::Env{Coluna.MathProg.VarId}, untreated_nodes::Base.Generator{DataStructures.PriorityQueue{Coluna.Algorithm.PrintedNode{Coluna.Algorithm.Node}, Float64, Base.Order.ForwardOrdering}, Coluna.Algorithm.var"#102#104"})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/treesearch/interface.jl:115
 [22] children
    @ ~/.julia/packages/Coluna/65ad5/src/Algorithm/treesearch/printer.jl:88 [inlined]
 [23] tree_search(strategy::Coluna.Algorithm.BestDualBoundStrategy, space::Coluna.Algorithm.PrinterSearchSpace{Coluna.Algorithm.BaBSearchSpace, Coluna.Algorithm.DefaultLogPrinter, Coluna.Algorithm.DevNullFilePrinter}, env::Env{Coluna.MathProg.VarId}, input::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/treesearch/explore.jl:31
 [24] run!(algo::Coluna.Algorithm.TreeSearchAlgorithm, env::Env{Coluna.MathProg.VarId}, reform::Coluna.MathProg.Reformulation, input::Coluna.Algorithm.OptimizationState{Coluna.MathProg.Formulation{Coluna.MathProg.DwMaster}, Coluna.MathProg.MinSense})
    @ Coluna.Algorithm ~/.julia/packages/Coluna/65ad5/src/Algorithm/treesearch.jl:60
 [25] optimize!(reform::Coluna.MathProg.Reformulation, env::Env{Coluna.MathProg.VarId}, initial_primal_bound::Coluna.ColunaBase.Bound{Coluna.MathProg.Primal, Coluna.MathProg.MinSense}, initial_dual_bound::Coluna.ColunaBase.Bound{Coluna.MathProg.Dual, Coluna.MathProg.MinSense}, initial_columns::Nothing)
    @ Coluna ~/.julia/packages/Coluna/65ad5/src/optimize.jl:90
 [26] macro expansion
    @ ~/.julia/packages/Coluna/65ad5/src/optimize.jl:54 [inlined]
 [27] macro expansion
    @ ~/.julia/packages/TimerOutputs/4yHI4/src/TimerOutput.jl:237 [inlined]
 [28] optimize!(env::Env{Coluna.MathProg.VarId}, prob::Coluna.MathProg.Problem, annotations::Coluna.Annotations)
    @ Coluna ~/.julia/packages/Coluna/65ad5/src/optimize.jl:53
 [29] optimize!(model::Coluna.Optimizer)
    @ Coluna ~/.julia/packages/Coluna/65ad5/src/MOIwrapper.jl:199
 [30] optimize!
    @ ~/.julia/packages/MathOptInterface/Ohzb2/src/Bridges/bridge_optimizer.jl:376 [inlined]
 [31] optimize!
    @ ~/.julia/packages/MathOptInterface/Ohzb2/src/MathOptInterface.jl:87 [inlined]
 [32] optimize!(m::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.Bridges.LazyBridgeOptimizer{Coluna.Optimizer}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}})
    @ MathOptInterface.Utilities ~/.julia/packages/MathOptInterface/Ohzb2/src/Utilities/cachingoptimizer.jl:316
 [33] optimize!(model::Model; ignore_optimize_hook::Bool, _differentiation_backend::MathOptInterface.Nonlinear.SparseReverseMode, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ JuMP ~/.julia/packages/JuMP/gVq7V/src/optimizer_interface.jl:185
 [34] optimize!(m::Model)
    @ BlockDecomposition ~/.julia/packages/BlockDecomposition/KH7HC/src/BlockDecomposition.jl:76
 [35] optimize!(model::Model; ignore_optimize_hook::Bool, _differentiation_backend::MathOptInterface.Nonlinear.SparseReverseMode, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ JuMP ~/.julia/packages/JuMP/gVq7V/src/optimizer_interface.jl:174
 [36] optimize!(model::Model)
    @ JuMP ~/.julia/packages/JuMP/gVq7V/src/optimizer_interface.jl:155
 [37] top-level scope
    @ ~/CLionProjects/idol_benchmark/GAP/coluna/main.jl:98

To Reproduce A working example can be found here.

Expected behavior I would expect coluna not to fail. In other words, that the conveyed bound be checked before calling add_constraint against nan values.

Environment (please complete the following information):

guimarqu commented 1 year ago

Hey Henri! Nice to hear from you!

Do I need a license to run MOSEK? If it's the case I'm afraid I won't be able to run the example.

You're probably right. We use intervals to maintain the bounds of the variables and MathOptInterface's documentation states that infinite bounds are allowed in intervals (see https://jump.dev/MathOptInterface.jl/stable/reference/standard_form/#MathOptInterface.Interval). Besides, looks like infinite intervals are tested in MosekTools.jl (they are not excluded from the test list). So it should have worked :/

It's not the first time we face this issue. So I'll consider changing the way we maintain variable bounds and stick to the classic constraints (>= and <=) and stop the use of infinite. I just can tell you that we won't do this change before 0.7. We are currently stabilizing the algorithms.

Could you run your instance with GLPK or Gurobi?

hlefebvr commented 1 year ago

Hi Guillaume,

Yes, you'd need a Mosek license. I use an academic one.

This error only occurs with Mosek (tested with GLPK and Gurobi).

Thanks for your answer!

Whenever I have time, I'll try to find a workaround or to understand exactly why this only occurs with MosekTools.jl.

guimarqu commented 1 year ago

You can try to reproduce using this example:

https://jump.dev/MathOptInterface.jl/stable/tutorials/example/

You'll have to replace the integrality constraint by an Interval.

hlefebvr commented 1 year ago

It seems that MosekTools.jl is indeed the one to blame here.

using MathOptInterface

const MOI = MathOptInterface

using MosekTools
using GLPK
using Gurobi

optimizer = GLPK.Optimizer()

c = [1.0, 2.0, 3.0]
w = [0.3, 0.5, 1.0]
C = 3.2

x = MOI.add_variables(optimizer, length(c));

MOI.set(
           optimizer,
           MOI.ObjectiveFunction{MOI.ScalarAffineFunction{Float64}}(),
           MOI.ScalarAffineFunction(MOI.ScalarAffineTerm.(c, x), 0.0),
       );

MOI.add_constraint(
    optimizer,
    MOI.ScalarAffineFunction(MOI.ScalarAffineTerm.(w, x), 0.0),
    MOI.LessThan(C),
);

for x_i in x
    #                                                         # Gurobi | Mosek | GLPK  
    #MOI.add_constraint(optimizer, x_i, MOI.ZeroOne())        #  OK    | KO**  | OK
    #MOI.add_constraint(optimizer, x_i, MOI.Interval(0., 1.)) #  OK    | OK    | OK
    MOI.add_constraint(optimizer, x_i, MOI.Interval(0., Inf)) #  OK    | KO*   | OK

    # *error is "Mosek.MosekError(1391, "The upper bound specified is not a number (nan).")"
    # **error is "LoadError: MathOptInterface.UnsupportedConstraint{MathOptInterface.VariableIndex, MathOptInterface.ZeroOne}: `MathOptInterface.VariableIndex`-in-`MathOptInterface.ZeroOne` constraint is not supported by the model."
end

MOI.optimize!(optimizer)

I will create an issue for MosekTools.jl.

guimarqu commented 1 year ago

Great, thanks for checking! I close this issue and open a new one for the variable bounds.