dwavesystems / dwavesystems/dimod

Deterministically ordered `BinaryPolynomial`

Open
#1,327 0 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Python
Stars
143
Forks
91
Avg merge
1h 24m
Merged PRs (30d)
3

Description

**Application**
The terms of a `BinaryPolynomial` are implemented with `frozenset`.
Python sets are unordered in a non-deterministic way. This leads to some interesting behavior that propagates to the related functions, `reduce_binary_polynomial` and `make_quadratic_cqm`.

Within a python invocation, it is possible to produce the same CQM model repeatedly, given the same `BinaryPolynomial` object.
This changes from run to run though, see this [post](https://stackoverflow.com/questions/3848091/set-iteration-order-varies-from-run-to-run#:~:text=The%20reason%20the%20set%20iteration,because%20of%20the%20random%20seed) on stackoverflow. This can lead to CQM models with different variables and constraints given the same `BinaryPolynomial`, or different reduced terms and constraints being returned from `reduce_binary_polynomial`.

It would be useful to be able to produce the same reduction results from run to run, rather than having to fix an environment variable to force the behavior.

**Proposed Solution**
Rework `BinaryPolynomial` and related functions to avoid sets - or possibly use something like an [ordered set](https://github.com/rspeer/ordered-set) instead.

**Alternatives Considered**
Setting the environment variable `PYTHONHASHSEED` makes set iteration deterministic. This has to be done prior to invoking Python.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.