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.0rc2-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7281a3f6f430149684d4551900aa4211121016c0530da13c67ff773cc1216476 |
|
MD5 | 31723882b46086a18cc49debaaf01298 |
|
BLAKE2b-256 | f89438ab06a8dbe8c284cabb4a72a0d2c81a42c056dd3a420631b613b725bb66 |
Hashes for dwave_greedy-0.2.0rc2-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d3f66cf35f9492c454d7e62246ec0fb99bcd454f9f5ad0adcebc5844294c45a6 |
|
MD5 | 34128cc467a8af9af03bc16f7f0ec84d |
|
BLAKE2b-256 | 80cbd7e8e8f111ecc81fd2824029e29ec5a5358f292bf440cad4f3f6e414fe79 |
Hashes for dwave_greedy-0.2.0rc2-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2439330f52fbbcbdc142a9bb901241dfd7147e4e361a96032eed2a3fed71f963 |
|
MD5 | 74bc0cca7bb7053a8c9328ed8e459b15 |
|
BLAKE2b-256 | a0d13f48f613a4bb4ffe8cfaa4d9c8820a3fd42e9a7e80e63e5fdbd5f166a15c |
Hashes for dwave_greedy-0.2.0rc2-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d2a613c9db7a105be3290fa33980ef2c6ced98d647ea98f7b0338ccc3a97fc45 |
|
MD5 | 525c4c74848c5e383f3f0d35f85cd3d0 |
|
BLAKE2b-256 | b527d6b680e8280ee847ba4f60ac24184a25e75541bd2ce2d6efaa9fff4aaf08 |
Hashes for dwave_greedy-0.2.0rc2-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 00b8e5e43fa6b8785ee5048ddee33e1b4e70d6a5487d602e0454a929feb18c31 |
|
MD5 | 9543883c0d947df919fe1c8bd74cc185 |
|
BLAKE2b-256 | 0c6b62ff336ba2400bcd1f4c2129805d4417b067c2c101d24db418fd27e2617e |
Hashes for dwave_greedy-0.2.0rc2-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3c9e092cf9242517207f2faa54d178d4d7cb06a3a27533f2706dc2583ce05dd1 |
|
MD5 | bf2f72918e37a805124454263aa08610 |
|
BLAKE2b-256 | 8944089bfc1cf210f6cc823187089fd8cd1a16d572f26f96d419288c8096df7a |
Hashes for dwave_greedy-0.2.0rc2-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 786955715752f010efbce52daf2c8ee012d59286ff2e218588b2e5142cba1033 |
|
MD5 | be00ec47b2010fd8b696783e34a51f80 |
|
BLAKE2b-256 | 75406ea38410bfc475d13ea9350b97924674a1cf03304a731d5185de2f535d32 |
Hashes for dwave_greedy-0.2.0rc2-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a6b5f6bca5c318f272a9943c776dd5c99c5eabb5d9d41648f5a97297b0080bed |
|
MD5 | 4589a28906e6ceaa59639f717a7d5455 |
|
BLAKE2b-256 | a1e9c87e5e15c1ac0406f7f04cc28c11d8571e8bc62fc3758608f1587ef73e48 |
Hashes for dwave_greedy-0.2.0rc2-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f643c02eca464e396bd9d468a401abd2823b87bf1e4ca17438d7063d71ca85cd |
|
MD5 | 88d4de5b0981ae71e6611d4cf6d42866 |
|
BLAKE2b-256 | 07c1f27b19cd48ca9fa8ca602f7136ded1b968cccc1f60135a8ba5dc1cb6e626 |
Hashes for dwave_greedy-0.2.0rc2-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f24a1950c6883138078e4c1d6f82ac0a61fd941c23d0816debd2a4548bf39cc7 |
|
MD5 | aec85d350ac04bf5614a8e7fcfd77a4f |
|
BLAKE2b-256 | 6369c678a1b680321cfa2c90f80efdf9f3e8656d652008b6686beafde1bc28bb |
Hashes for dwave_greedy-0.2.0rc2-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbef17a86bb9ba897bb1f980761e4efa5cd974dc2b57864cd210b1635fa5ca2f |
|
MD5 | 11a544f23effb08a2fe185a4715475f1 |
|
BLAKE2b-256 | 27bc1aa11e8cbb8bd3df148b197f82f5f848ebaf41b591c54b3ca2e3ddab3c15 |
Hashes for dwave_greedy-0.2.0rc2-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e14a43f7a704db5f0555119a975124b53f8e05922109c18856d29e3028c9865e |
|
MD5 | 51ea11a5b3787e6156c0a815d20c3040 |
|
BLAKE2b-256 | 260d7b87df041d9d87db6881d1de253168bd4d557e1936734ffccdce8f11d712 |
Hashes for dwave_greedy-0.2.0rc2-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dac18ac1fd7dbeca7a314d4dc5342d76e11f619a93c415445d1804582844ca78 |
|
MD5 | 0132eee59b6c4c7ab24617cbee742c78 |
|
BLAKE2b-256 | f3df6994baf4ce8bc4aa2f93d24db53029965dd6b95cea110e8b23f6122c3e86 |
Hashes for dwave_greedy-0.2.0rc2-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4edd9cc003122b0abaf8d1234c278583f53f49e6bb2fa63042c374554cc937fe |
|
MD5 | 83a139f84a46e7d2d05ef1ddf63f0b48 |
|
BLAKE2b-256 | 04a0891e0568eaf734cfaf46f14e1a2a85009c5ca240758501819548bc0191e2 |
Hashes for dwave_greedy-0.2.0rc2-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7a8dcbd16f481e56cdc997e7df3a77fd149bfc39d2e5a4dcc71ba15f2c87a35d |
|
MD5 | 67f52e3488c2e2253ca9c59a73987325 |
|
BLAKE2b-256 | b45c2a949dd806c16c4151e3b675cd34248e18ff2825ffce10b8d7e2310ef05b |
Hashes for dwave_greedy-0.2.0rc2-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8849f2a712ff5f1f3776e91d99929036d5085d41e0aa5bb021cf41e58e7cb4de |
|
MD5 | 8407e1fdaedf7160111d593717ca99cb |
|
BLAKE2b-256 | 60c3fcde07b36e0fd8fbcb47c320ce894395358432b562afc031542a30ca6b17 |
Hashes for dwave_greedy-0.2.0rc2-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9f444ed89c3ceded690e95710c66447d32c0b2ad4f356aa4d16743d0898197b |
|
MD5 | 6c57c49860e20e427af7a8bb4fcfe7af |
|
BLAKE2b-256 | 9e48c67d308c6c21ff8612d80211d3de7561726579ed5bcb6930eb1df7157878 |
Hashes for dwave_greedy-0.2.0rc2-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6f7c63d75380b411b0a39f427cb6fe5345d9bf60a4ceb87dd9c354eca1fb8f8c |
|
MD5 | d80263c2f8882a9a59352b4fbaf047be |
|
BLAKE2b-256 | c8b4d01fcfa0ff0981114739a105bb1ce62b414d22f0f135767a1b01e0a470c9 |
Hashes for dwave_greedy-0.2.0rc2-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1028a64b20f73b7b4593e15130fed7dcecfbfd4726261e3bff55af92df49a37e |
|
MD5 | f6597ddddc863e9cb33b1f7a4ae9d238 |
|
BLAKE2b-256 | a9ebce5ab74326e7bf67d9d3240495875e8f91aaab1ae37e2c12d93140c7fd8d |
Hashes for dwave_greedy-0.2.0rc2-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e2f8ec9abdbe2e969e9c353b8c210b58701caa0d62de9534a381a628bfea5452 |
|
MD5 | 9f3dadc4e2fa4bbe567e64bf2cfe1c9d |
|
BLAKE2b-256 | 6a01fa03ade849dd0be7d4cc6ed9835a87dd28eb4cd9084ca4dd6eeea9943c04 |