Skip to main content

Ocean-compatible collection of greedy/brute-force solvers/samplers

Project description

Linux/MacOS/Windows build status Code coverage Documentation status Latest version on PyPI PyPI - Python Version

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for dwave-greedy, version 0.2.1
Filename, size File type Python version Upload date Hashes
Filename, size dwave_greedy-0.2.1-cp36-cp36m-macosx_10_9_x86_64.whl (214.6 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (653.9 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp36-cp36m-manylinux_2_5_x86_64.manylinux1_x86_64.whl (527.6 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp36-cp36m-win32.whl (197.5 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp36-cp36m-win_amd64.whl (212.4 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp37-cp37m-macosx_10_9_x86_64.whl (214.7 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (654.1 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.whl (527.4 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp37-cp37m-win32.whl (197.5 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp37-cp37m-win_amd64.whl (212.5 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp38-cp38-macosx_10_9_x86_64.whl (213.9 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (680.7 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.whl (537.4 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp38-cp38-win32.whl (198.9 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp38-cp38-win_amd64.whl (214.4 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp39-cp39-macosx_10_9_x86_64.whl (216.1 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (681.3 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl (527.3 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp39-cp39-win32.whl (198.6 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size dwave_greedy-0.2.1-cp39-cp39-win_amd64.whl (213.7 kB) File type Wheel Python version cp39 Upload date Hashes View
Filename, size dwave-greedy-0.2.1.tar.gz (130.9 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page