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.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 498d52645af2c8a346426ca33ba8e86224150bd0e563d55b5ccb151732d7848f |
|
MD5 | f8447db2561cdb07950439374a42b69f |
|
BLAKE2b-256 | ac716c0b6661c338638d72456b15efaf4b77c5709f1d4961188cc6025c367ea8 |
Hashes for dwave_greedy-0.1.1-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f1061385eb15fcc71958cb6de6f7326b1048898dc287c5f0b092b86e261c9cc |
|
MD5 | efcc3a0ff85a1eb31e4b2d448c3d1f45 |
|
BLAKE2b-256 | 6b623a42e3fc47f3538f2b2e077e6c492f71b6419790922b9c344ac1cea52507 |
Hashes for dwave_greedy-0.1.1-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0569b1b5b7351878d51433894312c35ac19857b3761bbd55ea00efccbf62a1ef |
|
MD5 | dba121ea836a3f7ac51309d450e1aaaa |
|
BLAKE2b-256 | e79894a15f61c8a9cca96ec4f65f81f3a1da2a6323a259b9226a53f17dbef0f1 |
Hashes for dwave_greedy-0.1.1-cp38-cp38-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9efac4e72e54a6acdf2e5bb8fdb55b3ae5a189486dfaa90a1eaecea24706d9ea |
|
MD5 | b98efc56f778133773802ce4a642c244 |
|
BLAKE2b-256 | fbeecfccc32a17edafe729140e8066fc3942ca05b99f714b39894651175c65ab |
Hashes for dwave_greedy-0.1.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e712e5195f35c2b1ad9ae59f46939523f9642e9839334aa880d5647ebb9e21fd |
|
MD5 | b7a1de98788fc614b4f4ca9470eebfa3 |
|
BLAKE2b-256 | 443d2dfad34b25fa7aa7e1144071ed77db1afd567cf12e82c88f9cd972a4fee1 |
Hashes for dwave_greedy-0.1.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ddacb1c62ab2b58eaae523ab8833874d2fd6abac72dc305a4229aa4559a273a7 |
|
MD5 | d8003d1b44fd641027284aa2b4ea780b |
|
BLAKE2b-256 | df43852ca357562eabce588295008bbdaa649ca0ad7f3cd98f5976057079c2a1 |
Hashes for dwave_greedy-0.1.1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 30d9ee040b129ce521db360017eea1930b198a236155d3f7ad63b6f5507593a0 |
|
MD5 | 92646efcafe9ab1fb1e2ccf8fb106dba |
|
BLAKE2b-256 | 5acdc48e50dac84c6968b750967fc8487ef1b5fc7bec63fd300e9c680f3e35e8 |
Hashes for dwave_greedy-0.1.1-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c1068fc5f91a658c654072c3a4d80254fb87a234c94407e406d20d4bfb14119f |
|
MD5 | 42c920324cce00790e31c30ae8573816 |
|
BLAKE2b-256 | 28a2f9a8d0e346001cd622462dc96b2adbb62651465c24ad5f51d88441cda34b |
Hashes for dwave_greedy-0.1.1-cp37-cp37m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 13f75eb9904cbe19f9cc3b3f17c540e08b3ae3a94045234241a84a10296d070b |
|
MD5 | b715900cb359242cc6f715763ad0cb19 |
|
BLAKE2b-256 | a4dbcc86eb0be22051c35319230a1e857847f592e34387134b0b74bdc0afb6fb |
Hashes for dwave_greedy-0.1.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 59011f16a5a0c3f8fc15f03c49650aa0310de847373c9b9b95b08a94888f932f |
|
MD5 | 0d094bd1b0116f0e66c3f70b8ba927b6 |
|
BLAKE2b-256 | d6bc1d10bbd2027d577f100bd06441bdc579f41065ba0f7818c44d970099c3eb |
Hashes for dwave_greedy-0.1.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 13b0404995f0d80fde5b11ddd461ccc7fff3c9d0d5e1bed6739e9e34bb4de726 |
|
MD5 | 99de6f0f3d387b29bfb972298c5f4979 |
|
BLAKE2b-256 | c1d6b7d6612f4d48572eb87733a891fda3ac61102704c4416313ab99f285b83f |
Hashes for dwave_greedy-0.1.1-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d5e43cf2c7e3c5ddc80d278ac88ce7a4217dc24ee364d4697ceb1374bd3964fa |
|
MD5 | 951ec8a6b2ef7071abd9f2b185b83f5f |
|
BLAKE2b-256 | 37974aaf112272ca4e2687400fd1b9880f3b9eb62876adce70b58b0c70bf235e |
Hashes for dwave_greedy-0.1.1-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f4ae91b44618f395bc9fc19d19fc07b7cc302816af7f7b66359a717af7a75370 |
|
MD5 | 4c90b1a3c7c0526b4e17e22959e17920 |
|
BLAKE2b-256 | 71d320c6fbaae0f4db76f400e9863700e536718d0ac1eb027cfc516b5f385c99 |
Hashes for dwave_greedy-0.1.1-cp36-cp36m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d9cb105aeec9efcfd45d5b857937c802163b07df91416c72c683bc13827fac8b |
|
MD5 | b2ba5c16eb560be72e04a2abc263e20e |
|
BLAKE2b-256 | 3694874d4e38fedf3310c06927712e62145951378c08f5e6709ae187aa984dba |
Hashes for dwave_greedy-0.1.1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4fe566f5b8bbadb29ab098f8d34c558ff56b3d6403bea02bdf0ca35d47cb3e25 |
|
MD5 | a92024c4a176a1466660d79b6160c37d |
|
BLAKE2b-256 | 7609146e4df7dc2f093331c25a41db6be3c84a1f38c4ff3893aa7ef55cfed21e |
Hashes for dwave_greedy-0.1.1-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 74b36cca4c9e22be547683216955723e37700bb67b1203e9c0ccb90cfa8091ed |
|
MD5 | 123da57f38700f8c733d5bb90571f4d1 |
|
BLAKE2b-256 | 4c99b2eb9ee8e4f51dae48b26ec3bc377a2b368344fb5fc00aefd67b8821177f |
Hashes for dwave_greedy-0.1.1-cp35-cp35m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0db008da43a0a18f07a8cbff0182a24b44c270997b7c335fdab1989d6974d57a |
|
MD5 | 9d3b30831cd0bb2cf9a92b4dec9edf7f |
|
BLAKE2b-256 | 50d176f69d98b9a59f4ae297ef3785fcfd85b5f1db50c802e0c4669af427b288 |
Hashes for dwave_greedy-0.1.1-cp35-cp35m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fb94cd89fc56b542f1ef38fc14e157ade316f9989133be4b5d3a5951dde2d784 |
|
MD5 | 90c97f036dc90926135f6cbcc5461326 |
|
BLAKE2b-256 | bc583c4047e5ca1f4f852266227cbd00dc070fcf0522edb6893e7bda87340706 |
Hashes for dwave_greedy-0.1.1-cp35-cp35m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fe0481d44d2fcf1a5cb7321064d96956db51eb7e8366564b8bb11e0ac3d50326 |
|
MD5 | fcd5ea545acb4ec1ecb1fcee49a588ee |
|
BLAKE2b-256 | ca64d7e68ddbbfb5c328b4df42bf58a98ec22c5e2c8f6f0affe8e4cc7ade74a7 |
Hashes for dwave_greedy-0.1.1-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0a7c04b485897db352abcdf7d0ec2c2cb5f88681d1b738478f3bd35a57c01020 |
|
MD5 | ec581089dc497e2351a50e1c75908602 |
|
BLAKE2b-256 | e13c950a875faafc11054e54e96cc00fc52da8fb9c91ac52d4d87616905d15f9 |