Skip to main content
Join the official 2020 Python Developers SurveyStart the survey!

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

Project description

Linux/Mac build status Windows build status Code coverage Documentation status Last 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:

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


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.1.1
Filename, size File type Python version Upload date Hashes
Filename, size dwave_greedy-0.1.1-cp35-cp35m-macosx_10_9_x86_64.whl (91.9 kB) File type Wheel Python version cp35 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp35-cp35m-manylinux1_i686.whl (382.2 kB) File type Wheel Python version cp35 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp35-cp35m-manylinux1_x86_64.whl (402.4 kB) File type Wheel Python version cp35 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp35-cp35m-win32.whl (69.0 kB) File type Wheel Python version cp35 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp35-cp35m-win_amd64.whl (81.7 kB) File type Wheel Python version cp35 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp36-cp36m-macosx_10_9_x86_64.whl (93.8 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp36-cp36m-manylinux1_i686.whl (386.9 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp36-cp36m-manylinux1_x86_64.whl (405.7 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp36-cp36m-win32.whl (75.0 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp36-cp36m-win_amd64.whl (89.7 kB) File type Wheel Python version cp36 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp37-cp37m-macosx_10_9_x86_64.whl (93.9 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp37-cp37m-manylinux1_i686.whl (386.9 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp37-cp37m-manylinux1_x86_64.whl (405.4 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp37-cp37m-win32.whl (75.0 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp37-cp37m-win_amd64.whl (89.7 kB) File type Wheel Python version cp37 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp38-cp38-macosx_10_9_x86_64.whl (93.1 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp38-cp38-manylinux1_i686.whl (398.5 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp38-cp38-manylinux1_x86_64.whl (414.7 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp38-cp38-win32.whl (76.3 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave_greedy-0.1.1-cp38-cp38-win_amd64.whl (91.6 kB) File type Wheel Python version cp38 Upload date Hashes View
Filename, size dwave-greedy-0.1.1.tar.gz (13.4 kB) File type Source Python version None Upload date Hashes View

Supported by

Pingdom Pingdom Monitoring Google Google Object Storage and Download Analytics Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN DigiCert DigiCert EV certificate StatusPage StatusPage Status page