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:
USE_CYTHON=1 pip install git+https://github.com/dwavesystems/dwave-greedy.git#egg=dwave-greeedy
Note: USE_CYTHON=1 forces Cythonization and proper build from source. When building from PyPI package source (which includes Cythonized files), this is not necessary.
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.1.0rc2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fd3019769282168d3ebd07c499e58eae32e363dda0d0f37ad8ed5ab9c27e7e77 |
|
MD5 | dc783b4b55f7e9d090e76dfb37c19cd1 |
|
BLAKE2b-256 | 76220d68be5e8dce95287b99cfc0b81866d4d59e328b1c775a2141b9896a523a |
Hashes for dwave_greedy-0.1.0rc2-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2d24633c03f85190dca93ff3fff5f6fc7ec7729dcdfeb39b6675c28ae1cc2193 |
|
MD5 | 05799e4cb565170d7078ae6744a44aa3 |
|
BLAKE2b-256 | d1f05d49b844d8d5c998eae6dde12d3d290b02f1baf2136c51e5174c04b54b07 |
Hashes for dwave_greedy-0.1.0rc2-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0fe83136d5fa3c20d9945ec73d2209c96f044c42eb93dc3c137b060f06c53207 |
|
MD5 | 3ae9136d77dcd7048c3f8024f22bc731 |
|
BLAKE2b-256 | e6a3f485404aef4f82539dee42f7aaaf1bd5702da3af4820b3b8ab1188341e3e |
Hashes for dwave_greedy-0.1.0rc2-cp38-cp38-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1ccdb11f6edf2949b404c9616824e0b33e89ee586718be9aee1bb918c7239be2 |
|
MD5 | daf813be6580a43725d4859d6b6303f7 |
|
BLAKE2b-256 | 889c41225b3db6f74ac7a63889c78d1172533079b3a4a11340f1e52228d839ff |
Hashes for dwave_greedy-0.1.0rc2-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 39691fcb7b398f9d907189c73f22d366a2693e53c0f48a2fc8009949d72f9306 |
|
MD5 | df9e00ace5947b6f72d8391619211c00 |
|
BLAKE2b-256 | 43d5bdc9f1e6e599872c7881f3b819f79263874fb5ddface2c0c66f63cee4d6b |
Hashes for dwave_greedy-0.1.0rc2-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 423e72a756f0e0581a1f435057e2c6c3a77761c86a970fd9e7a8c9290f5ff880 |
|
MD5 | 979cb190d5e669a72ef253b1832affad |
|
BLAKE2b-256 | 0eaa94e5c9f4e60e8cb442b26a11b48163c5e5b57fd9664c757cfd502357238c |
Hashes for dwave_greedy-0.1.0rc2-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e2c73e81550e54e1770951f2670e7a4dfb77cb99c832124eda70e85a6cfa4b0 |
|
MD5 | 79d992ea1f48767e01466209eb84c6e7 |
|
BLAKE2b-256 | f6c8c02d6e9aa9b4385982f73bd657e8c1160fae64151c02cb3b2356c341933c |
Hashes for dwave_greedy-0.1.0rc2-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a4f9a2eba3779e97e3797523a075a849dee160c55d515216abed67f234627efb |
|
MD5 | 896097dbe03060af43e523115271e122 |
|
BLAKE2b-256 | d3a69922aa4fe333888806b3c547984c22a1d1a81541eb27b449d2273df60fec |
Hashes for dwave_greedy-0.1.0rc2-cp37-cp37m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f5abb953d4974301c6b4ec1b2482b47924aeab73fc7a04b3f3cbe61a3cc5f61 |
|
MD5 | 0cb9cb3b890dde2d0a939aa4a02aad78 |
|
BLAKE2b-256 | 8ea8c2592ee611d88fb4d609a285ab914c6086bbe92ef0e8cc985dc055134975 |
Hashes for dwave_greedy-0.1.0rc2-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be3cb4815a9d547ee2e836d32b8f7aee88f8d609287f92be4c73c2b2f650c6e1 |
|
MD5 | 6ed2819e75eaf0f452b7218848f48a6f |
|
BLAKE2b-256 | 55787124e1ebbbfe39764b30edd2ec876375bbc792e94466955ce4793776a247 |
Hashes for dwave_greedy-0.1.0rc2-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e5dd56b4bdb76872ae24846446a16b8640835784e7f14c45cc4cbdc96034af9 |
|
MD5 | 05c9f6e0af56e6a5ef1968de176b6526 |
|
BLAKE2b-256 | b0dab6527b7a0f50c0cc447825b357d8743cb7517fb01acb6676c7920b907d7f |
Hashes for dwave_greedy-0.1.0rc2-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7e6f6b53ff86988622ec8e0ecbbbde5a3188fa659f613ddae6e7f26aed033ff0 |
|
MD5 | 41e05dca950160c13d4b48f962967015 |
|
BLAKE2b-256 | fadf197cb3801a17e46c9c678ea06355e7f729bb9ab17476f67afaf72ba874f2 |
Hashes for dwave_greedy-0.1.0rc2-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4b5b39f2a29617dca32ed64ecd18c530511a8876438603c2a261e32f9c99a5b4 |
|
MD5 | 810ae0f60971a888fd6d127622c8a661 |
|
BLAKE2b-256 | 2db37446a83d56af2abd6d5ed9c23c6877e846d9b56ee844dd851d5d36085878 |
Hashes for dwave_greedy-0.1.0rc2-cp36-cp36m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 99ba1a9e116fab18ae0ba9f8dc66719298688556bb13b1daabcf9556ca4315ab |
|
MD5 | 9191e7ef16e8b0eb39ccc1fafb3f3782 |
|
BLAKE2b-256 | 51ec33a563c599bb4900e535b1a91a579d4646f76dd0f19098922a9dc3971753 |
Hashes for dwave_greedy-0.1.0rc2-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57fbd641840a08aa6a359f9d42950905be21b1866e237d905c7ac0e329e669ea |
|
MD5 | 16221019612789269214b32f3ba8de3b |
|
BLAKE2b-256 | aed4bbc2449f561f824388b94ac0c879bb51777564d84bff593557e66d3362b4 |
Hashes for dwave_greedy-0.1.0rc2-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 30231c1c00f9bc8384203ce983539f8c56dd370390f9df504dc2e1c1cfb477f6 |
|
MD5 | bc68969340f7a737b3775ad7f04b1730 |
|
BLAKE2b-256 | 658c8c81467f55327cdf2aa11ffaeae8e908c7cb604b6e3cf9363beae1bbb31d |
Hashes for dwave_greedy-0.1.0rc2-cp35-cp35m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d9bf5c3bffc55aecff6fd99fa9527dbad6b4aef0397b655396fb199ab722bf48 |
|
MD5 | 721d03e5aac0576235ec5f1e91042c65 |
|
BLAKE2b-256 | 1c9f988127f5a801ab4c45b0e66d5b256d276d1816521bb83f9d5bcb2a46dcea |
Hashes for dwave_greedy-0.1.0rc2-cp35-cp35m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 91757c72185d68c8318b0da464750cd0d5abc037f5d7522e26d2ab162e6458c6 |
|
MD5 | 3fafad6cfc5bab45078518f75b64f189 |
|
BLAKE2b-256 | 7a872087825d8b75e06410faa935329f861367fd58c3da0d9cbe1f756cdd9d37 |
Hashes for dwave_greedy-0.1.0rc2-cp35-cp35m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b878671270da1fea388592bd56a4507c162e89a03dee886d689144d60d1bfcb6 |
|
MD5 | b4527c61e142076a031e0e3c2c4eebb1 |
|
BLAKE2b-256 | 1df5dd467de227ce8f23fea0153d50c027d5158816711bfbde92984ac3312cf8 |
Hashes for dwave_greedy-0.1.0rc2-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 441620a23df0216af3618c5721ec9d581a6f7290748b19186f70197923446793 |
|
MD5 | 8891ad2da3cd5644a29470e013b83b77 |
|
BLAKE2b-256 | 5e4caa87ac88acf86ce68bded92cfd527cb2f92278f97cba71cb1cf0c97c2e78 |