Benchmarks on KaHyPar selector and greedy merge

[nzy1997]

CPU Info

M4

Setup:

using Test
using OptimalBranchingMIS
using OptimalBranchingCore
using OptimalBranchingMIS.Graphs


g = random_regular_graph(200, 3; seed = 2134)

1. MinBoundarySelector(2)

mis1, count1 = mis_branch_count(g)

(mis1, count1) = (88, 6496)

2. KaHyParSelector(20)

bs = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = KaHyParSelector(20), measure = D3Measure())
misk, countk = mis_branch_count(g; branching_strategy = bs)

(misk, countk) = (88, 3595)

3. KaHyParSelector(15)

bs = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = KaHyParSelector(15), measure = D3Measure())
misk, countk = mis_branch_count(g; branching_strategy = bs)

(misk, countk) = (88, 4501)

4. KaHyPar(15) + GreedyMerge()

bs = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = KaHyParSelector(15), measure = D3Measure(), set_cover_solver = OptimalBranchingCore.GreedyMerge())
miskg, countkg = mis_branch_count(g; branching_strategy = bs)

(miskg, countkg) = (88, 6248)

3. KaHyPar(15) + NaiveBranch()

The naive branch maximizes the length of each clause.

bs = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = KaHyParSelector(15), measure = D3Measure(), set_cover_solver = OptimalBranchingCore.NaiveBranch())
miskn, countkn = mis_branch_count(g; branching_strategy = bs)

miskn, countkn = (88, 107727)

Profile on greedy merge

Count  Overhead File                                          Line Function
331         0 @OptimalBranchingCore/src/greedymerge.jl        29 greedymerge(cls::Vector{Vector{Clause{LongLongUInt{1}}…
23         0 @OptimalBranchingMIS/src/graphs.jl              34 removed_vertices(vertices::Vector{Int64}, g::SimpleGra…
34         0 @OptimalBranchingMIS/src/tablesolver.jl         17 _reduced_alpha_configs(g::SimpleGraph{Int64}, openvert…
50         0 @OptimalBranchingMIS/src/tablesolver.jl         27 reduced_alpha_configs
46         0 @OptimalBranchingMIS/src/tablesolver.jl         27 reduced_alpha_configs(::TensorNetworkSolver, graph::Si…
30         0 @OptimalBranchingMIS/src/types.jl               89 size_reduction(p::MISProblem, m::D3Measure, cl::Clause…
301         0 @OptimalBranchingMIS/src/types.jl               95 size_reduction(p::MISProblem, m::D3Measure, cl::Clause…
22         0 @OptimalBranchingMIS/src/types.jl               97 size_reduction(p::MISProblem, m::D3Measure, cl::Clause…
Total snapshots: 693.

btime on greedy merge

9s for optimal branching, γ = 1.0814

246.635ms for greedy merge, γ = 1.0842073740067577

[GiggleLiu]

I find the number of branches has a large variance. Can you confirm that? @nzy1997

[nzy1997]

I also got a larger branch count. That's a little weird, since there's no change on the default solvers.

 g = random_regular_graph(200, 3; seed = 2134)
      
mis1, count1 = mis_branch_count(g)
(88, 10882)

When I check out to the pervious version, I can still get the original branch count 6496.

[GiggleLiu]

Is that due to the change of KaHyPar config file?

[GiggleLiu]

Gamma informed branching does not perform well

#34

julia> bs = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = MinBoundarySelector(2), measure = D3Measure(), set_cover_solver=IPSolver(max_itr=20, γ0=2.0))
julia> misk, countk = mis_branch_count(g; branching_strategy = bs, show_progress=true)

Default: (88, 10290)

Gamma informed:

julia> bs = BranchingStrategy(table_solver = TensorNetworkSolver(), selector = MinBoundarySelector(2), measure = D3Measure(), set_cover_solver=IPSolver(max_itr=1, γ0=1.044))
julia> misk, countk = mis_branch_count(g; branching_strategy = bs, show_progress=true)

(88, 26945)