GitHub

Quick Start

This section will provide a brief introduction about how to use the OptimalBranching.jl package.

The maximum independent set problem

We provided two simple interfaces to solve the maximum independent set problem and count the branches used in calculation.

julia> using OptimalBranching, Graphs
julia> g = smallgraph(:tutte){46, 69} undirected simple Int64 graph
julia> mis_size(g) # the size of the maximum independent set (MIS)19
julia> mis_branch_count(g) # MIS size and the number of branches used in calculation(19, 2)

One can also select different strategies to solve the problem, which inclues

Here is an example:

julia> branching_strategy = BranchingStrategy(
           table_solver = TensorNetworkSolver(),
           selector = MinBoundarySelector(2),
           measure = D3Measure(),
           set_cover_solver = IPSolver()
       )BranchingStrategy
├── table_solver - TensorNetworkSolver(true)
├── set_cover_solver - IPSolver(HiGHS.Optimizer, 5, false)
├── selector - MinBoundarySelector(2)
└── measure - D3Measure()
julia> mis_size(g, bs = branching_strategy, reducer = MISReducer())19

One can also use the branch_and_reduce function to solve the problem, which is more flexible.

julia> branch_and_reduce(MISProblem(g), branching_strategy, MISReducer(), MaxSizeBranchCount)MaxSizeBranchCount(19, 2)

The optimal branching rule

We first specify a branching table, which is a table of bitstrings that the rule needs to cover. At least one bitstring in each row of the table is needed to be covered.

julia> using OptimalBranchingCore
julia> tbl = BranchingTable(5, [
               [[0, 0, 0, 0, 1], [0, 0, 0, 1, 0]],
               [[0, 0, 1, 0, 1]],
               [[0, 1, 0, 1, 0]],
               [[1, 1, 1, 0, 0]]])BranchingTable{BitBasis.LongLongUInt{1}}
10000, 01000
10100
01010
00111

Then, we generate the candidate clauses, which are the clauses forming the branching rule (a DNF formula).

julia> candidates = OptimalBranchingCore.candidate_clauses(tbl)14-element Vector{Clause{BitBasis.LongLongUInt{1}}}:
 Clause{BitBasis.LongLongUInt{1}}: #1 ∧ #2 ∧ #3 ∧ ¬#4 ∧ ¬#5
 Clause{BitBasis.LongLongUInt{1}}: #2 ∧ ¬#5
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ ¬#2 ∧ ¬#3 ∧ ¬#4 ∧ #5
 Clause{BitBasis.LongLongUInt{1}}: ¬#4
 Clause{BitBasis.LongLongUInt{1}}: #3 ∧ ¬#4
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ ¬#3
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ ¬#2 ∧ ¬#3 ∧ #4 ∧ ¬#5
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ ¬#2 ∧ ¬#4 ∧ #5
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ ¬#2 ∧ #3 ∧ ¬#4 ∧ #5
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ #2 ∧ ¬#3 ∧ #4 ∧ ¬#5
 Clause{BitBasis.LongLongUInt{1}}: ¬#5
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ ¬#3 ∧ #4 ∧ ¬#5
 Clause{BitBasis.LongLongUInt{1}}: ¬#1 ∧ ¬#2
 Clause{BitBasis.LongLongUInt{1}}: ¬#1

For each candidate clause, we calculate the size reduction of the problem after applying the clause. Here, we use a simple measure: counting the number of variables eliminated by the clause.

julia> Δρ = [length(literals(sc)) for sc in candidates]; println(Δρ)[5, 2, 5, 1, 2, 2, 5, 4, 5, 5, 1, 4, 2, 1]

Finally, we solve the set cover problem to find the optimal branching rule. The solver is set to be the IPSolver. For more options, please refer to the Performance Tips section.

julia> res_ip = OptimalBranchingCore.minimize_γ(tbl, candidates, Δρ, IPSolver())OptimalBranchingResult{BitBasis.LongLongUInt{1}, Int64}:
 selected_ids: [10, 8, 1]
 optimal_rule: DNF{BitBasis.LongLongUInt{1}}: (¬#1 ∧ #2 ∧ ¬#3 ∧ #4 ∧ ¬#5) ∨ (¬#1 ∧ ¬#2 ∧ ¬#4 ∧ #5) ∨ (#1 ∧ #2 ∧ #3 ∧ ¬#4 ∧ ¬#5)
 branching_vector: [5, 4, 5]
 γ: 1.2671683045421243

The result is an instance of OptimalBranchingResult, which contains the selected clauses, the optimal branching rule, and the branching vector.