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.1-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6045b7c17577d8f6a669863b94bac9a4d10ca281fd8db9b6b2a9b36e2cc2529d |
|
MD5 | 7af2b7e2bcee8e699efd9234a7c8abd4 |
|
BLAKE2b-256 | 2703fb2af46fb5d3465e741ab95a23d1ca5d0b0dfe9ea6ca552bf964681042da |
Hashes for dwave_greedy-0.2.1-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 23be0552db9092419fed416db7d00b073061eebaa17181d206584760a36b3ed2 |
|
MD5 | 68781d0d8fbb81aad81aefe448673e4a |
|
BLAKE2b-256 | 3ddfbcd106b6a7d05b0b1cfd7d76ae68dd304d76c59085378ee1dd361847ab0c |
Hashes for dwave_greedy-0.2.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e692045c8c1d29f103cdb16c132b6fc7ef2e3e55d653d9450df1a742c48420d |
|
MD5 | 3079305c199d6a8bffd1abffd8c4e047 |
|
BLAKE2b-256 | aadb9b92bd5101aff65395f40e7fc912d1cec12b4792cb3e5441d1615d879888 |
Hashes for dwave_greedy-0.2.1-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aeaeb6ba24b82f0bb9abd357ad74e87e5fd7f5eb1896c066c63fa28b89287c3d |
|
MD5 | 77c880915129ab8929d5cff515be8e33 |
|
BLAKE2b-256 | 449becde1bcaf1993fda19e7d87f0cefa1fa7041a689b69204caa0c0f078ecfb |
Hashes for dwave_greedy-0.2.1-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1c6e0f48ec468a6a744504abad3e86dc8d0a1de5ff22cf8a47c64364ffcac622 |
|
MD5 | 2b5f5d42039737c14b51ead72c564f0d |
|
BLAKE2b-256 | 83d832f2f2bedccf4eefa56ec176f8d1879f1f3ed0e139ba6eaa76d8d953b9e6 |
Hashes for dwave_greedy-0.2.1-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 63615464d73a8bb840e59e1084d7fd8b31c4a7d51ce7c1098f34261b2114db18 |
|
MD5 | 735dc2730b950a97052818b656559699 |
|
BLAKE2b-256 | 46655f06fcb18a243d0a7b369cd23a53c784f13e1893842cb67d6ffc4ce8c382 |
Hashes for dwave_greedy-0.2.1-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d6025c65c829c26fda8972a76e9955ab449373641bc0afc928be51f0f26d669a |
|
MD5 | 9b02049f4594f0eff921af8070382516 |
|
BLAKE2b-256 | 4f2aa60dcfe4dc91388cd5421b96298c0e316901bafb40393bd13bc288903088 |
Hashes for dwave_greedy-0.2.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a885a5919902f8643becb7aa536a96b6d07a8644f1e66bc3954cb8a3b4f42c0d |
|
MD5 | 64fa2b3056b6a86d6e923a80f32ab0a0 |
|
BLAKE2b-256 | 9ec645893c59834dc8d979a3d7f072e48b0a69bc4fe80d3c183789a69fc593ba |
Hashes for dwave_greedy-0.2.1-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5b5fce0ec9102a999addbdab6c2539730b3f8a92f03c941b527a10f350a9be8c |
|
MD5 | e727d90d1632878567456903f3cad9e3 |
|
BLAKE2b-256 | 6f18f8d65b2d590caf5f34bd40565c9487823c34a34ce3a7be5e10fea7a639df |
Hashes for dwave_greedy-0.2.1-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 99737431109e0771ec54750f44222e8798d3314088a6f1846f7cf931db84681b |
|
MD5 | 91782bd959ea8bfe513292aac15f9426 |
|
BLAKE2b-256 | b1bea4bf2f512aa5c834027bcabd5f7e4f2e011b68e91f124173375e483066f9 |
Hashes for dwave_greedy-0.2.1-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 47a25df12f6c0a1b3c477230001dc60af34dac9af5171c7543f0e1702b202b15 |
|
MD5 | 72f4488149777ac8af5a900c1eafd80c |
|
BLAKE2b-256 | e9027886ef74790f26594d97dc2bd2b68d9e81d1ce1995bacd36893bd7d008e0 |
Hashes for dwave_greedy-0.2.1-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aa7d984d7a5839fde481ef590c999568752cdb3586e6a13ec11121bb21264a90 |
|
MD5 | 17c68d30d458ba77407fcc786e8dbce7 |
|
BLAKE2b-256 | e3954f3a1e4c5e1c824ecbd1970ad73f6d61952f44404bba66abb527016f2154 |
Hashes for dwave_greedy-0.2.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 91585fefb2faa95d7da2ea4e85665a066d18b41fc14aced658c3ac0ae2a8873d |
|
MD5 | 9981657d4288461837a416766e47ccfe |
|
BLAKE2b-256 | 2298d0a0c637ea2cbcd3cec48450b1f36df1ae524b495a447337ae7264350938 |
Hashes for dwave_greedy-0.2.1-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 45679cf6138fbfd48e3410e016421ddcf0feec3f4152228b5e39c7af39775e9e |
|
MD5 | 87bf55ff1434cc19f28f6f47823cdc6f |
|
BLAKE2b-256 | ea99ad4688ea12a5603417b6d1a65c6a48590328d69daf7daf27a7a8456d19c3 |
Hashes for dwave_greedy-0.2.1-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae8714fe0357e838e1567d6e59bad93df33d7d6b0f607027e21120ba657a52b6 |
|
MD5 | be5233ab1117b1c24b1a738c13730686 |
|
BLAKE2b-256 | f3b52fe76543675aff09ddc120424160f21eb2fd0bf4364b6c800b75a012802c |
Hashes for dwave_greedy-0.2.1-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f873a672fb3deeb97e3c0a3311548888056759c3ad05e4c6d6a3cb1104334e8d |
|
MD5 | d4210303739dbacfe1da10806f97c5ef |
|
BLAKE2b-256 | 4fade180280a5340595e06c24079f61a0056cd73b740a9e5ece5a1a8e4d4f129 |
Hashes for dwave_greedy-0.2.1-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e6cba4a065d01f27f5e5b7b590a63191690f9521f3c4902c6c94590a023e246 |
|
MD5 | c79bd186df0dce502349dd1925fa8dde |
|
BLAKE2b-256 | 6a5fac16897118850f6af679f67c9015d1b16f611db979a694b41096e13897c3 |
Hashes for dwave_greedy-0.2.1-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9c0788f8e45bd9f06cebc945d280d158ce48bf44dcecbfa7f265e463506a12af |
|
MD5 | fb60f0360e4cd4aca30184dcd6a54f31 |
|
BLAKE2b-256 | df1afd6a8bfc29f15ae375afd7b0d5ada53c79af3b44cf7d302e487e02263fb9 |
Hashes for dwave_greedy-0.2.1-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49db1df02b4ea621f4c8751a2d6610c57512ad7200794db17d2264dc00dc9611 |
|
MD5 | 0177754bdabe0bf954e3d99d3df27ba1 |
|
BLAKE2b-256 | b7344acc78020bfe8ea5b947180bcc98da02ce2ed7b0c52e514fb43a6e02f9ae |
Hashes for dwave_greedy-0.2.1-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f14117387e261a072b77ce17835cabbdeb8780ab159350bab5e245206df1a3d0 |
|
MD5 | 60638a396f252504391ee1b111ce7ccb |
|
BLAKE2b-256 | 8c1fee04eb16f5c460684937a28e774f4e2606b8c31ca0f92c07796b309ba5cf |