Data

Tools

Indexes

Applications

Experiments

Open Source Science

OptimalBranching

Automated discovery of optimal branching rules for the branch-and-bound algorithm

https://github.com/optimalbranching/optimalbranching.jl

Science Score: 54.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ✓
    Academic publication links
    Links to: arxiv.org
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (17.3%) to scientific vocabulary

Keywords

branching combinatorial julia-language maximum-independent-set
Last synced: 6 months ago · JSON representation ·

Repository

Automated discovery of optimal branching rules for the branch-and-bound algorithm

Basic Info
Statistics
  • Stars: 15
  • Watchers: 2
  • Forks: 1
  • Open Issues: 14
  • Releases: 2
Topics
branching combinatorial julia-language maximum-independent-set
Created over 1 year ago · Last pushed 7 months ago
Metadata Files
Readme License Citation

README.md

Dev Build Status codecov

OptimalBranching.jl is a collection of tools for solving combinatorial optimization problems with branch-and-reduce method. It is written in Julia and features automatically generated branching rules with provable optimality (arXiv: 2412.07685). The rule generation is problem agnostic, and it can be easily extended to other problems. It contains two submodules: * OptimalBranchingCore.jl: the core algorithms, which convert the problem of searching the optimal branching rule into the problem of searching the optimal set cover. * OptimalBranchingMIS.jl: the maximum independent set (MIS) problem solver based on the optimal branching algorithms.

Installation

OptimalBranching is a   Julia Language   package. To install OptimalBranching, please open Julia's interactive session (known as REPL) and press ] key in the REPL to use the package mode, then type the following command

```julia pkg> add OptimalBranchingCore # for the core algorithms

pkg> add OptimalBranching # for utilities based on the core algorithms ```

If you have problem to install the package, please file us an issue.

Get started

```julia julia> using OptimalBranching, OptimalBranching.OptimalBranchingMIS.Graphs

julia> graph = smallgraph(:tutte) {46, 69} undirected simple Int64 graph

julia> misbranchcount(graph) (19, 2) ``` In this example, the maximum independent set size of the Tutte graph is 19, and the optimal branching strategy only generates 2 branches in the branching tree.

For advanced usage, please refer to the documentation.

How to Contribute

If you find any bug or have any suggestion, please open an issue.

Citation

If you find this package useful in your research, please cite the relevant paper in the CITATION.bib file.

Owner

  • Name: OptimalBranching
  • Login: OptimalBranching
  • Kind: organization

The branching algorithm, the automatic way

Citation (CITATION.bib) 

@misc{Gao2024,
      title={Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem}, 
      author={Xuan-Zhao Gao and Yi-Jia Wang and Pan Zhang and Jin-Guo Liu},
      year={2024},
      eprint={2412.07685},
      archivePrefix={arXiv},
      primaryClass={math.OC},
      url={https://arxiv.org/abs/2412.07685}, 
}

GitHub Events

Total
  • Fork event: 1
  • Create event: 29
  • Commit comment event: 2
  • Release event: 1
  • Issues event: 14
  • Watch event: 7
  • Delete event: 1
  • Member event: 1
  • Issue comment event: 107
  • Push event: 111
  • Pull request review event: 31
  • Pull request review comment event: 41
  • Pull request event: 45
Last Year
  • Fork event: 1
  • Create event: 29
  • Commit comment event: 2
  • Release event: 1
  • Issues event: 14
  • Watch event: 7
  • Delete event: 1
  • Member event: 1
  • Issue comment event: 107
  • Push event: 111
  • Pull request review event: 31
  • Pull request review comment event: 41
  • Pull request event: 45

Issues and Pull Requests

Last synced: 6 months ago

All Time
  • Total issues: 24
  • Total pull requests: 72
  • Average time to close issues: 23 days
  • Average time to close pull requests: 4 days
  • Total issue authors: 5
  • Total pull request authors: 6
  • Average comments per issue: 5.88
  • Average comments per pull request: 1.4
  • Merged pull requests: 52
  • Bot issues: 0
  • Bot pull requests: 10
Past Year
  • Issues: 24
  • Pull requests: 72
  • Average time to close issues: 23 days
  • Average time to close pull requests: 4 days
  • Issue authors: 5
  • Pull request authors: 6
  • Average comments per issue: 5.88
  • Average comments per pull request: 1.4
  • Merged pull requests: 52
  • Bot issues: 0
  • Bot pull requests: 10
View more stats
Top Authors
Issue Authors
  • GiggleLiu (15)
  • ArrogantGao (5)
  • nzy1997 (2)
  • JuliaTagBot (1)
  • YijiawWang (1)
Pull Request Authors
  • ArrogantGao (27)
  • GiggleLiu (25)
  • dependabot[bot] (6)
  • YijiawWang (6)
  • nzy1997 (4)
  • github-actions[bot] (4)
Top Labels
Issue Labels
enhancement (7) discussion (3)
Pull Request Labels
dependencies (6) github_actions (1)

Packages

  • Total packages: 3
  • Total downloads:
    • julia 2 total
  • Total dependent packages: 0
    (may contain duplicates)
  • Total dependent repositories: 0
    (may contain duplicates)
  • Total versions: 14
juliahub.com: OptimalBranchingCore

Automated discovery of optimal branching rules for the branch-and-bound algorithm

  • Versions: 6
  • Dependent Packages: 0
  • Dependent Repositories: 0
  • Downloads: 1 Total
Rankings
Dependent repos count: 3.2%
Downloads: 3.3%
Average: 7.6%
Dependent packages count: 16.3%
Last synced: 6 months ago
juliahub.com: OptimalBranchingMIS

Automated discovery of optimal branching rules for the branch-and-bound algorithm

  • Versions: 5
  • Dependent Packages: 0
  • Dependent Repositories: 0
  • Downloads: 1 Total
Rankings
Dependent repos count: 3.2%
Downloads: 3.8%
Average: 7.8%
Dependent packages count: 16.3%
Last synced: 6 months ago
juliahub.com: OptimalBranching

Automated discovery of optimal branching rules for the branch-and-bound algorithm

  • Versions: 3
  • Dependent Packages: 0
  • Dependent Repositories: 0
Rankings
Dependent repos count: 3.2%
Downloads: 3.8%
Average: 7.8%
Dependent packages count: 16.3%
Last synced: 6 months ago

Dependencies

.github/workflows/CI.yml actions
  • actions/checkout v4 composite
  • codecov/codecov-action v4 composite
  • julia-actions/cache v2 composite
  • julia-actions/julia-buildpkg v1 composite
  • julia-actions/julia-docdeploy v1 composite
  • julia-actions/julia-processcoverage v1 composite
  • julia-actions/julia-runtest v1 composite
  • julia-actions/setup-julia v2 composite
.github/workflows/CompatHelper.yml actions
.github/workflows/TagBot.yml actions
  • JuliaRegistries/TagBot v1 composite