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 Distributions
Built Distributions
Hashes for dwave_greedy-0.1.0rc1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9d70898b40c112883edb6409b0b6a4d5235a28eabb57b8eaff22f2359ad65ccd |
|
MD5 | 671a66b2c37103d01d5388850dcdc0a4 |
|
BLAKE2b-256 | 6b6df8b8a141a7fb308b20c512ea7ef5549425137c8d0298cbadca87325d700c |
Hashes for dwave_greedy-0.1.0rc1-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 76bdbb209eaf5c46212c12cde5dbba27b34c0226c5fafb97dd16ab8e6e09df47 |
|
MD5 | 3d0c5bbaf4cf655bd2677d749fb72c35 |
|
BLAKE2b-256 | 3b370894d25c55d546d24463a5896c970fcc303cf752375e9f90cd0b30f18d3f |
Hashes for dwave_greedy-0.1.0rc1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 54077891eb966470afabea8e3a74b22348ac260d163d301b53feecb9ee38921b |
|
MD5 | b00d0347e0dde7c901bbbb0146bb62a3 |
|
BLAKE2b-256 | a5f901d5e6bcdeeac5f7294a77ad3ba658c4d821f953c3eae702ad7ae3789049 |
Hashes for dwave_greedy-0.1.0rc1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 90ec067eb0d64974ff5ae24dfd1c8f8312194c0a9b389a384a318e4cd41c0915 |
|
MD5 | 2f67fbae6689008698ff1dad171d4ac5 |
|
BLAKE2b-256 | cb1a467c8056d1b6d9e4b00782e8518f43f2822d19a3fb99ae50aed0ab377c62 |
Hashes for dwave_greedy-0.1.0rc1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | adec3f9a66770dd980274899ec20b2376fd6fddcc2c6ab5ec0636a94a113bdf3 |
|
MD5 | c6786f103ac1716c71cec542932f2161 |
|
BLAKE2b-256 | a6cc06e76077c5e3d5f746f7de4b9f1d330bc08b872d2c9ef6a3bf1b607723cc |
Hashes for dwave_greedy-0.1.0rc1-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bc5a5d2b17319b66a255d1f8d4cc8171578b6d711586c62977cfeafd4590bd0b |
|
MD5 | 9d530090ee1321ddc37d68ad3a3a061f |
|
BLAKE2b-256 | 6e0a098231cd4c7c3b546724abca014cca324e80a3719bd56851fef2ea79e69f |
Hashes for dwave_greedy-0.1.0rc1-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 96aa1b13e7e7926060f7f5de5dfd03aae623cdbd57463f19e1708a8fc6e1b324 |
|
MD5 | d0d678391b4120330bcfb77fe9c8fe6f |
|
BLAKE2b-256 | 39c013bc1d0a1cbaf50855cb4a2dbae7588c9e9a775cab056cb179fc7cb86afe |
Hashes for dwave_greedy-0.1.0rc1-cp35-cp35m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 368c8f21ce1bd05f7dccb48f67ce5e91cac5abf8db8e9b163585d05cc9320d25 |
|
MD5 | 6dcacc5eecd958b65f55771cbf5877cd |
|
BLAKE2b-256 | 91018a5a0c0c5caa2af2ec2011e8d2ad98127faf4ea99407e04ecafa8654786f |