Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fix in the lowerbound tightening #204

Merged
merged 24 commits into from
Oct 25, 2024
Merged

Fix in the lowerbound tightening #204

merged 24 commits into from
Oct 25, 2024

Conversation

dhendryc
Copy link
Collaborator

It can happen that both children nodes are pruned. And thus, the lower bound improvement might be substantial for both of them.

Also, corrected the sharpness constants for the optimal design problems according to the corrected proofs.

src/tightenings.jl Outdated Show resolved Hide resolved
matbesancon
matbesancon previously approved these changes Oct 22, 2024
@matbesancon
Copy link
Member

the mac tests failed again:

Sparse poisson regression: Error During Test at /Users/runner/work/Boscia.jl/Boscia.jl/examples/poisson_reg.jl:49
  Got exception outside of a @test
  AssertionError: lower_bound <= tree.incumbent + node.fw_dual_gap_limit : -0.9027271955946277 <= -0.9042653557617399
  Stacktrace:
    [1] evaluate_node!(tree::BnBTree{Boscia.FrankWolfeNode{FrankWolfe.ActiveSet{Vector{Float64}, Float64, Vector{Float64}}, FrankWolfe.DeletedVertexStorage{Vector{Float64}}, Boscia.IntegerBounds, Boscia.NodeInfo{Float64}}, @NamedTuple{problem::Boscia.SimpleOptimizationProblem{var"#f#203"{Float64}, var"#grad!#205"{Float64}, Boscia.TimeTrackingLMO{Boscia.MathOptBLMO{SCIP.Optimizer}}, Boscia.IntegerBounds}, current_node_id::Base.RefValue{Int64}, updated_incumbent::Base.RefValue{Bool}, global_tightening_rhs::Base.RefValue{Float64}, global_tightening_root_info::@NamedTuple{lower_bounds::Dict{Int64, Tuple{Float64, Float64}}, upper_bounds::Dict{Int64, Tuple{Float64, Float64}}}, global_tightenings::Boscia.IntegerBounds, options::Dict{Symbol, Any}, result::Dict{Symbol, Any}}, Vector{Float64}, Boscia.FrankWolfeSolution{Boscia.FrankWolfeNode{FrankWolfe.ActiveSet{Vector{Float64}, Float64, Vector{Float64}}, FrankWolfe.DeletedVertexStorage{Vector{Float64}}, Boscia.IntegerBounds, Boscia.NodeInfo{Float64}}, Vector{Float64}}}, node::Boscia.FrankWolfeNode{FrankWolfe.ActiveSet{Vector{Float64}, Float64, Vector{Float64}}, FrankWolfe.DeletedVertexStorage{Vector{Float64}}, Boscia.IntegerBounds, Boscia.NodeInfo{Float64}})
      @ Boscia ~/work/Boscia.jl/Boscia.jl/src/node.jl:286
    [2] optimize!(tree::BnBTree{Boscia.FrankWolfeNode{FrankWolfe.ActiveSet{Vector{Float64}, Float64, Vector{Float64}}, FrankWolfe.DeletedVertexStorage{Vector{Float64}}, Boscia.IntegerBounds, Boscia.NodeInfo{Float64}}, @NamedTuple{problem::Boscia.SimpleOptimizationProblem{var"#f#203"{Float64}, var"#grad!#205"{Float64}, Boscia.TimeTrackingLMO{Boscia.MathOptBLMO{SCIP.Optimizer}}, Boscia.IntegerBounds}, current_node_id::Base.RefValue{Int64}, updated_incumbent::Base.RefValue{Bool}, global_tightening_rhs::Base.RefValue{Float64}, global_tightening_root_info::@NamedTuple{lower_bounds::Dict{Int64, Tuple{Float64, Float64}}, upper_bounds::Dict{Int64, Tuple{Float64, Float64}}}, global_tightenings::Boscia.IntegerBounds, options::Dict{Symbol, Any}, result::Dict{Symbol, Any}}, Vector{Float64}, Boscia.FrankWolfeSolution{Boscia.FrankWolfeNode{FrankWolfe.ActiveSet{Vector{Float64}, Float64, Vector{Float64}}, FrankWolfe.DeletedVertexStorage{Vector{Float64}}, Boscia.IntegerBounds, Boscia.NodeInfo{Float64}}, Vector{Float64}}}; callback::Boscia.var"#callback#23"{Boscia.var"#callback#20#24"{DateTime, Vector{Float64}, Vector{Float64}, Vector{Float64}, Vector{Int64}, Vector{Int64}, Bool, Vector{Int64}, Vector{Int64}, Vector{Int64}, Dict{Symbol, Any}, Vector{Vector{Int64}}, Vector{Vector{Int64}}, Vector{Vector{Int64}}, Vector{Int64}, Nothing, Vector{Int64}, Vector{Int64}, Vector{Int64}, Int64, Int64, Int64, String, Vector{String}}})
      @ Boscia ~/work/Boscia.jl/Boscia.jl/src/custom_bonobo.jl:35
    [3] solve(f::var"#f#203"{Float64}, grad!::var"#grad!#205"{Float64}, blmo::Boscia.MathOptBLMO{SCIP.Optimizer}; traverse_strategy::Bonobo.BestFirstSearch, branching_strategy::Bonobo.MOST_INFEASIBLE, variant::Boscia.BPCG, line_search::FrankWolfe.Adaptive{Float64, Int64}, active_set::Nothing, lazy::Bool, lazy_tolerance::Float64, fw_epsilon::Float64, verbose::Bool, dual_gap::Float64, rel_dual_gap::Float64, time_limit::Float64, print_iter::Int64, dual_gap_decay_factor::Float64, max_fw_iter::Int64, min_number_lower::Float64, min_node_fw_epsilon::Float64, use_postsolve::Bool, min_fw_iterations::Int64, max_iteration_post::Int64, dual_tightening::Bool, global_dual_tightening::Bool, bnb_callback::Nothing, strong_convexity::Float64, sharpness_constant::Float64, sharpness_exponent::Float64, domain_oracle::Boscia.var"#72#74", start_solution::Nothing, fw_verbose::Bool, use_shadow_set::Bool, custom_heuristics::Vector{Boscia.Heuristic{Boscia.var"#28#29"}}, rounding_prob::Float64, clean_solutions::Bool, max_clean_iter::Int64, kwargs::@Kwargs{})
      @ Boscia ~/work/Boscia.jl/Boscia.jl/src/interface.jl:310
    [4] #solve#70
      @ ~/work/Boscia.jl/Boscia.jl/src/MOI_bounded_oracle.jl:645 [inlined]
    [5] macro expansion
      @ ~/work/Boscia.jl/Boscia.jl/examples/poisson_reg.jl:110 [inlined]
    [6] macro expansion
      @ ~/hostedtoolcache/julia/1.11.1/x64/share/julia/stdlib/v1.11/Test/src/Test.jl:1700 [inlined]
    [7] top-level scope
      @ ~/work/Boscia.jl/Boscia.jl/examples/poisson_reg.jl:50

@dhendryc dhendryc merged commit 297ccfb into main Oct 25, 2024
3 checks passed
@dhendryc dhendryc deleted the lb-tightening-fix branch October 25, 2024 10:12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants