dwavesystems / dwave-preprocessing Goto Github PK

View Code? Open in Web Editor NEW

4.0 4.0 15.0 450 KB

Common preprocessing tools that can aid in solving binary quadratic models (BQM).

License: Apache License 2.0

Python 26.42% C++ 67.96% Makefile 0.51% Cython 5.12%

dwave-preprocessing's People

Contributors

Stargazers

Watchers

Forkers

hhtong joelpasvolsky amahmudwave pierrelouisp arcondello stjordanis randomir nakano57 jackraymond rog77 retrohun chiefwf2772 alexzucca90 elham-azd mdcoury

dwave-preprocessing's Issues

Add per_variable_quadratic_range kwarg or similar to ScaleComposite

It would be useful to also be able to scale the problem based on the per-variable quadratic range. See dwavesystems/dwave-system#404.

Import fails

Hi, I built and imported dwave-preprocessing but get the following error:

import: 'dwave.preprocessing'
Traceback (most recent call last):
  File "/home/conda/feedstock_root/build_artifacts/dwave-preprocessing_1673615490577/test_tmp/run_test.py", line 2, in <module>
    import dwave.preprocessing
  File "/home/conda/feedstock_root/build_artifacts/dwave-preprocessing_1673615490577/_test_env_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placeh/lib/python3.10/site-packages/dwave/preprocessing/__init__.py", line 23, in <module>
    from dwave.preprocessing.presolve import *
  File "/home/conda/feedstock_root/build_artifacts/dwave-preprocessing_1673615490577/_test_env_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placeh/lib/python3.10/site-packages/dwave/preprocessing/presolve/__init__.py", line 15, in <module>
    from dwave.preprocessing.presolve.pypresolve import *
  File "/home/conda/feedstock_root/build_artifacts/dwave-preprocessing_1673615490577/_test_env_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placeh/lib/python3.10/site-packages/dwave/preprocessing/presolve/pypresolve.py", line 91, in <module>
    from dwave.preprocessing.presolve.cypresolve import cyPresolver
ImportError: /home/conda/feedstock_root/build_artifacts/dwave-preprocessing_1673615490577/_test_env_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placehold_placeh/lib/python3.10/site-packages/dwave/preprocessing/presolve/cypresolve.cpython-310-x86_64-linux-gnu.so: undefined symbol: _ZN3fmt2v96detail18throw_format_errorEPKc

Logs: https://dev.azure.com/conda-forge/feedstock-builds/_build/results?buildId=634321&view=logs&jobId=aaada960-d85f-5b88-82e5-99df4d27a2ce&j=aaada960-d85f-5b88-82e5-99df4d27a2ce&t=1169dac8-f5b1-5012-e49a-d6d84b7b929b
Context: conda-forge/dwave-preprocessing-feedstock#11

Am I missing something during building or what could that be?

Use FEASIBILITY_TOLERANCE when removing redundant equality constraints

See

dwave-preprocessing/dwave/preprocessing/src/presolveimpl.hpp

Line 519 in 432f9e6

if (minac == constraint.rhs() && maxac == constraint.rhs()) {

Add tests for float("inf") biases/offset/rhs/bounds

We have tests for NaN. We should add a similar set of +/-inf.

Mark models with no constraints as feasible in presolve

Currently there are no cases where we mark a model as being feasible. However, we could/should in the case that the model has no constraints.

Getting segmentation faults when submitting empty BQMs to FixVariablesComposite

Might be coming from dimod - not sure.

Improve performance of Roof Duality through parallelization & better variable to vertex mapping.

Three steps take most of the time.

Creation of implication network.
Computing Max-Flow.
Making implication network symmetric.

These three steps can be made faster by the following techniques and should be implemented when we have a good parallel Max-Flow algorithm at our disposal (otherwise Amdahl's law will come in effect).

Creation of Implication network :

For very large graphs, we can create all the edges corresponding to a vertex in parallel. Creating the edges of different vertices in parallel is not a good thing, since it will lead to too much contention and we have to use locks throughout the process. But to parallelize the creation of all the edges of a single vertex in parallel we need to do two things.

Keep an explicit posiform - many biases in the QUBO for a variable do not contribute to the implication network as they are flushed to zeroes when converted to an integral type, thus we cannot parallelize the creation of all the edges corresponding to a variable, as the index where the edge will be in the adjacency list will not be dependent on the index/iterator offset of the QUBO bias for that vertex, it will be dependent on the index/offset of the posiform coefficient. We can create the posiform in parallel though but having an explicit posiform will increase the memory requirement by around 25%.

Basically we want something like this :

for (vertex = 0 ;vertex < last_parallel vertex; vertex++) {
  #pragma omp parallel 
   // Note the counter does not go from 0 - num_out_edges, since other 
   // vertices lead to out edges coming out of vertex, that is why we also 
   // add counter[vertex] to out_edge to calculate index_of_edge_of_vertex.
   for(out_edge = 0; out_edge < num_posiform_coefficients; out_edge++) {
        // All threads write to different indices so no lock needed.
       index_of_edge_of_vertex = counter[vertex] + out_edge; 
       // This does not need a lock as only threads do not access 
       // common destination/destination_complement vertices.
       index_of_destination = counter[destination];
       Create edge;
       // Skipping code for symmetric and residual edges, 
       // 4 edges will be created in total. (see implication network)
       // Only one edge created out of destination and destination_complement.
       counter[destination]++;
       counter[destination_complement]++;
   }
   counter[vertex] += num_posiform_coefficients;
   counter[vertex_complement] += num_posiform_coefficients;
}

// We are processing an upper triangular matrix in essence,
// processing the edges of the last vertices in parallel is not efficient,
// since they do not have many outgoing edges.
for(vertex = last_parallel_vertex; vertex < num_vertices; vertex++) {
   Process them in serial
 }

Use of pointers instead of vectors - We have to preallocate the amount of memory we will need and each thread will write to the exact position, this can be done using vectors too but the resize() function of vectors adds too much overhead.

We should not try to parallelize the creation of the graph for BQMs that do not use random access iterators, for example adjMapBQM, since the benefit will be very low.

Computing Max-Flow :

There are many papers claiming much better performance than the push_relabel algorithm we have implemented but we have to note two things :

One is some of them are tuned for computer vision tasks, they may perform very poorly for common graphs.

Secondly these algorithms are generally compared with off the shelf implementations of push_relabel algorithm, some comparisons online where the serial and parallel version of the code are written by the same author show that there is not much benefit in parallizing a good implementation of push_relabel algorithm. So we can wait for a better parallel algorithm to be developed before we opt for parallelizing max-flow computation.

The breadth-first search is not a bottleneck now but it could also be parallelized, but that would require us to call openmp functions explicitly.

Making Residual Graph symmetric: - DONE

This is a step very easy to parallelize and have been parallelized already. But the problem is we are mapping variable 0-n-1 to vertex 0-n-1, n is the source and n+1 - 2n are the complements of the variables and 2n+1 is the sink. If we map variable 0 to vertex 0,1 , variable 1 to vertex 2,3 then in the adjacency list of the implication network the outedges from a vertex will end up being created in a sorted order based on the original variable. In the step where we make the residual network symmetric, a thread processes an edge and its symmetric version. But we cannot allow two different threads to process the edges twice, that is the thread that encounters the original edge and the thread that encounters the symmetric edge, we decide which thread will process them based on the comparison of indices of the source & destination variable. (see code).
Instead of doing this check every time, if the edges were sorted, we could do a binary search for each thread and start processing from the right position. We are skipping this step since that makes the code harder to read. Note for this optimization to work we must process the vertices in order, since that will create the edges in order. What it means is that we must create all the edges out of the source when it is time to create all the edges out of the source, and not create the edges to each vertex from the source when processing the respective vertex.

The above mentioned update to the step of making residual graph symmetric is done, now the mapping is separated into s different file of its own mapping_policy.hpp. The other code that is code outside of mapping_policy is more or less independent of the mapping methodology now.

Fix broken link to docs in readme

Consider making `SpinReveralTransformComposite` respect `initial_state` arguments

Right now the SRT composite will ignore initial_state arguments, which means that the initial states are not correspondingly transformed.

We could sniff out that specific argument name, and then do the relevant transformation. But that is a bit of a hack.

`ImportError` after pip installing `dwave-system`

Description
Installing dwave-system in a fresh environment throws an import error when attempting to import the dwave.system module.
See full trace:

>>> from dwave.system import LeapHybridCQMSampler
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\system\__init__.py", line 15, in <module>
    import dwave.system.flux_bias_offsets
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\system\flux_bias_offsets.py", line 22, in <module>
    from dwave.system.samplers.dwave_sampler import DWaveSampler
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\system\samplers\__init__.py", line 15, in <module>
    from dwave.system.samplers.clique import *
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\system\samplers\clique.py", line 25, in <module>
    from dwave.preprocessing import ScaleComposite
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\preprocessing\__init__.py", line 18, in <module>
    import dwave.preprocessing.composites
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\preprocessing\composites\__init__.py", line 17, in <module>
    from dwave.preprocessing.composites.fix_variables import *
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\preprocessing\composites\fix_variables.py", line 22, in <module>
    from dwave.preprocessing.lower_bounds import roof_duality
  File "C:\Users\mchristensen\envs\test_dws_1.18\lib\site-packages\dwave\preprocessing\lower_bounds.py", line 17, in <module>
    from dwave.preprocessing.cyfix_variables import fix_variables_wrapper
ImportError: DLL load failed while importing cyfix_variables: The specified module could not be found.

This traces back to dwave.preprocessing, particularly version 0.6.2 which gets pulled in due to this line in setup.py:
'dwave-preprocessing>=0.5.0'

To Reproduce
In a fresh virtual environment with no packages installed:
pip install dwave-system==1.18.0 (tested with 1.18.0, 1.19.0, 1.20.0)
Then open a terminal and try:
import dwave.system

Expected behavior
Perhaps installing the maximum compatible version of preprocessing which seems to be 0.6.1

Environment:

OS: Windows 10 Pro 64-bit (10.0, build 19043)
Python version: Python 3.8.3

Incorporate lower bounds

dwavesystems/dimod#567

Consider renaming fix_variables function to roof_duality

Since we're releasing a new package, perhaps we should consider using a more explicit name. The deprecated dimod function can still be called fix_variables.

Separate normalization and presolving

It would be useful to separate normalizing techniques from presolving techniques. This would allow flows like

presolver = Presolver(cqm)

presolver.load_default_techniques()
try:
    presolver.apply()
except InfeasibleError:
    normalization_presolver = Presolver(cqm)
    normalization_presolver.load_normalization_techniques()
    normalization_presolver.apply()

See #62

Failing to install on Linux AArch64

Build is failing on Linux AArch64 machine

System details:
Linux 1pthunderx1-137 5.4.0-60-generic #67-Ubuntu SMP Tue Jan 5 18:24:57 UTC 2021 aarch64 aarch64 aarch64 GNU/Linux
u

Build Failure logs: logs.txt

Raise an InvalidModelError when given NaN bounds

#101 introduced a method to test whether biases were NaN, but we should also check that the bounds

SpinReversalTransformComposite not handling empty BQMs

Run the dimod.testing.load_sampler_bqm_tests to reproduce. We should add these tests to test_spin_reversal_transform.py once this bug is fixed.

======================================================================
ERROR: test_sample_binary_DictBQM_empty_<dwave.preprocessing.composites.spin_reversal_transform.SpinReversalTransformComposite object at 0x1050d9850> (tests.test_spin_reversal_transform.TestSpinTransformComposite)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/Users/htong/env39/lib/python3.9/site-packages/dimod/testing/sampler.py", line 68, in method
    return f(self, *args)
  File "/Users/htong/env39/lib/python3.9/site-packages/dimod/testing/sampler.py", line 32, in test_sample
    sampleset = sampler.sample(bqm)
  File "/Users/htong/Desktop/dwavesystems/dwave-preprocessing/dwave/preprocessing/composites/spin_reversal_transform.py", line 120, in sample
    return concatenate(responses)
  File "/Users/htong/env39/lib/python3.9/site-packages/dimod/sampleset.py", line 399, in concatenate
    record = recfunctions.stack_arrays(records, defaults=defaults,
  File "<__array_function__ internals>", line 5, in stack_arrays
  File "/Users/htong/env39/lib/python3.9/site-packages/numpy/lib/recfunctions.py", line 1318, in stack_arrays
    output[name][i:j] = a[name]
  File "/Users/htong/env39/lib/python3.9/site-packages/numpy/ma/core.py", line 3319, in __getitem__
    dout._fill_value.flat[0]).all():
IndexError: index 0 is out of bounds for axis 0 with size 0

Remove unusued variables in Presolve

It would be useful to remove any variables that are not used in the objective or constraints.

Conflicts with dwave-cloud-client because both install /usr/local/lib/python3.9/site-packages/dwave/init.py

Increase stacklevel on UserWarning

dwave-preprocessing/dwave/preprocessing/composites/fix_variables.py

Line 125 in 7862154

warnings.warn(msg)

should use stacklevel=2

Add timeout

It would be useful to have a timeout. E.g.

presolver.apply(timeout=10.5)

Presolver class docs should note that variables are relabeled

Currently a user would not expect that the model in the Presolver class is relabled to integer labels:

>>> cqm.variables
Variables(['a'])
>>> pre = Presolver(cqm)
>>> cqm2 = pre.copy_model()
>>> cqm2.variables
Variables([0])

Question: Is this to reduce the in-memory CQM size similar to when big CQMs are uploaded by LeapHybridCQMSampler() for example? It would be easier to use the copies if they kept the variable names of the original.

Installation from source fails on Cython

In a new virtual environment in WIN10 OS using Python 3.6, installation from source,

pip install -r requirements.txt
python setup.py build_ext --inplace

fails on cython:

python setup.py build_ext --inplace
Compiling dwave/preprocessing/cyfix_variables.pyx because it changed.
[1/1] Cythonizing dwave/preprocessing/cyfix_variables.pyx

Error compiling Cython file:
------------------------------------------------------------
...
from libcpp.vector cimport vector
from libcpp cimport bool as cppbool

import dimod
from dimod import AdjVectorBQM
from dimod.bqm.cppbqm cimport AdjVectorBQM as cppAdjVectorBQM
^
------------------------------------------------------------

dwave\preprocessing\cyfix_variables.pyx:24:0: 'dimod\bqm\cppbqm.pxd' not found

Error compiling Cython file:
------------------------------------------------------------
...
from libcpp.vector cimport vector
from libcpp cimport bool as cppbool

import dimod
from dimod import AdjVectorBQM
from dimod.bqm.cppbqm cimport AdjVectorBQM as cppAdjVectorBQM
^
------------------------------------------------------------

dwave\preprocessing\cyfix_variables.pyx:24:0: 'dimod\bqm\cppbqm\AdjVectorBQM.pxd' not found

Error compiling Cython file:
------------------------------------------------------------
...
from libcpp cimport bool as cppbool

import dimod
from dimod import AdjVectorBQM
from dimod.bqm.cppbqm cimport AdjVectorBQM as cppAdjVectorBQM
from dimod cimport cyAdjVectorBQM
^
------------------------------------------------------------

dwave\preprocessing\cyfix_variables.pyx:25:0: 'dimod.pxd' not found

Error compiling Cython file:
------------------------------------------------------------
...
from libcpp cimport bool as cppbool

import dimod
from dimod import AdjVectorBQM
from dimod.bqm.cppbqm cimport AdjVectorBQM as cppAdjVectorBQM
from dimod cimport cyAdjVectorBQM
^
------------------------------------------------------------

dwave\preprocessing\cyfix_variables.pyx:25:0: 'dimod\cyAdjVectorBQM.pxd' not found

Error compiling Cython file:
------------------------------------------------------------
...
from dimod.bqm.cppbqm cimport AdjVectorBQM as cppAdjVectorBQM
from dimod cimport cyAdjVectorBQM
from dimod.vartypes import Vartype

cdef extern from "include/dwave-preprocessing/fix_variables.hpp" namespace "fix_variables_":
    vector[pair[int, int]] fixQuboVariables[V, B](cppAdjVectorBQM[V, B]& refBQM,
                                                 ^
------------------------------------------------------------

dwave\preprocessing\cyfix_variables.pyx:29:50: 'cppAdjVectorBQM' is not a type identifier

Error compiling Cython file:
------------------------------------------------------------
...
    if bqm.vartype is not Vartype.BINARY:
        raise ValueError("bqm must be BINARY")
    if not all(v in bqm.linear for v in range(len(bqm))):
        raise ValueError("bqm must be linearly indexed")

    cdef cyAdjVectorBQM cybqm = dimod.as_bqm(bqm, cls=AdjVectorBQM)
        ^
------------------------------------------------------------

dwave\preprocessing\cyfix_variables.pyx:51:9: 'cyAdjVectorBQM' is not a type identifier

Error compiling Cython file:
------------------------------------------------------------
...
        raise ValueError("bqm must be BINARY")
    if not all(v in bqm.linear for v in range(len(bqm))):
        raise ValueError("bqm must be linearly indexed")

    cdef cyAdjVectorBQM cybqm = dimod.as_bqm(bqm, cls=AdjVectorBQM)
    fixed = fixQuboVariables(cybqm.bqm_, bool(strict))
                           ^
------------------------------------------------------------

dwave\preprocessing\cyfix_variables.pyx:52:28: Unable to deduce type parameter V, B
Traceback (most recent call last):
  File "setup.py", line 57, in <module>
    nthreads=int(os.getenv('CYTHON_NTHREADS', 0)),
  File "C:\Users\jpasvolsky\!git_ADTT\preprocessing\lib\site-packages\Cython\Build\Dependencies.py", line 1102, in cythonize
    cythonize_one(*args)
  File "C:\Users\jpasvolsky\!git_ADTT\preprocessing\lib\site-packages\Cython\Build\Dependencies.py", line 1225, in cythonize_one
    raise CompileError(None, pyx_file)
Cython.Compiler.Errors.CompileError: dwave/preprocessing/cyfix_variables.pyx

Incoroporate extended roof duality

dwavesystems/dimod#545

Compress pairs variables related by linear equality

Feature request:

If a constraint of the form a x_1 + b x_2 = c,
remove the variable x_2 be substituting x_2 = c/a - b/a x_2.
Translate solutions back to full variable set afterwards.

These kinds of constraints show up in a number of application in problems (especially linear problems), as it is often assumed the impact of the redundant variables on the speed of solution will be negligible.

Remove single variable constraints missing constraints like `x >= a`, when the `a` is strictly larger than `x`'s upper bound

I'll fix this and #78 together in the same PR

Installation from PyPi fails on missing NumPy

In a new virtual environment in WIN10 OS using Python 3.6, installation from PyPi, pip install dwave-preprocessing fails.

pip install dwave-preprocessing
Collecting dwave-preprocessing
  Using cached dwave-preprocessing-0.1.1.tar.gz (62 kB)
    ERROR: Command errored out with exit status 1:
     command: 'c:\users\jpasvolsky\!git_adtt\preprocessing\scripts\python.exe' -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\\Users\\jpasvolsky\\AppData\\Local\\Temp\\pip-install-7gz6g7t2\\dwave-preprocessing_e54f6ea941544163a14e1d3f0a31f300\\setup.py'"'"'; __file__='"'"'C:\\Users\\jpasvolsky\\AppData\\Local\\Temp\\pip-install-7gz6g7t2\\dwave-preprocessing_e54f6ea941544163a14e1d3f0a31f300\\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'"'"'))' egg_info --egg-base 'C:\Users\jpasvolsky\AppData\Local\Temp\pip-pip-egg-info-6xezr56r'
         cwd: C:\Users\jpasvolsky\AppData\Local\Temp\pip-install-7gz6g7t2\dwave-preprocessing_e54f6ea941544163a14e1d3f0a31f300\
    Complete output (5 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "C:\Users\jpasvolsky\AppData\Local\Temp\pip-install-7gz6g7t2\dwave-preprocessing_e54f6ea941544163a14e1d3f0a31f300\setup.py", line 19, in <module>
        import numpy
    ModuleNotFoundError: No module named 'numpy'
    ----------------------------------------
WARNING: Discarding https://files.pythonhosted.org/packages/67/d3/dff294154297d936fe137230d03eb1d6b764dcf3bc06fbbfb8c6b85628ba/dwave-preprocessing-0.1.1.tar.gz#sha256=fb858610a630bbc087d481f6c36aa90039d24b0a20ed2bac4c14e7c39e2e8a8f (from https://pypi.org/simple/dwave-preprocessing/) (requires-python:>=3.6). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
  Using cached dwave-preprocessing-0.1.0.tar.gz (58 kB)
    ERROR: Command errored out with exit status 1:
     command: 'c:\users\jpasvolsky\!git_adtt\preprocessing\scripts\python.exe' -c 'import io, os, sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\\Users\\jpasvolsky\\AppData\\Local\\Temp\\pip-install-7gz6g7t2\\dwave-preprocessing_98d156d7353845f1b61e9d394f16c5b1\\setup.py'"'"'; __file__='"'"'C:\\Users\\jpasvolsky\\AppData\\Local\\Temp\\pip-install-7gz6g7t2\\dwave-preprocessing_98d156d7353845f1b61e9d394f16c5b1\\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'"'"'))' egg_info --egg-base 'C:\Users\jpasvolsky\AppData\Local\Temp\pip-pip-egg-info-zu4d235f'
         cwd: C:\Users\jpasvolsky\AppData\Local\Temp\pip-install-7gz6g7t2\dwave-preprocessing_98d156d7353845f1b61e9d394f16c5b1\
    Complete output (5 lines):
    Traceback (most recent call last):
      File "<string>", line 1, in <module>
      File "C:\Users\jpasvolsky\AppData\Local\Temp\pip-install-7gz6g7t2\dwave-preprocessing_98d156d7353845f1b61e9d394f16c5b1\setup.py", line 19, in <module>
        import numpy
    ModuleNotFoundError: No module named 'numpy'
    ----------------------------------------
WARNING: Discarding https://files.pythonhosted.org/packages/66/6a/71ecc31e5dfca0a7c130946416cc29ed0c130f0e8c2f68ee59c8cae8a880/dwave-preprocessing-0.1.0.tar.gz#sha256=c90dba47d9294c05280b76a9f1cff6c9b3b2f28b3625d76421a5547a5f58f475 (from https://pypi.org/simple/dwave-preprocessing/) (requires-python:>=3.6). Command errored out with exit status 1: python setup.py egg_info Check the logs for full command output.
ERROR: Could not find a version that satisfies the requirement dwave-preprocessing (from versions: 0.1.0rc1, 0.1.0, 0.1.1rc1, 0.1.1rc2, 0.1.1)
ERROR: No matching distribution found for dwave-preprocessing

README should be updated to also mention presolve

Currently the README just talks about tools for BQMs: "dwave-preprocessing is a package of common preprocessing tools that can aid in solving binary quadratic models (BQM)." That should change to "... quadratic models" and say it provides presolve too

Consider refactoring SpinReversalTransformComposite

There are a few changes we could/should make to the SpinReversalTransformComposite

Make it nonblocking. Currently it will submit each SRT serially. It would be trivial to make it non-blocking instead. Probably the easiest thing would be to use the dimod.decorators.nonblocking_sample_method decorator like we do with the ScaleComposite.
Change the default num_spin_reversal_transforms to 0. It's currently set to 1.
Change the way it handles num_reads. Currently it will multiply num_spin_reversal_transforms and num_reads, we could instead check whether num_reads are present and divide appropriately. This would be more consistent with the current server-side behaviour. Alternative: make the multiplying behavior more clear in the documentation.

IMO (1) and (2) are no-brainers. (3) I am a bit more skeptical of, I am currently leaning towards the alternative. But needs more thought.

Propagate the `info` field from the child sampler

Adding this specifically for the FixVariablesComposite (in addition to the generally known issue of propagating info) because for this one, once variables are dropped, the embedding context becomes very helpful, not just the timing info.

Return SRTs from SpinReveralTransformComposite

It would be quite straightforward to add a return_transforms=False kwarg. The only difficult part is deciding what to return - we could obviously return the SRT matrix, but we would probably want to indicate which variables are matched to which columns somehow.

Consider loading default techniques by default in Presolve

It does seem a bit redundant to do

pre = Presolver(cqm)
pre.load_default_techniques()
pre.apply()

when most non-expert users will likely want those techniques.

We could instead allow users to set the techniques explicitly while keeping the default that they are on

pre = Presolver(cqm)
pre.set_techniques(Technique1, Technique2)  # override the default
pre.apply()

Presolver.detach_model() should cause subsequent access to model to fail

The detach_model() docs say "Subsequent attempts to access the model will raise a RuntimeError" but that is not happening:

pre = Presolver(cqm)
pre.load_default_presolvers()
pre.detach_model()
cqm2 = pre.copy_model()
>>> type(cqm2)
dimod.constrained.constrained.ConstrainedQuadraticModel
>>> cqm2.is_equal(dimod.ConstrainedQuadraticModel())
True

The post-detach cqm2 = pre.copy_model() command gives no error and happily generates an empty CQM.

Add CutVertexComposite

See dwavesystems/dimod#548

3 tests fail

======================================================================
ERROR: test_ignored_interactions (test_scale.TestScaleComposite)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/disk-samsung/freebsd-ports/science/py-preprocessing/work-py39/dwave-preprocessing-0.4.0/tests/test_scale.py", line 70, in test_ignored_interactions
    dtest.assert_sampleset_energies(sampleset, bqm)
  File "/usr/local/lib/python3.9/site-packages/dimod/testing/asserts.py", line 204, in assert_sampleset_energies
    for sample, energy in sampleset.data(['sample', 'energy']):
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1251, in data
    record = self.record
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1100, in record
    self.resolve()
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1449, in resolve
    samples = self._result_hook(self._future)
  File "/usr/local/lib/python3.9/site-packages/dimod/decorators.py", line 86, in <lambda>
    return SampleSet.from_future(next(iterator), lambda _: next(iterator))
  File "/disk-samsung/freebsd-ports/science/py-preprocessing/work-py39/stage/usr/local/lib/python3.9/site-packages/dwave/preprocessing/composites/scale.py", line 140, in sample
    sampleset.record.energy = original_bqm.energies(sampleset)
  File "/usr/local/lib/python3.9/site-packages/dimod/binary/binary_quadratic_model.py", line 1092, in energies
    return self.data.energies(samples_like, dtype=dtype)
  File "dimod/binary/cybqm/cybqm_template.pyx.pxi", line 360, in dimod.binary.cybqm.cybqm_float64.cyBQM_template.energies
  File "/usr/local/lib/python3.9/functools.py", line 888, in wrapper
    return dispatch(args[0].__class__)(*args, **kw)
TypeError: _as_samples_sampleset() got an unexpected keyword argument 'labels_type'

======================================================================
ERROR: test_ignored_offset (test_scale.TestScaleComposite)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/disk-samsung/freebsd-ports/science/py-preprocessing/work-py39/dwave-preprocessing-0.4.0/tests/test_scale.py", line 85, in test_ignored_offset
    dtest.assert_sampleset_energies(sampleset, bqm)
  File "/usr/local/lib/python3.9/site-packages/dimod/testing/asserts.py", line 204, in assert_sampleset_energies
    for sample, energy in sampleset.data(['sample', 'energy']):
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1251, in data
    record = self.record
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1100, in record
    self.resolve()
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1449, in resolve
    samples = self._result_hook(self._future)
  File "/usr/local/lib/python3.9/site-packages/dimod/decorators.py", line 86, in <lambda>
    return SampleSet.from_future(next(iterator), lambda _: next(iterator))
  File "/disk-samsung/freebsd-ports/science/py-preprocessing/work-py39/stage/usr/local/lib/python3.9/site-packages/dwave/preprocessing/composites/scale.py", line 140, in sample
    sampleset.record.energy = original_bqm.energies(sampleset)
  File "/usr/local/lib/python3.9/site-packages/dimod/binary/binary_quadratic_model.py", line 1092, in energies
    return self.data.energies(samples_like, dtype=dtype)
  File "dimod/binary/cybqm/cybqm_template.pyx.pxi", line 360, in dimod.binary.cybqm.cybqm_float64.cyBQM_template.energies
  File "/usr/local/lib/python3.9/functools.py", line 888, in wrapper
    return dispatch(args[0].__class__)(*args, **kw)
TypeError: _as_samples_sampleset() got an unexpected keyword argument 'labels_type'

======================================================================
ERROR: test_ignored_variables (test_scale.TestScaleComposite)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/disk-samsung/freebsd-ports/science/py-preprocessing/work-py39/dwave-preprocessing-0.4.0/tests/test_scale.py", line 100, in test_ignored_variables
    dtest.assert_sampleset_energies(sampleset, bqm)
  File "/usr/local/lib/python3.9/site-packages/dimod/testing/asserts.py", line 204, in assert_sampleset_energies
    for sample, energy in sampleset.data(['sample', 'energy']):
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1251, in data
    record = self.record
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1100, in record
    self.resolve()
  File "/usr/local/lib/python3.9/site-packages/dimod/sampleset.py", line 1449, in resolve
    samples = self._result_hook(self._future)
  File "/usr/local/lib/python3.9/site-packages/dimod/decorators.py", line 86, in <lambda>
    return SampleSet.from_future(next(iterator), lambda _: next(iterator))
  File "/disk-samsung/freebsd-ports/science/py-preprocessing/work-py39/stage/usr/local/lib/python3.9/site-packages/dwave/preprocessing/composites/scale.py", line 140, in sample
    sampleset.record.energy = original_bqm.energies(sampleset)
  File "/usr/local/lib/python3.9/site-packages/dimod/binary/binary_quadratic_model.py", line 1092, in energies
    return self.data.energies(samples_like, dtype=dtype)
  File "dimod/binary/cybqm/cybqm_template.pyx.pxi", line 360, in dimod.binary.cybqm.cybqm_float64.cyBQM_template.energies
  File "/usr/local/lib/python3.9/functools.py", line 888, in wrapper
    return dispatch(args[0].__class__)(*args, **kw)
TypeError: _as_samples_sampleset() got an unexpected keyword argument 'labels_type'

----------------------------------------------------------------------
Ran 326 tests in 0.733s

FAILED (errors=3)

Version: 0.4.0
Python 3.9
FreeBSD 13.1

1 test fails: test_zero_biases AssertionError: -inf != 5

======================================================================
FAIL: test_zero_biases (test_presolve.TestPresolver)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/usr/ports/science/py-dwave-preprocessing/work-py39/dwave-preprocessing-0.5.4/tests/test_presolve.py", line 267, in test_zero_biases
    self.assertEqual(cqm.upper_bound(0), +5)
AssertionError: -inf != 5

----------------------------------------------------------------------
Ran 337 tests in 0.526s

Version: 0.5.4
FreeBSD 13.1

C++ tests fail to link: ld: error: undefined symbol: operator delete(void*)

cc -O2 -pipe  -fstack-protector-strong -fno-strict-aliasing   -L/usr/local/lib -lspdlog -pthread -lfmt  -fstack-protector-strong  test_main.o  -o test_main.out
ld: error: undefined symbol: operator delete(void*)
>>> referenced by test_main.cpp
>>>               test_main.o:(Catch::Detail::Approx::toString() const)
>>> referenced by test_main.cpp
>>>               test_main.o:(Catch::Detail::Approx::toString() const)
>>> referenced by test_main.cpp
>>>               test_main.o:(Catch::Detail::Approx::setMargin(double))
>>> referenced 2412 more times

dwave-preprocessing is built using clang-15.

Version: 0.5.4
FreeBSD 13.2

Calculate more numerically accurate lower bound.

In roof duality, we convert a bqm to a posiform , convert its coefficients to integer coefficients, then convert it to an implication graph and find the max flow. We use the max flow to compute the lower bound of the bqm, but we may be able to take the original posiform use the fixed variables and find the lower bound. This will bypass the float-to-integer and integer-to-float conversions and provide a more accurate lower bound. We need to find out a way how to use the original posiform since roof duality will not fix all the variables in the posiform.

Discussion: Should we remove "trivial" constraints as part of normalization?

For constraints like x <= 1, we can trivially convert them into bounds. The question is whether that's a normalization step or a presolve step. This becomes most relevant in the infeasible case.

Argument for normalization

One argument for doing it in normalization is that these sorts of trivial constraints are easy to construct when a user is not familiar with the API. It may seem more intuitive to do

x = cqm.add_variable("INTEGER", "x")
cqm.add_constraint(x <= 5)

than

cqm.add_variable("INTEGER", "x", upper_bound=5)

so the user's "intention" may be to treat these constraints as bounds.

Another reason is that having trivially infeasible bounds is likely to indicate a bug in the user's code.

Argument for presolve

This is (to me) the more consistent approach.

Fix SpinReversalTransformComposite to work with NullSampler etc

Moved from dwavesystems/dimod#629

"SpinReversalTransformComposite fails when the child sampler returns empty samplesets. See https://github.com/dwavesystems/dimod/pull/627/files#diff-591becf8218c51ff0b7708c0a149d2e2R25 in dwavesystems/dimod#627"

Provide a better error message for infeasible models

Right now, the error message for an infeasible model is a terse "given CQM is infeasible". It would be good to provide more information to help the user debug.

This will likely be difficult, as we run into the issues in #59 (comment). Perhaps the best approach would be to encourage the user to rerun with logging. That of course assumes that we have added logging by then.

Convert integers with 0 <= i <= 1 bounds to binary variables

It's not uncommon for binary variables to be encoded as integers.

Default num_spin_reversal_transforms to 1 in SpinReversalTransformComposite

Moved from dwavesystems/dimod#813

Wheel build fails due to circular dependency with dimod

Building dwave-preprocessing from source (via PEP-517 build system), requires dimod~=0.10.0, which, in turn, in versions >=0.10.5 requires dwave-preprocessing>=0.3,<0.4. As a result, pip wheel fails to install the (yet unreleased) version of dwave-preprocessing, and falls back to installing the latest for which it can find a wheel:

See for example this build of 0.3.1:

Created temporary directory: /tmp/pip-ephem-wheel-cache-e6b6j2px
Created temporary directory: /tmp/pip-req-tracker-ecez82nl
Initialized build tracking at /tmp/pip-req-tracker-ecez82nl
Created build tracker: /tmp/pip-req-tracker-ecez82nl
Entered build tracker: /tmp/pip-req-tracker-ecez82nl
Created temporary directory: /tmp/pip-wheel-lh7m08dq
Processing /dwave/preprocessing
  Created temporary directory: /tmp/pip-req-build-h47germ4
  DEPRECATION: A future pip version will change local packages to be built in-place without first copying to a temporary directory. We recommend you use --use-feature=in-tree-build to test your packages with this new behavior before it becomes the default.
   pip 21.3 will remove support for this functionality. You can find discussion regarding this at https://github.com/pypa/pip/issues/7555.
  Added file:///dwave/preprocessing to build tracker '/tmp/pip-req-tracker-ecez82nl'
  Created temporary directory: /tmp/pip-build-env-xmkbzxsj
  Created temporary directory: /tmp/pip-standalone-pip-9ifxkzl3
  Running command /opt/_internal/cpython-3.9.7/bin/python3.9 /tmp/pip-standalone-pip-9ifxkzl3/__env_pip__.zip/pip install --ignore-installed --no-user --prefix /tmp/pip-build-env-xmkbzxsj/overlay --no-warn-script-location -v --no-binary :none: --only-binary :none: -i https://pypi.org/simple -- 'setuptools>=46.4.0' 'wheel>=0.30.0' 'Cython>=0.29.21,<3.0' numpy==1.19.4 'dimod>=0.10.0.dev9,<0.11.0'
  Using pip 21.2.4 from /tmp/pip-standalone-pip-9ifxkzl3/__env_pip__.zip/pip (python 3.9)
  Collecting setuptools>=46.4.0
    Using cached setuptools-58.2.0-py3-none-any.whl (946 kB)
  Collecting wheel>=0.30.0
    Using cached wheel-0.37.0-py2.py3-none-any.whl (35 kB)
  Collecting Cython<3.0,>=0.29.21
    Using cached Cython-0.29.24-cp39-cp39-manylinux1_x86_64.whl (1.9 MB)
  Collecting numpy==1.19.4
    Using cached numpy-1.19.4-cp39-cp39-manylinux1_x86_64.whl (13.4 MB)
  Collecting dimod<0.11.0,>=0.10.0.dev9
    Using cached dimod-0.10.7-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl (10.6 MB)
  Collecting pyparsing<3.0.0,>=2.4.7
    Using cached pyparsing-2.4.7-py2.py3-none-any.whl (67 kB)
  Collecting dwave-preprocessing<0.4,>=0.3
    Using cached dwave-preprocessing-0.3.1.tar.gz (159 kB)
    Installing build dependencies: started
    Running command /opt/_internal/cpython-3.9.7/bin/python3.9 /tmp/pip-standalone-pip-9ifxkzl3/__env_pip__.zip/pip install --ignore-installed --no-user --prefix /tmp/pip-build-env-z40lauk3/overlay --no-warn-script-location --no-binary :none: --only-binary :none: -i https://pypi.org/simple -- 'setuptools>=46.4.0' 'wheel>=0.30.0' 'Cython>=0.29.21,<3.0' numpy==1.19.4 'dimod>=0.10.0.dev9,<0.11.0'
    Collecting setuptools>=46.4.0
      Using cached setuptools-58.2.0-py3-none-any.whl (946 kB)
    Collecting wheel>=0.30.0
      Using cached wheel-0.37.0-py2.py3-none-any.whl (35 kB)
    Collecting Cython<3.0,>=0.29.21
      Using cached Cython-0.29.24-cp39-cp39-manylinux1_x86_64.whl (1.9 MB)
    Collecting numpy==1.19.4
      Using cached numpy-1.19.4-cp39-cp39-manylinux1_x86_64.whl (13.4 MB)
    Collecting dimod<0.11.0,>=0.10.0.dev9
      Using cached dimod-0.10.7-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl (10.6 MB)
    Collecting pyparsing<3.0.0,>=2.4.7
      Using cached pyparsing-2.4.7-py2.py3-none-any.whl (67 kB)
    Collecting dwave-preprocessing<0.4,>=0.3
      Using cached dwave-preprocessing-0.3.1.tar.gz (159 kB)
    ERROR: Exception:
    Traceback (most recent call last):
      File "/tmp/pip-standalone-pip-9ifxkzl3/__env_pip__.zip/pip/_internal/cli/base_command.py", line 173, in _main
        status = self.run(options, args)
      ...
      File "/tmp/pip-standalone-pip-9ifxkzl3/__env_pip__.zip/pip/_internal/req/req_tracker.py", line 97, in add
        raise LookupError(message)
    LookupError: https://files.pythonhosted.org/packages/9d/6e/51d3f843bafea371f3d96cf35a2e5c85e6d17c264cf3799ad6c11043c0c4/dwave-preprocessing-0.3.1.tar.gz#sha256=360e886a2e89f3f4aa0d3ddf448c71a2eaab74183000687bcafb1175682f8775 (from https://pypi.org/simple/dwave-preprocessing/) (requires-python:>=3.6) is already being built: dwave-preprocessing<0.4,>=0.3 from https://files.pythonhosted.org/packages/9d/6e/51d3f843bafea371f3d96cf35a2e5c85e6d17c264cf3799ad6c11043c0c4/dwave-preprocessing-0.3.1.tar.gz#sha256=360e886a2e89f3f4aa0d3ddf448c71a2eaab74183000687bcafb1175682f8775 (from dimod<0.11.0,>=0.10.0.dev9)
    Installing build dependencies: finished with status 'error'
  WARNING: Discarding https://files.pythonhosted.org/packages/9d/6e/51d3f843bafea371f3d96cf35a2e5c85e6d17c264cf3799ad6c11043c0c4/dwave-preprocessing-0.3.1.tar.gz#sha256=360e886a2e89f3f4aa0d3ddf448c71a2eaab74183000687bcafb1175682f8775 (from https://pypi.org/simple/dwave-preprocessing/) (requires-python:>=3.6). Command errored out with exit status 2: /opt/_internal/cpython-3.9.7/bin/python3.9 /tmp/pip-standalone-pip-9ifxkzl3/__env_pip__.zip/pip install --ignore-installed --no-user --prefix /tmp/pip-build-env-z40lauk3/overlay --no-warn-script-location --no-binary :none: --only-binary :none: -i https://pypi.org/simple -- 'setuptools>=46.4.0' 'wheel>=0.30.0' 'Cython>=0.29.21,<3.0' numpy==1.19.4 'dimod>=0.10.0.dev9,<0.11.0' Check the logs for full command output.
    Using cached dwave_preprocessing-0.3.0-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.whl (770 kB)

As a short-term fix, we can use dimod<0.10.5 for building, but longer-term we should revisit the solution in dwavesystems/dimod#999 to dwavesystems/dimod#989.

Presolve sometimes leaves fixed variables in the model

An example found by @JoelPasvolsky as part of https://github.com/dwave-examples/tour-planning

Objective (Maximize Exercise):

    -8.4*cycle_0 + 0*bus_0 - 8.6*cycle_1 + 0*bus_1 - 4.6*cycle_2 + 0*bus_2 - 8.8*cycle_3 + 0*bus_3 - 4.3*cycle_4 + 0*bus_4 - 4.6*cycle_5 + 0*bus_5 - 8.5*cycle_6 + 0*bus_6 - 3.3*cycle_7 + 0*bus_7 - 7.3*cycle_8 + 0*bus_8 - 1.6*cycle_9 + 0*bus_9 - 1.5*cycle_10 + 0*bus_10 - 1.1*cycle_11 + 0*bus_11 - 9*cycle_12 + 0*bus_12 - 8.4*cycle_13 + 0*bus_13 - 4.3*cycle_14 + 0*bus_14 - 2.5*cycle_15 + 0*bus_15 - 3.2*cycle_16 + 0*bus_16 - 3.1*cycle_17 + 0*bus_17 - 4.9*cycle_18 + 0*bus_18 - 5.6*cycle_19 + 0*bus_19

Cost Constraint: 

    cycle_0 + 5*bus_0 + cycle_1 + 5*bus_1 + cycle_2 + 5*bus_2 + cycle_3 + 5*bus_3 + cycle_4 + 5*bus_4 + cycle_5 + 5*bus_5 + cycle_6 + 5*bus_6 + cycle_7 + 5*bus_7 + cycle_8 + 5*bus_8 + cycle_9 + 5*bus_9 + cycle_10 + 5*bus_10 + cycle_11 + 5*bus_11 + cycle_12 + 5*bus_12 + cycle_13 + 5*bus_13 + cycle_14 + 5*bus_14 + cycle_15 + 5*bus_15 + cycle_16 + 5*bus_16 + cycle_17 + 5*bus_17 + cycle_18 + 5*bus_18 + cycle_19 + 5*bus_19 <= 150.0

Time Constraint: 

    cycle_0 + 0.2*bus_0 + cycle_1 + 0.2*bus_1 + cycle_2 + 0.2*bus_2 + cycle_3 + 0.2*bus_3 + cycle_4 + 0.2*bus_4 + cycle_5 + 0.2*bus_5 + cycle_6 + 0.2*bus_6 + cycle_7 + 0.2*bus_7 + cycle_8 + 0.2*bus_8 + cycle_9 + 0.2*bus_9 + cycle_10 + 0.2*bus_10 + cycle_11 + 0.2*bus_11 + cycle_12 + 0.2*bus_12 + cycle_13 + 0.2*bus_13 + cycle_14 + 0.2*bus_14 + cycle_15 + 0.2*bus_15 + cycle_16 + 0.2*bus_16 + cycle_17 + 0.2*bus_17 + cycle_18 + 0.2*bus_18 + cycle_19 + 0.2*bus_19 <= 8.0

Slope Constraints: 

    Too steep to cycle on leg 0: 8.4*cycle_0 <= 2.0
    Too steep to cycle on leg 1: 8.6*cycle_1 <= 2.0
    Too steep to cycle on leg 2: 4.6*cycle_2 <= 2.0
    Too steep to cycle on leg 3: 8.8*cycle_3 <= 2.0
    Too steep to cycle on leg 4: 4.3*cycle_4 <= 2.0
    Too steep to cycle on leg 5: 4.6*cycle_5 <= 2.0
    Too steep to cycle on leg 6: 8.5*cycle_6 <= 2.0
    Too steep to cycle on leg 7: 3.3*cycle_7 <= 2.0
    Too steep to cycle on leg 8: 7.3*cycle_8 <= 2.0
    Too steep to cycle on leg 9: 1.6*cycle_9 <= 2.0
    Too steep to cycle on leg 10: 1.5*cycle_10 <= 2.0
    Too steep to cycle on leg 11: 1.1*cycle_11 <= 2.0
    Too steep to cycle on leg 12: 9*cycle_12 <= 2.0
    Too steep to cycle on leg 13: 8.4*cycle_13 <= 2.0
    Too steep to cycle on leg 14: 4.3*cycle_14 <= 2.0
    Too steep to cycle on leg 15: 2.5*cycle_15 <= 2.0
    Too steep to cycle on leg 16: 3.2*cycle_16 <= 2.0
    Too steep to cycle on leg 17: 3.1*cycle_17 <= 2.0
    Too steep to cycle on leg 18: 4.9*cycle_18 <= 2.0
    Too steep to cycle on leg 19: 5.6*cycle_19 <= 2.0

Single-Locomotion-Mode-Per-Leg Constraints: 

    One-hot leg0: cycle_0 + bus_0 == 1.0
    One-hot leg1: cycle_1 + bus_1 == 1.0
    One-hot leg2: cycle_2 + bus_2 == 1.0
    One-hot leg3: cycle_3 + bus_3 == 1.0
    One-hot leg4: cycle_4 + bus_4 == 1.0
    One-hot leg5: cycle_5 + bus_5 == 1.0
    One-hot leg6: cycle_6 + bus_6 == 1.0
    One-hot leg7: cycle_7 + bus_7 == 1.0
    One-hot leg8: cycle_8 + bus_8 == 1.0
    One-hot leg9: cycle_9 + bus_9 == 1.0
    One-hot leg10: cycle_10 + bus_10 == 1.0
    One-hot leg11: cycle_11 + bus_11 == 1.0
    One-hot leg12: cycle_12 + bus_12 == 1.0
    One-hot leg13: cycle_13 + bus_13 == 1.0
    One-hot leg14: cycle_14 + bus_14 == 1.0
    One-hot leg15: cycle_15 + bus_15 == 1.0
    One-hot leg16: cycle_16 + bus_16 == 1.0
    One-hot leg17: cycle_17 + bus_17 == 1.0
    One-hot leg18: cycle_18 + bus_18 == 1.0
    One-hot leg19: cycle_19 + bus_19 == 1.0

Consider reimplementing C++ Presolver using a pointer to implementation

It would be easier to maintain backwards compatibility etc if we used the PImpl pattern.

This would give us a directory structure like

dwave/preprocessing/
    include/
        presolve.hpp
    src/
        presolve.cpp
        presolveimpl.hpp

The other huge benefit here is that we make PresolveImpl a full-fledged class that can be unittested. This gives us the ability to unittest individual techniques without exposing them to the user.

Consider removing C++ PostSolver

I think the current postsolver pattern doesn't actually provide much benefit. I think a much better pattern is something like

class Presolver() {
 public:
    void apply();  // do presolve
    vector<assignment_type> unapply(vector<assignment_type> sample);  // restore a sample. Could use a different name

    CQM detach_model();  // can still allow this for memory savings
 private:
     class ModelHandler {
     public:
        // these can be made thread safe and keeps the changes in sync with transforms
        void remove_variable(index_type v);  
        void add_variable(Vartype vartype);

        // modifying the expressions in separate threads is safe and changes don't need to be saved in transforms
        auto& objective() { return model_.objective; }
        auto constraints() { return model_.constraints(); }
     private:
        CQM model_;
        vector<Transform> transforms_;
     };
};

Benefits:

Removes the superfluous PostSolver class, simplifying user code
Sets us up much better for thread safety
Safer pattern in terms of keeping the CQM/transforms list in sync

Additional Context
We don't even have a notion of a PostSolver at the Cython/Python level so no change there.