Ocean-compatible collection of greedy/brute-force solvers/samplers
Project description
dwave-greedy
An implementation of a steepest descent solver for binary quadratic models.
Steepest descent is the discrete analogue of gradient descent, but the best move is computed using a local minimization rather rather than computing a gradient. At each step, we determine the dimension along which to descend based on the highest energy drop caused by a variable flip.
>>> import greedy
...
>>> solver = greedy.SteepestDescentSolver()
>>> sampleset = solver.sample_ising({0: 2, 1: 2}, {(0, 1): -1})
...
>>> print(sampleset)
0 1 energy num_oc.
0 -1 -1 -5.0 1
['SPIN', 1 rows, 1 samples, 2 variables]
Installation
Install from a package on PyPI:
pip install dwave-greedy
or install from source:
pip install git+https://github.com/dwavesystems/dwave-greedy.git#egg=dwave-greeedy
Note: installation from source involves a “cythonization” step. To install project requirements automatically, make sure to use a PEP-517 compliant pip, e.g. pip>=10.0.
To build from source:
pip install -r requirements.txt
python setup.py build_ext --inplace
python setup.py install
Examples
Simple frustrated Ising triangle:
import dimod
import greedy
# Construct a simple problem
bqm = dimod.BQM.from_qubo({'ab': 1, 'bc': 1, 'ca': 1})
# Instantiate the sampler
sampler = greedy.SteepestDescentSampler()
# Solve the problem
result = sampler.sample(bqm)
Large RAN1 sparse problem (requires NetworkX package):
import dimod
import greedy
import networkx
# Generate random Erdős-Rényi sparse graph with 10% density
graph = networkx.fast_gnp_random_graph(n=1000, p=0.1)
# Generate RAN1 problem on the sparse graph
bqm = dimod.generators.random.ran_r(r=1, graph=graph)
# Instantiate the sampler
sampler = greedy.SteepestDescentSampler()
# Run steepest descent for 100 times, each time from a random state
sampleset = sampler.sample(bqm, num_reads=100)
# Print the best energy
print(min(sampleset.record.energy))
License
Released under the Apache License 2.0. See LICENSE file.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for dwave_greedy-0.2.0-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1070e982a3ea2468d1ed035759caa0772257826cb8da903dbd012bb0a2a28c23 |
|
MD5 | ad866a65a755e568152d78968c0f81c5 |
|
BLAKE2b-256 | 4e033549b29464011161e6e9e55889c212f31f8a82caaecd3c85dfdef6869ee1 |
Hashes for dwave_greedy-0.2.0-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d3539c852f25dad10b2c2b9fc56eddbeb3449b5aac8f387031f43dbac22ef32e |
|
MD5 | 0fbc34fe271b24651dec5e81ef82bc6c |
|
BLAKE2b-256 | 585a9ec71342d383264bb75f01fb10b59ef5ba024ae87d92a439a6ec65fce53e |
Hashes for dwave_greedy-0.2.0-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 02ac42af9c86ad63c82fdec69136fd8c9a760d00c5ae1524f30b2f303f8ff1de |
|
MD5 | 8708006af2532798b9e4c9152dc53875 |
|
BLAKE2b-256 | ac42dd43426f59bb49a82ac23ea04b0ad562054467a3700e1c4a982010dcd4f5 |
Hashes for dwave_greedy-0.2.0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 94529ac48221a83b12b3cf3c212f2882e3d89edb1cc1c05d144198961dabf0bc |
|
MD5 | f2ad8461b5b2a32218cddb8bf16a0829 |
|
BLAKE2b-256 | e7bc9427300d2e77598bff0f412f89b0acfc927dad817537cf6ce09bd81bc215 |
Hashes for dwave_greedy-0.2.0-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 678d80c50a7b391588deffd9bc5ef7143c53b74c502169e5ec9f3b4751b40515 |
|
MD5 | 118d797b3d2fef1536ac233dad071ac6 |
|
BLAKE2b-256 | 9ebc63793eb6d3fc52767866c1acf77038a925e320dc7d7cfed99e61a09a489e |
Hashes for dwave_greedy-0.2.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbdcf620b5f96b7dcd352d8e05fb3e00ee51b98f7d4c96d2eb6044ca0392b011 |
|
MD5 | 02453276711ae48441c7bf381bfd1324 |
|
BLAKE2b-256 | d2318995fcb769190403f51116ab3252949c3888008b5d055e8dd9dc39cf1779 |
Hashes for dwave_greedy-0.2.0-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ff1d6bb53b84db5d620c5644b3de6c17871ad91986f4f5c51f1d537d2bf3eb8d |
|
MD5 | b8fd204870fd56586628a10d18ead3eb |
|
BLAKE2b-256 | 2e64f0012f5e08aa40bf28a8f7bd6464279174e776c9b5669821f3bef59665bb |
Hashes for dwave_greedy-0.2.0-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1458d1162a65b54efeb4bb90207155fcdacb1fdff15d0f58e8c294cbc3d0eb83 |
|
MD5 | 8e0835a784070ad1d5910e9d3fa28a9f |
|
BLAKE2b-256 | fb88d5a2abacc3c0470e1dbf44dbd18732e25dd7d371421c5fb278f6ba1e14cf |
Hashes for dwave_greedy-0.2.0-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 25adacf3d5529044452ac27d3e823b55bcb71b016ad868a8421bbf7d44417ffa |
|
MD5 | d3edad9e47cd21e4f2ec8c2ba6a3b1b5 |
|
BLAKE2b-256 | 72410552de6301847a641f25a3f6e3dbbc100df6b77d167b453411999e9b9823 |
Hashes for dwave_greedy-0.2.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2e9ace74453d531cf20f40621b91643c52c4791eea260dce58b893918e539ebb |
|
MD5 | 3efce11366c0dfab7c054c9221e62659 |
|
BLAKE2b-256 | e62545f297d119fc9c52a909856380a9058cd6b1205ac20b3bb84f291e19550f |
Hashes for dwave_greedy-0.2.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7ed4532ebaf245cfc0de4cddd2dae5d9975874fdd1e3bb592b56366cf89723aa |
|
MD5 | 155a9798b42bcb34c95e1d022bf44d82 |
|
BLAKE2b-256 | 4be63c2a4ed78f731c1fe5dfa15e06c9f644a4dfaf787bf4eed254057325e045 |
Hashes for dwave_greedy-0.2.0-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6f8f399fe6dc2dee0599ee3853f4c2da4afe81ea891063c3178077342dbcbaae |
|
MD5 | 63e34bf499ff03ab7be2bb7c6b37e76b |
|
BLAKE2b-256 | 3e6dedf2a903fae65ec7ec1c83a51cab8d99224bdae2946fd176c2a660dbf17f |
Hashes for dwave_greedy-0.2.0-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 563a930d85c207ae0d7c4298e0abfec09ad0bf90c3e566cbdb0d602c2f4d03b7 |
|
MD5 | d442bffeefd74754b3153d131518119b |
|
BLAKE2b-256 | 00d4b3b2267013c2039103878d29374cd422ce8556ddf032642d659a77ae0b34 |
Hashes for dwave_greedy-0.2.0-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8f819cd113ef5705d7229472b993504ad8c9f28eaa2d7778a6777b524cb03bf7 |
|
MD5 | 3b550cbcc3acae0dc712e51ed91a61e1 |
|
BLAKE2b-256 | 8ccbd30df16af5171c66844e40dab2258d3e8d9c07d05f7523141ef674a0e57b |
Hashes for dwave_greedy-0.2.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2a62ddd6c8da3cd0bdbb7575d07087685167e3817424a47bafc2f18097377082 |
|
MD5 | 5be880f45b97cae62538221cb73ea075 |
|
BLAKE2b-256 | 49dfd4b4d2300457a491bc9e7ebb25dbd86e2bad690907e358b268a73115faf1 |
Hashes for dwave_greedy-0.2.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6d4d0c04f0bbfcfacc39118570cf1ecdb08943bd8a28e0b83f8a464214982965 |
|
MD5 | 1d9e06ffeabfe19243a275181d5ba074 |
|
BLAKE2b-256 | 66b71821e0df2a4da298f4cf755514af9c506f89ff0fa4267a1c1666a3d2d247 |
Hashes for dwave_greedy-0.2.0-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fa91ffb7138c7983fddcd35ee4913e65d088cb122f53b033d56b9263f7e62e1e |
|
MD5 | efd9c2916551b43f49c6c06e377d5ae5 |
|
BLAKE2b-256 | 8bcc2d13b28cd1404ee72ed4cc305caafab97ea88ae0a2ecccb760d5fd248763 |
Hashes for dwave_greedy-0.2.0-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b65981e18658e2a3dc4bca99caec4f271a27d7817d68c492bd3567ed877c679 |
|
MD5 | 59df3a248a005af18544757ce85cb7b7 |
|
BLAKE2b-256 | efeb36fde68c58bec976d7f71682097f9d77523c99e0ab4d1dc2d4864f572c47 |
Hashes for dwave_greedy-0.2.0-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4891e55fe8252fe0b982b15208120b0958234aa98eeb87cd079fac347ba3d75b |
|
MD5 | 6a2bec747729231b7c009fef529189fb |
|
BLAKE2b-256 | e1219e7d86b2eefc35d747b998025f7f3674c48ea00c3077be463aae713c8e02 |
Hashes for dwave_greedy-0.2.0-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e75029565cccbb7de9466444613f2c3a9ebfd2c28679d029309f7e491b6fe546 |
|
MD5 | f70247e6f3caddf88215794be0adbea9 |
|
BLAKE2b-256 | 2f7096960c1ba7d794428c89b16f61548b99374dc6509bfaa58bab6ef48a7e74 |