QUBO
A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
Science Score: 67.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
Found 1 DOI reference(s) in README -
✓Academic publication links
Links to: arxiv.org, zenodo.org -
○Committers with academic emails
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (11.4%) to scientific vocabulary
Keywords
Repository
A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
Basic Info
- Host: GitHub
- Owner: JuliaQUBO
- License: other
- Language: Julia
- Default Branch: master
- Homepage: https://juliaqubo.github.io/QUBO.jl/
- Size: 5.63 MB
Statistics
- Stars: 37
- Watchers: 5
- Forks: 3
- Open Issues: 3
- Releases: 6
Topics
Metadata Files
README.md
QUBO.jl
[![Code Coverage](https://codecov.io/gh/psrenergy/QUBO.jl/branch/master/graph/badge.svg?token=ECM5OQ9T67")](https://codecov.io/gh/psrenergy/QUBO.jl)
[](https://github.com/psrenergy/QUBO.jl/actions/workflows/ci.yml)
[](https://psrenergy.github.io/QUBO.jl/QUBO.jl/dev)
[](https://zenodo.org/badge/latestdoi/614041491)
[](https://www.youtube.com/watch?v=OTmzlTbqdNo)
[](https://arxiv.org/abs/2307.02577)
*A Julia ecosystem for Quadratic Unconstrained Binary Optimization*
QUBO.jl is an all-in-one package for working with QUBO models in JuMP and interfacing with their solvers. This project aggregates and extends functionality from its complementary packages ToQUBO.jl, QUBODrivers.jl and QUBOTools.jl.
QUBO? 🟦
QUBO is an acronym for Quadratic Unconstrained Binary Optimization, a notorious family of Combinatorial Optimization problems. Recently, significant advances in computing systems and algorithms specialized for sampling QUBO solutions have contributed to its increasing popularity.
These novel tools include Quantum Annealing, Quantum Gate-Circuit Optimization Algorithms (Quantum Optimization Alternating Ansatz, Variational Quantum Eigensolver), other hardware-accelerated platforms, such as Coherent Ising Machines and Simulated Bifurcation Machines, not to mention traditional methods such as Simulated Annealing and Parallel Tempering.
Mathematical Model
Conceptually speaking, it is an optimization model with a quadratic objective function on binary variables and no constraints. Despite being very simple, these models are capable of representing other nonconvex global optimization problems.
math
\begin{array}{rl}
\min & \alpha \left[\mathbf{x}' \mathbf{Q}\,\mathbf{x} + \mathbf{\ell}' \mathbf{x} + \beta \right] \\
\textrm{s.t.} & \mathbf{x} \in \lbrace{0, 1}\rbrace^{n}
\end{array}
Show Description
Analizing the model attentively, let $\mathbf{x}$ be a **vector of boolean (zero-one) variables**. Take also the **vector of linear terms** $\mathbf{\ell} \in \mathbb{R}^{n}$ and the **strictly upper triangular matrix of quadratic terms** $\mathbf{Q} \in \mathbb{R}^{n \times n}$. Last but not least, consider $\alpha, \beta \in \mathbb{R}$ as the **scaling** and **offset** parameters, respectively. Note that in this kind of problem, $\min$ and $\max$ are interchangeable under sign inversion. Also, spin variables $\mathbf{s} \in \lbrace{\pm 1}\rbrace^{n}$ may be employed instead, assuming that $s = 2x - 1$ by convention.Quick Start 🚀
Instalation
```julia import Pkg
Pkg.add("QUBO") ```
Example
Given the following binary Knapsack Problem
math
\begin{array}{rl}
\max & x_{1} + 2 x_{2} + 3 x_{3} \\
\textrm{s.t.} & 0.3 x_{1} + 0.5 x_{2} + x_{3} \leq 1.6 \\
& \mathbf{x} \in \mathbb{B}^{3}
\end{array}
one could write a simple JuMP model and have its constraint automatically encoded by ToQUBO.jl.
Show Code
```julia using JuMP using QUBO model = Model(() -> ToQUBO.Optimizer(ExactSampler.Optimizer)) @variable(model, x[1:3], Bin) @objective(model, Max, x[1] + 2 * x[2] + 3 * x[3]) @constraint(model, 0.3 * x[1] + 0.5 * x[2] + x[3] <= 1.6) optimize!(model) for i = 1:result_count(model) xi = value.(x, result = i) yi = objective_value(model, result = i) println("x: ", xi, "; cost = ", yi) end ```Overview 🗺️
Citing QUBO.jl 📑
If you find QUBO.jl and its packages useful in your work, we kindly request that you cite the following paper (preprint):
tex
@misc{qubojl:2023,
title = {QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization},
author = {Pedro {Maciel Xavier} and Pedro Ripper and Tiago Andrade and Joaquim {Dias Garcia} and Nelson Maculan and David E. {Bernal Neira}},
year = {2023},
doi = {10.48550/arXiv.2307.02577},
eprint = {2307.02577},
archivePrefix = {arXiv},
primaryClass = {math.OC},
}
This project is part of a collaboration involving PSR Energy Consulting & Analytics, the Federal University of Rio de Janeiro (UFRJ), Purdue University and the Universities Space Research Association (USRA).
Owner
- Name: JuliaQUBO
- Login: JuliaQUBO
- Kind: organization
- Repositories: 1
- Profile: https://github.com/JuliaQUBO
QUBO modelling, solvers & tools. A joint work of @psrenergy and @SECQUOIA
Citation (CITATION.bib)
% If you use this software, please cite it as below.
@misc{qubojl:2023,
title = {QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization},
author = {Pedro {Maciel Xavier} and Pedro Ripper and Tiago Andrade and Joaquim {Dias Garcia} and Nelson Maculan and David E. {Bernal Neira}},
year = {2023},
doi = {10.48550/arXiv.2307.02577},
eprint = {2307.02577},
archivePrefix = {arXiv},
primaryClass = {math.OC},
}
GitHub Events
Total
- Watch event: 7
- Issue comment event: 1
- Fork event: 1
Last Year
- Watch event: 7
- Issue comment event: 1
- Fork event: 1
Committers
Last synced: 6 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Pedro Maciel Xavier | p****r@p****m | 64 |
| pedroripper | p****r@g****m | 48 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 6 months ago
All Time
- Total issues: 6
- Total pull requests: 3
- Average time to close issues: 15 days
- Average time to close pull requests: about 1 month
- Total issue authors: 5
- Total pull request authors: 2
- Average comments per issue: 2.0
- Average comments per pull request: 0.33
- Merged pull requests: 3
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 0
- Pull requests: 1
- Average time to close issues: N/A
- Average time to close pull requests: 7 days
- Issue authors: 0
- Pull request authors: 1
- Average comments per issue: 0
- Average comments per pull request: 0.0
- Merged pull requests: 1
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- pedromxavier (1)
- bernalde (1)
- JuliaTagBot (1)
Pull Request Authors
- pedromxavier (2)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
-
Total downloads:
- julia 11 total
- Total dependent packages: 0
- Total dependent repositories: 0
- Total versions: 5
juliahub.com: QUBO
A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
- Homepage: https://juliaqubo.github.io/QUBO.jl/
- Documentation: https://docs.juliahub.com/General/QUBO/stable/
- License: MPL-2.0
-
Latest release: 0.3.2
published over 1 year ago
Rankings
Dependencies
- JuliaRegistries/TagBot v1 composite
- actions/checkout v2 composite
- codecov/codecov-action v2 composite
- julia-actions/julia-buildpkg v1 composite
- julia-actions/julia-processcoverage v1 composite
- julia-actions/julia-runtest v1 composite
- julia-actions/setup-julia v1 composite
- actions/checkout v2 composite
- actions/checkout v2 composite
- julia-actions/setup-julia latest composite
- actions/checkout v2 composite
- julia-actions/setup-julia latest composite