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.0rc3-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 212b335371a19c62b4758c049c79255c8baa5556bed1d115843fefbd58559ef8 |
|
MD5 | 6b6a437546296a6d16350615eece68da |
|
BLAKE2b-256 | 0de255115e42b1538ffdd3ae60e7ff60c6b46146c16002836ec58229dcd3d65b |
Hashes for dwave_greedy-0.2.0rc3-cp39-cp39-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f9ce60b3f01dc4144bbe22ca31500b99a63eda3bd0e451ad39991e8a1ee16ed0 |
|
MD5 | f53379772016e0c2fa4592288c0adb18 |
|
BLAKE2b-256 | 46ac04982e11e0cd973f7813beb7c8dd0d1acb7447e03ea05f27d167c59cb257 |
Hashes for dwave_greedy-0.2.0rc3-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a5efd54bf5d9979503f2dadba35f4f45d8041770bf7f1b66dd88e133d42ece6f |
|
MD5 | 878124a45a48df8218ab72162332eda2 |
|
BLAKE2b-256 | f42ec1f2001df55cb825c96edf2af2b02d189859f73ba333c284b33ca4ca851d |
Hashes for dwave_greedy-0.2.0rc3-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b710efc96df8c9945c4605b057123f7938d2b629c77196b65bffdecb4cdd2d51 |
|
MD5 | 0c1d30a92e3a0ad81a8bbfbde2fd0821 |
|
BLAKE2b-256 | e0f735c7e31769793237c31b5f92ad3e09725b3e0c92d82d0744bea76dbe8f65 |
Hashes for dwave_greedy-0.2.0rc3-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b144093f0ec236fdd2d01a7717365839edebfea89a638dd0fbd4ae2a31e19ac |
|
MD5 | 74206caa18f97690ab32e39a4d6ca3e4 |
|
BLAKE2b-256 | 116087280a4ab4771212f453ada7fc945cd82d3b1254c0500512939eef1b07fb |
Hashes for dwave_greedy-0.2.0rc3-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d6fd4c09cdc16d1f175ffcd959e8b1cbd0e88df02cbd9bbe9e9b4e5936af83fc |
|
MD5 | 4b1216918a67b9aeb7bd34d677d48107 |
|
BLAKE2b-256 | 12264c29c89dfb9e6fa4a362a6a43c7f9896bc4d8d612a31aed2f45fe3f498be |
Hashes for dwave_greedy-0.2.0rc3-cp38-cp38-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 28664dda0cb02745c54b5fece9f9b9c7cfef599f0dcbd99989f66dabe49598f1 |
|
MD5 | be8839e3539902602768c8cc2af4f216 |
|
BLAKE2b-256 | 177c203c20d77c0a40fec464868783b44f194068a173e7130df7f94bde7ed7ef |
Hashes for dwave_greedy-0.2.0rc3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 978c967b1b29f9ba0f64b82088aa339dfe985115e749cac1b3116f73eaf46fe5 |
|
MD5 | 732cefaef48bf28d4191caa334e37dca |
|
BLAKE2b-256 | 4e0fd0660f49e4502fd88a5287ae82f70991d638317f5cec76b3ffdc86b1ba30 |
Hashes for dwave_greedy-0.2.0rc3-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9132faf6fa2a094ec3f0cc628cf193271aeba47a8a388bc209f50036920fd8bc |
|
MD5 | 1f5036e8d6403bf9c860cc8d4ebb5e9d |
|
BLAKE2b-256 | 4931f3e89c3dd0270d654cf88f3cfdc78905704dae6c8e238c7e76512ece0702 |
Hashes for dwave_greedy-0.2.0rc3-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5c3a58d210b3ffd231ac8070a7c5fc97c7c95f7860326fa210fad4fa10b44caf |
|
MD5 | 1dd5a0e3bf162d8fbb33668a0e5e24b6 |
|
BLAKE2b-256 | 37d79328d838bf167b6e3b5f4a9d623c05af47432206199237b5c2464a9edafd |
Hashes for dwave_greedy-0.2.0rc3-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 40d7bad009f0c60caf97ed0bc4b10554fcbf924cd7c2d92f5a9fca531a31376b |
|
MD5 | 0ea13d2ae4fb0daf5150cfd616aed9d6 |
|
BLAKE2b-256 | 9db67932b01a767a6a31b3ac166fdd3ed227d9000ca1971f40e793aa1fc11291 |
Hashes for dwave_greedy-0.2.0rc3-cp37-cp37m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c1680d9311021cf1c5e193d3870294a666234e25a6498c4eed4755feb75ebbb7 |
|
MD5 | 95cd72d1697c9e0d2d22bbd4a10078fb |
|
BLAKE2b-256 | ce6c6971af0b70d39d178c5a752a73c40807c185f695852c0363eb3bd575820c |
Hashes for dwave_greedy-0.2.0rc3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9fd5ff13e0781e66bfe1e948e7a2339b346c7cef3c39343f5b6bbb6f087de727 |
|
MD5 | 01893eb1162f074eb537edb5d855304d |
|
BLAKE2b-256 | 54b67daea447d75905756acdb2664415648dc3975b20d7e8c5488a25fda2349c |
Hashes for dwave_greedy-0.2.0rc3-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d4230fff07f0ed9403e1c4a8f6c974da87ef376a3301826149d938a6e1f9f220 |
|
MD5 | bdc30936b30b49a39639725594eab956 |
|
BLAKE2b-256 | a39b4488e52f80fdd3138462fd0ece2cc6a3cb1013a8c2fcf0442fa69a9d2e73 |
Hashes for dwave_greedy-0.2.0rc3-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8039305a11c14155f89622d03a3c6407d31ca653fc702bd51abc008dfbb7367e |
|
MD5 | 089b62855d7481f5451a9c06e049a998 |
|
BLAKE2b-256 | d1d9e50f13a33bd24dd8a10ca2c9a967369d03e3fa494412fb9375ad941e47f5 |
Hashes for dwave_greedy-0.2.0rc3-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e90ad7a7845a2d2369f925578414950a92f3e189f4dfa68a335d6cf6c37ce51c |
|
MD5 | c4a569e5a4cac9f40c13616826631fed |
|
BLAKE2b-256 | 55536c6466497243d64ce608b9dce8127498fd9fa68e0fcec528364a8834c1b6 |
Hashes for dwave_greedy-0.2.0rc3-cp36-cp36m-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aec5f7d72d6b1b51df74297015cddeccfa6f6c4f6a2436c46104032fc4d72d7c |
|
MD5 | abcf2052a316206ffb9de44879c44f40 |
|
BLAKE2b-256 | c2a550682cdabb044efe7ae86070bc2afe8b12fb6fe874ddd7d8e0e0afad88fa |
Hashes for dwave_greedy-0.2.0rc3-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f958023b3f08679688ec75171c5fc178021e598fb8bc1365884206245a0c1d55 |
|
MD5 | 63ecb534c1b45a8c52b5f3f35d246852 |
|
BLAKE2b-256 | 0240140cc22ac60a6b32cf2fdb0cfd2f9bb60141d0356062a7d07dd98074bde1 |
Hashes for dwave_greedy-0.2.0rc3-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9de17545d980284291796c3c26d94ae59ed5d62871e5e78a63688305c679d28a |
|
MD5 | 5c2e4eb7f78010cd0a2fd39cb8c1ec2e |
|
BLAKE2b-256 | ee0c2499ec204aaad9e382599ee648287f274d26f48ee8f80d3f9fe95c2901ea |
Hashes for dwave_greedy-0.2.0rc3-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b53da5563c3874d9e9f55c779fa15c2a37ec8c99498e8097226a56c58adc81e4 |
|
MD5 | 5dc49047de46d30493af73bd2cae2157 |
|
BLAKE2b-256 | 4c86c7879da31af5408d3a0cd4105bedf9d2ed809a5c46db3386cf4f7e4dba7e |