dwavesystems / dwave-tabu Goto Github PK

View Code? Open in Web Editor NEW

20.0 20.0 19.0 246 KB

Tabu solver for QUBO/Ising problems.

Home Page: https://docs.ocean.dwavesys.com/projects/tabu/en/latest

License: Apache License 2.0

Python 41.63% C++ 51.39% C 1.21% Makefile 0.49% Cython 5.28%

dwave-tabu's People

Contributors

Stargazers

Watchers

Forkers

randomir joelpasvolsky stjordanis sajidsaleem wbernoudy shyamalschandra arcondello cnxtech hhtong scorpjd global-localhost global19 global19-atlassian-net zeta1999 fermiq rog77 retrohun ruiztechservices

dwave-tabu's Issues

Adjust `initial_states` to `num_reads`

As a continuation of #38, support initial_states semantics (along with initial_states_mapper) as described in dwavesystems/dwave-neal#56.

Tabu sampler is not compatible with AdjArrayBQM

Hi Team,

The new BQM generators, such as AdjArrayBQM, are really cool!
But, Tabu sampler can't handle the new objects.
Are you planing to fix it?

Best,

Drop dwave-hybrid dependency for testing

Once we extract testing utils to a "common" package, we should use it instead:

dwave-tabu/tests/test_sampler.py

Line 23 in 8dfb88f

from hybrid.testing import RunTimeAssertionMixin

Feature: Accept cyBQM

The current version doesn't work with cyBQM, specifically AdjArrayBQM

Need to make RTD public

Clicking on the RTD link:

Asks clicker to log in to RTDs. This is because it has not been set to public:

NumPy update incompatible with sphinx

Change to NumPy version in 6da72b1 breaks the doc build.

Default value of 1 for `scale_factor` means bad results bqms with non-integer biases

Though the parameter scale_factor is documented, the default behavior means casting all biases to int (not just rounding, but truncating the fractional part) which can be pathological for anything but very low precision problems.

A quick example (note I don't fully understand this as I would think it should produce random samples):

In [21]: tabu_sampler.sample_ising({0: 0.4}, {}, num_reads=100).record.energy.mean()                                                                                                     
Out[21]: 0.3999999999999999

scale_factor should probably be set internally in the sample method, determined by the bqm range of biases. I can't think of any use-case that requires exposing it (though please mention it if there is one!)

Add target energy based termination criterion

Initial states (raw data) converted in place to binary vartype

>>> import dimod, tabu
>>> 
>>> bqm = dimod.BQM.from_ising({}, {'ab': 1})
>>> 
>>> initial = dimod.SampleSet.from_samples_bqm([{'a': 1, 'b': -1}, {'a': -1, 'b': 1}], bqm)
>>> initial
SampleSet(rec.array([([ 1, -1], -1., 1), ([-1,  1], -1., 1)],
          dtype=[('sample', 'i1', (2,)), ('energy', '<f8'), ('num_occurrences', '<i8')]), ['a', 'b'], {}, 'SPIN')
>>> 
>>> ss = tabu.TabuSampler().sample(bqm, initial_states=initial)
>>> 
>>> initial
SampleSet(rec.array([([1, 0], -1., 1), ([0, 1], -1., 1)],
          dtype=[('sample', 'i1', (2,)), ('energy', '<f8'), ('num_occurrences', '<i8')]), ['a', 'b'], {}, 'SPIN')

Expected behavior: input initial states are not modified. Tabu solver works on a copy of input data.

Doctests failing in Sphinx 2.0

See https://circleci.com/gh/dwavesystems/dwave-tabu/1129.

Doctests do work for Sphinx < 2.0.

Add option to seed sample call for reproducible results

Error Importing Tabu

Hello, I have been trying to import dwave tabu, but I have been experiencing some issues. When importing the package in python3, I get this result:

>>>import tabu
Traceback (most recent call last):
  File "/home/chip/.local/lib/python3.5/site-packages/tabu/tabu_search.py", line 14, in swig_import_helper
    return importlib.import_module(mname)
  File "/usr/lib/python3.5/importlib/__init__.py", line 126, in import_module
    return _bootstrap._gcd_import(name[level:], package, level)
  File "<frozen importlib._bootstrap>", line 986, in _gcd_import
  File "<frozen importlib._bootstrap>", line 969, in _find_and_load
  File "<frozen importlib._bootstrap>", line 958, in _find_and_load_unlocked
  File "<frozen importlib._bootstrap>", line 666, in _load_unlocked
  File "<frozen importlib._bootstrap>", line 577, in module_from_spec
  File "<frozen importlib._bootstrap_external>", line 914, in create_module
  File "<frozen importlib._bootstrap>", line 222, in _call_with_frames_removed
ImportError: /home/chip/.local/lib/python3.5/site-packages/tabu/_tabu_search.so: wrong ELF class: ELFCLASS64

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/chip/.local/lib/python3.5/site-packages/tabu/__init__.py", line 17, in <module>
    from tabu.tabu_search import TabuSearch
  File "/home/chip/.local/lib/python3.5/site-packages/tabu/tabu_search.py", line 17, in <module>
    _tabu_search = swig_import_helper()
  File "/home/chip/.local/lib/python3.5/site-packages/tabu/tabu_search.py", line 16, in swig_import_helper
    return importlib.import_module('_tabu_search')
  File "/usr/lib/python3.5/importlib/__init__.py", line 126, in import_module
    return _bootstrap._gcd_import(name[level:], package, level)
ImportError: No module named '_tabu_search'

I suspect that the error has something to do with swig, but I am unsure what to do to resolve it. Any help would be greatly appreciated.
Thanks

Blocker to https://github.com/dwavesystems/docs/issues/57 ?

Before I fix dwavesystems/docs#57, with links to RTD, I think the RTD for dwave-tabu should be dwave-tabu under https://docs.ocean.dwavesys.com/projects, not d-wave-systems-dwave-tabu as it is currently:

If there's some good reason for this inconsistent format, let me know. Thanks!

Need to add copyright headers

@randomir just a reminder

Missing class, methods documentation

https://docs.ocean.dwavesys.com/projects/tabu/en/latest/reference/sampler.html is empty
Used to show class & methods. Did you break the path?

Simplify licensing by removing 3rd party windows include file

Can we remove tabu/src/extern/stdint.h, now that we migrated from swig to cython?

Blocker for dwavesystems/dwave-ocean-sdk#144.

Update build from source section in readme/docs

We still talk about swig, although we switched to cython.

Fix cpp-tests

See #61 (comment)

fails to give global minima

I am trying to solve a qubo problem using dwave tabu. I am using the python interface with the following commands.
from tabu import TabuSampler response = TabuSampler().sample_qubo(Q) print(response.first.energy)
every time I run, I am getting different values of energy and solution. I am getting energy close to the global minimum, but not global minima.
whereas qbsolv command gives global minima every time. what is the problem or am I missing something?

TabuSampler fails for single variable BQMs

To reproduce:

>>> import tabu, dimod
>>> tabu.TabuSampler().sample(dimod.BinaryQuadraticModel({'a': 1}, {}, 0, dimod.SPIN))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/home/radomir/work/dwave-tabu/tabu/sampler.py", line 113, in sample
    raise ValueError("'tenure' should be an integer in range [1, num_vars - 1]")
ValueError: 'tenure' should be an integer in range [1, num_vars - 1]

Isolate RNG per instance and thread

Right now we use cstdlib's rand which is not thread-safe.

We should switch to something like std::default_random_engine generator.

Related to #30.

Fix pip install from sdist on windows

Install from sdist via pip works on Linux, but fails on Windows.

GIL locked during Tabu Search

C++ code is keeping GIL locked in TabuSearch, although TabuSearch is working on a copy of user data (created in TabuSampler.sample()).

Manifested as dwavesystems/dwave-hybrid#122.

Install via pip fails on Debian / Ubuntu

Hello team, 

When I tried to install dwave-tabu via pip, following error occurred while building wheels. (I was instead able to install dwave-tabu by downloading this package and executing setup.py.) 

Environment:
Debian 10, python3.9.4
Ubuntu 20.04LTS, python3.8.? 

Error message:

aaa@bf6f91819798:~$ pip install --user dwave-tabu
Collecting dwave-tabu
 Using cached dwave-tabu-0.3.1.tar.gz (13 kB)
Requirement already satisfied: numpy>=1.16 in ./.local/lib/python3.8/site-packages (from dwave-tabu) (1.20.2)
Requirement already satisfied: dimod>=0.9.0 in ./.local/lib/python3.8/site-packages (from dwave-tabu) (0.9.14)
Building wheels for collected packages: dwave-tabu
 Building wheel for dwave-tabu (setup.py) ... error
 ERROR: Command errored out with exit status 1:
  command: /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/setup.py'"'"'; __file__='"'"'/tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' bdist_wheel -d /tmp/pip-wheel-jd5wrh_u
    cwd: /tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/
 Complete output (10 lines):
 running bdist_wheel
 running build
 running build_py
 running build_ext
 building 'tabu._tabu_search' extension
 swigging tabu/tabu_search.i to tabu/tabu_search_wrap.cpp
 swig -python -c++ -threads -o tabu/tabu_search_wrap.cpp tabu/tabu_search.i
 tabu/tabu_search.i:64: Error: Unable to find 'src/tabu_search.h'
 tabu/tabu_search.i:65: Error: Unable to find 'src/common.h'
 error: command 'swig' failed with exit status 1
 ----------------------------------------
 ERROR: Failed building wheel for dwave-tabu
 Running setup.py clean for dwave-tabu
Failed to build dwave-tabu
Installing collected packages: dwave-tabu
  Running setup.py install for dwave-tabu ... error
  ERROR: Command errored out with exit status 1:
   command: /usr/bin/python3 -u -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'/tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/setup.py'"'"'; __file__='"'"'/tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-yv3utw4q/install-record.txt --single-version-externally-managed --user --prefix= --compile --install-headers /home/aaa/.local/include/python3.8/dwa
ve-tabu
     cwd: /tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/
  Complete output (10 lines):
  running install
  running build
  running build_py
  running build_ext
  building 'tabu._tabu_search' extension
  swigging tabu/tabu_search.i to tabu/tabu_search_wrap.cpp
  swig -python -c++ -threads -o tabu/tabu_search_wrap.cpp tabu/tabu_search.i
  tabu/tabu_search.i:64: Error: Unable to find 'src/tabu_search.h'
  tabu/tabu_search.i:65: Error: Unable to find 'src/common.h'
  error: command 'swig' failed with exit status 1
  ----------------------------------------
ERROR: Command errored out with exit status 1: /usr/bin/python3 -u -c 'import io, os, sys, setuptools,tokenize; sys.argv[0] = '"'"'/tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/setup.py'"'"'; __file__='"'"'/tmp/pip-install-b4uflvbe/dwave-tabu_c0236da9290741ef96501a7aa8984ebc/setup.py'"'"';f = getattr(tokenize, '"'"'open'"'"', open)(__file__) if os.path.exists(__file__) else io.StringIO('"'"'from setuptools import setup; setup()'"'"');code = f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, __file__, '"'"'exec'"'"'))' install --record /tmp/pip-record-yv3utw4q/install-record.txt --single-version-externally-managed --user --prefix= --compile --install-headers /home/aaa/.local/include/python3.8/dwave-tabu Check the logs for full command output.

Add restarts count based termination criterion

Make the sampling interface more consistent with SA

Rename: init_solution to initial_states.

Still support initi_solution, but deprecate its use. Warn user.

Install from source with `pip install .` (via `bdist_wheel`) fails

pip install . will run setup.py bdist_wheel in a temporary directory to build a wheel, which it then installs in the active environment.

The problem is that during wheel building, python extensions are packaged before the compiled extension:

$ pip install . -v
...
Building wheels for collected packages: dwave-tabu
  Created temporary directory: /tmp/pip-wheel-ix5vtkcy
  Running setup.py bdist_wheel for dwave-tabu ...   Destination directory: /tmp/pip-wheel-ix5vtkcy
  Running command /tmp/dwave-tabu/env/bin/python3 -u -c "import setuptools, tokenize;__file__='/tmp/pip-req-build-8pwxbv_n/setup.py';f=getattr(tokenize, 'open', open)(__file__);code=f.read().replace('\r\n', '\n');f.close();exec(compile(code, __file__, 'exec'))" bdist_wheel -d /tmp/pip-wheel-ix5vtkcy --python-tag cp35
  running bdist_wheel
  running build
  running build_py
  file tabu/tabu_search.py (for module tabu.tabu_search) not found      <=== PROBLEM
  creating build
  creating build/lib.linux-x86_64-3.5
  creating build/lib.linux-x86_64-3.5/tabu
  copying tabu/__init__.py -> build/lib.linux-x86_64-3.5/tabu
  copying tabu/package_info.py -> build/lib.linux-x86_64-3.5/tabu
  copying tabu/sampler.py -> build/lib.linux-x86_64-3.5/tabu
  file tabu/tabu_search.py (for module tabu.tabu_search) not found
  running build_ext
  building 'tabu._tabu_search' extension
  swigging tabu/tabu_search.i to tabu/tabu_search_wrap.cpp
  swig -python -c++ -threads -o tabu/tabu_search_wrap.cpp tabu/tabu_search.i
  creating build/temp.linux-x86_64-3.5
  creating build/temp.linux-x86_64-3.5/tabu
  creating build/temp.linux-x86_64-3.5/tabu/src
  x86_64-linux-gnu-gcc -pthread -DNDEBUG -g -fwrapv -O2 -Wall -Wstrict-prototypes -g -fstack-protector-strong -Wformat -Werror=format-security -Wdate-time -D_FORTIFY_SOURCE=2 -fPIC -Itabu/src -I/usr/include/python3.5m -I/tmp/dwave-tabu/env/include/python3.5m -c tabu/tabu_search_wrap.cpp -o build/temp.linux-x86_64-3.5/tabu/tabu_search_wrap.o
  ...

and tabu/tabu_search.py module is created by SWIG during extension compilation.

Overriding the build command seems to be a known workaround.

This bug causes failing doctests, on #44.

Up the `dimod` version used for testing to a `dwave-system`-compatible range

Alternatively, resolve #75.

Namely, currently we install the latest dwave-hybrid for tests, which installs the latest dwave-system, which depends on dimod>=0.10 -- a conflicting requirement with dimod==0.9.x that we use in dev reqs. Because of that, tests fail. But these failures are silenced due to another bug in orb-ocean collection of CI tools.

Upgrade to work with latest dimod (0.7.7)

In dimod>=0.7.7, SampleSet replaced Response as a more general sample container.