### 3 releases (breaking)

0.3.0 | Jun 2, 2024 |
---|---|

0.2.0 | Apr 27, 2024 |

0.1.0 | Jan 12, 2024 |

#**325** in Math

**159** downloads per month

**BSD-3-Clause**

175KB

3K
SLoC

# Hercules: QUBO Solver and Heuristics Toolkit

Hercules is a Rust library for analysing, finding approximate solutions, and finding exact solutions for Quadratic Unconstrained Binary Optimization (QUBO) problems. It is mostly a side project for me during my PhD, so please be understanding of this.

## What is this library for?

Hercules is designed as a simple, easy-to-use library for solving QUBO problems. It is not necessarily designed to be a state-of-the-art tool but a toolkit for quickly prototyping and testing QUBO methods. That said, Hercules is designed to be fast and written in Rust, a high-performance systems programming language.

## Progress

Hercules is currently in the early stages of development. The following features are currently implemented:

- QUBO data structure
- QUBO problem generation
- QUBO Heuristics
- Initial Branch & Bound Solver

When referring to the solver, there is a world of a difference between naive implementations and useful for real world implementations. I am trying to iteratively move the solver to the category of useful for real world problems, without punting to much of the responsibilities to dependencies. This is documented in a very high level on my personal blog. As it stands, it can generally solve dense and sparse problems below 80 binaries. But I hope to push the capabilities to larger problem sizes, and solve the problems we can much faster.

- Initial Branch and Bound
- Initial Presolver
- Warm Starting
- Variable Branching Rules
- Multithreaded B&B solver
- Problem Reformulation
- Modern Presolver
- Warm starting subproblems
- Beck Optimality Proof

## Simple: Read and solve QUBO example

This can be used to generate get and generate high quality (depending on the search heuristic) solutions to the QUBO problem being considered. For example, the following code shows how to use the gain criteria search to find a local minimum of a QUBO problem.

`use` `hercules``::``qubo``::`Qubo`;`
`use` `hercules``::``local_search``::`simple_gain_criteria_search`;`
`use` `hercules``::``initial_points``::`generate_central_starting_points`;`
`//` read in a QUBO problem from a file
`let` p `=` `Qubo``::`read_qubo`(``"`test.qubo`"``)``;`
`//` generate an initial point of 0.5 for each variable
`let` x_0 `=` `generate_central_starting_points``(``&`p`)``;`
`//` use the gain criteria search to find a local minimum with an upper bound of 1000 iterations
`let` x_1 `=` `simple_gain_criteria_search``(``&`p`,` `&`x_0`,` `1000``)``;`

## Advanced: Mixing two local search heuristics

The subcomponents of Hercules can be used independently and interchangeably allowing us to create new heuristics on the fly. For example, the following code shows how to make a new local search function based on 1-opt and gain search. Each iteration of the algorithm is defined as finding the lowest energy point in the neighborhood of the current point and then doing a large-scale flipping operation, flipping bits based on the gains of the function. This allows for simple, easy-to-understand, and easy-to-implement local search algorithms (amongst other ideas).

`use` `hercules``::``qubo``::`Qubo`;`
`use` `hercules``::``local_search``::``*``;`
`use` `hercules``::``local_search_utils``::``*``;`
`use` `ndarray``::`Array1`;`
`use` `rayon``::``prelude``::``*``;`
`use` `hercules``::`initial_points`;`
`use` `smolprng``::``{``PRNG``,` JsfLarge`}``;`
`//` A simple local search heuristic that uses 1-opt and gain-criteria search
`pub` `fn` `simple_mixed_search``(``qubo``:` `&`Qubo, `x_0``:` `&``Array1``<``f64``>`, `max_steps``:``usize``)`` ``->` `Array1``<``f64``>``{`
`//` create a mutable copy of the initial point
`let` `mut` x `=` x_0`.``clone``(``)``;`
`//` flip the bits maximize the 1D gains
`let` `mut` x_1 `=` `get_gain_criteria``(`qubo`,` `&`x`)``;`
`let` `mut` steps `=` `0``;`
`//` run the local search until we reach a local minimum or we reach the maximum number of steps
`while` x_1 `!=` x `&&` steps `<=` max_steps `{`
x `=` x_1`.``clone``(``)``;`
`//` find the lowest energy point in the neighborhood of x (can be x itself)
x_1 `=` `one_step_local_search``(`qubo`,` `&`x`,` `&``(``0``..`qubo`.``num_x``(``)``)``.``collect``(``)``)``;`
`//` flip the bits to better satisfy the stationary conditions
x_1 `=` `get_gain_criteria``(`qubo`,` `&`x_1`)``;`
`//` increment the number of steps
steps `+=` `1``;`
`}`
`//` return the best point found
x_1
`}`
`//` create a random QUBO problem
`let` `mut` prng `=` `PRNG` `{`
generator`:` `JsfLarge``::`default`(``)``,`
`}``;`
`let` p `=` `Qubo``::`make_random_qubo`(``1000``,` `&``mut` prng`,` `0.``1``)``;`
`//` generate 8 random starting points
`let` `mut` x_s `=` `initial_points``::`generate_random_starting_points`(``&`p`,` `8``,` `&``mut` prng`)``;`
`//` solve each initial point, in parallel
`let` x_sols`:` `Vec``<``_``>` `=` x_s
`.``par_iter``(``)`
`.``map``(``|``x``|` `simple_mixed_search``(``&`p`,` `&`x`,` `1000``)``)`
`.``collect``(``)``;`
`//` find the best solution
`let` min_obj `=` x_sols
`.``iter``(``)`
`.``map``(``|``x``|` `p``.``eval``(``&`x`)``)`
`.``min_by``(``|``a``,` `b``|` `a``.``partial_cmp``(`b`)``.``unwrap``(``)``)`
`.``unwrap``(``)``;`

This is actually a quite effective simple local search heuristic, and can be used as a starting point for more complex heuristics. Here, we can solve a randomly generated sparse 1000x1000 QUBO problem to within 0.5% of the optimal solution in about 15 ms on a laptop.

## Python Interface: Using Hercules from Python

Hercules can be used from Python using the Py03 crate. This is currently a work in progress, and a standalone package is not currently available. This can be built via maturin via the

command. However, the following code shows how to use Hercules from Python.`maturin develop`

Here we can use the python interface to use the simple mixed search heuristic we developed above to solve a randomly generated QUBO problem. This is a 1000x1000 QUBO problem with 1000 nonzero entries, and we solve it from a random initial point for 50 iterations. This takes about the same about of time as the pure Rust version, and we get the same solution.

`import` `hercules`
`import` `random`
`import` `time`
`#` set a random seed
random.seed(time.time())
# read in the qubo problem
problem = hercules.read_qubo('test_large.qubo')
num_x = problem[-1]
# create a random initial point
x_0 = [random.randint(0, 1) for i in range(num_x)]
# start timing
start = time.time()
# solve the QUBO problem via the mixed local search heuristic with, initial point x_0, for 50 iterations
x_soln, obj = hercules.mls(problem, x_0, 50)
# stop timing
end = time.time()
# print the objective value of the solution
print('Solution: ', obj, ' in ', end - start, ' seconds')

## Docker

A Docker image is available here. To run this, pull down the image and run the following:

`docker run ``-``-`platform linux`/`amd64 dkenefake`/`hercules`:`test python pyhercules`.`py

#### Dependencies

~**77MB**

~1M SLoC