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.0-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 20d99051ad4dc77d852fd2a3ec5896d4deff8e75c033a15abc16a0f52f1b947e |
|
MD5 | 0035ca01b358a404efcc58df46ab546a |
|
BLAKE2b-256 | 2263e653a8c8d5f46989042418fbaa0c7beca55febe7555d70ba69d5a68eb3cb |
Hashes for dwave_greedy-0.1.0-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 175aecfcf40a8932548736306a2acf303cbc1ffc2b6790375b52fc30f4370a05 |
|
MD5 | 709bc3b4a038ff37eb1b6560abb3264f |
|
BLAKE2b-256 | ac82853fc86a4c54bfa0e92ae7d271abda48f406c9500d6f4ada1be518ee2ce9 |
Hashes for dwave_greedy-0.1.0-cp38-cp38-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 65a6df5376d1823aeb362858e360325acf02907d92ea852daa1ba2617d94bf64 |
|
MD5 | 8fd4c573527e46b1f9bfe558b9b7bd65 |
|
BLAKE2b-256 | e22153adc1d98f95fe3d0e2a51ed54578062564d49ec7ed6628142b6fff81f0f |
Hashes for dwave_greedy-0.1.0-cp38-cp38-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2eef7768f2b73c51de605406bbef8d9ca2d24c6a6b01cca6bbea8a77ec78b4b0 |
|
MD5 | b42288e3d4ec4e3622643b37a704ba24 |
|
BLAKE2b-256 | 9e23f4e929d40057668e724e9f807cf59c8d952946c42dbdfd218d095657e299 |
Hashes for dwave_greedy-0.1.0-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 20479b5371e4809f372cb1e8ca6d1b355b044dd747e21f3245680fecd4e85b3f |
|
MD5 | 35d111d57aa415fb7bdad807f1a6efc2 |
|
BLAKE2b-256 | 32ef02acd8d3d4a8472ec97a729bf618db92ee0633a7c2968ac8dc9ac0d275f3 |
Hashes for dwave_greedy-0.1.0-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 31b02e0c0409b1bde565e30c17ff43dd6f38c0a710a9a82c56cd48ba92c2ab8c |
|
MD5 | d8b476924b7b77e98eb7742893762445 |
|
BLAKE2b-256 | 7d52354c837a5146d3a36b49dc7bc71a3fb6d85b455c0ef40861e72b57824981 |
Hashes for dwave_greedy-0.1.0-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 759f8d46dfd2b463f5ffedf28bd0feb08894ba4d8ca5fba592cf3f3760262058 |
|
MD5 | ee8b63852b9a291017f4def8de0c6827 |
|
BLAKE2b-256 | 0eb3ddc5977aaeb503e14f196904f418f3e81835d254706d0c7742561917823b |
Hashes for dwave_greedy-0.1.0-cp37-cp37m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6269a89104bfb573563119e950de42ac072e2206a632f60b4f17d4c95b80ae63 |
|
MD5 | b1c91b5027cc057ffecb3563639f68ee |
|
BLAKE2b-256 | 686cea09f48cfb812ff0d7b4aae7038f7f2d2b0c4af63bcfef74fa9e5a422de6 |
Hashes for dwave_greedy-0.1.0-cp37-cp37m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8abb46b28302c7f9da4eefadeada39b97a5ed277f5e26b5a6bc0b7445549914c |
|
MD5 | 7d600d4eee13fb4a6594ee69497e85bd |
|
BLAKE2b-256 | 95405e9b921cd06559f2b745fe17b608c6db1c9b94b09af8bf439d74cb9b71c6 |
Hashes for dwave_greedy-0.1.0-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7662638909cd675ee437182d3066ff92b993049e416a005893e08f02732eb9d6 |
|
MD5 | e9201303ccbfce9b8321fac0843fc3e3 |
|
BLAKE2b-256 | 1094acfd4c372617111ac4a264fdd672fd423a028b040ae69f242e460b2490be |
Hashes for dwave_greedy-0.1.0-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce861072445e94fdee049809520fc689578b169d7569652fe42ac421602cb422 |
|
MD5 | 861164802ce3ebba3f935bce83a7e818 |
|
BLAKE2b-256 | 9cb498e5edf375f9cee45484db1fa430c5aec228ae801dcf0e1a606e00277cde |
Hashes for dwave_greedy-0.1.0-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 51cc8c14f7389253563cbf9bf2528c30bd9e68f078e4647c33c4ec76f7d5ac92 |
|
MD5 | 64199506e32d57e86e831f2f46778e00 |
|
BLAKE2b-256 | ba19d80c6217360698af999292513d00f38070b752833d3b943967cfc230b92c |
Hashes for dwave_greedy-0.1.0-cp36-cp36m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dfc238b3eb62127ff5d0d5b42413aaf1e3c8966432b78a65cba16c988a2e18fd |
|
MD5 | ab60dbceea804cfc2b0d22b64c27139e |
|
BLAKE2b-256 | ba4944519a1935f1779628787d01688d5e49ce800cfdec93be2aeea2a779c7f9 |
Hashes for dwave_greedy-0.1.0-cp36-cp36m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b7ff8b43271ac58bf6fa60fe4e8b1aaa890f0a53efad9669b34578660caaf883 |
|
MD5 | 7abf04958dddbc34c7c3042518d5758b |
|
BLAKE2b-256 | 3f4840439de6cbcaac7d808c028325e52ab640a59dc02f56e76bbe40c84fa33b |
Hashes for dwave_greedy-0.1.0-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e986c9d4c2fbd0f7e9b04b8dc8d3ee9d5834fdd76358e48993130b8ca23d4469 |
|
MD5 | 3c6b5a735a0d9f2fc1910167acefe5e7 |
|
BLAKE2b-256 | 9132df8bac94e140f26cfaddd7083121abb411f2b1e9febbaa7efa2a25cf7dee |
Hashes for dwave_greedy-0.1.0-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | db7e2e7d0aa8a3f1949b09b5b454b98e81302e9be00f5f98b9e388695662890a |
|
MD5 | 35a4519a54708ec662d9a8e9d6c9ab7e |
|
BLAKE2b-256 | cfa19b86249cceeae9cae1c49614377ada101124806dc5ac4cf7d766b687ca5f |
Hashes for dwave_greedy-0.1.0-cp35-cp35m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 62e2f1b7d98f0eb255a43ba7ec6c98a440b04be3705826de5538c5f45793297f |
|
MD5 | 2cd643b8989e791af00850bed1bb28ca |
|
BLAKE2b-256 | ef3b88a04be8182fecc478a795799e205cd01225f78f4e63ec1bf5033033885a |
Hashes for dwave_greedy-0.1.0-cp35-cp35m-manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be4b53b0b3ca69d40d3080540b45be3144f6606815a46bb42a7d7e9b977e3e06 |
|
MD5 | 8c24ee3282af0a67b51f6b3d654494a6 |
|
BLAKE2b-256 | d3e01a9a2a43010985ec4ca4bfe838eef98c9cd854bc79b83fa70f526b0ec447 |
Hashes for dwave_greedy-0.1.0-cp35-cp35m-manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a20bb0f2aa74fbedafca85cd4bc39088608b59793c9604c266e2811b04cce2f2 |
|
MD5 | fd72d95dff69a4adc3ae9869e0c868e6 |
|
BLAKE2b-256 | 973b1ebcafd50b72bb01e082092dd3679b8542d056b5b971b0b74166facc178d |
Hashes for dwave_greedy-0.1.0-cp35-cp35m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dda4cd4b1cedb8a244b5f11b0938e6ad1088f08d0407cf56c545a6b490266258 |
|
MD5 | 5206a4370a1615def19ebabe3e57b46c |
|
BLAKE2b-256 | f7da743476b28533b165cde664543a4e88e5daa7bcbf0ce0739367a62ad12715 |