dwavesystems / dwavesystems/dimod
More performant handling of linear constraints in CQM
- Dominant language
- Python
- Stars
- 143
- Forks
- 91
- Avg merge
- 1h 24m
- Merged PRs (30d)
- 3
Description
For large CQMs with lots of linear constraints, the user can run into memory/performance bottlenecks. One place we could potentially relieve the bottleneck is to _not_ encode the linear constraints as quadratic models. I see a few possible approaches:
1. Create a new `LinearModel` object or similar.
* Pro: relatively easy to implement
* Pro: utilizes the current structure, in that it just adds another model type. We already support BQM/QM
* Con: each linear constraint is its own object, which has a memory cost. Even worse, each linear model keeps its own `Variables` object which is redundant and potentially expensive from a memory perspective
2. Store linear constraints in a matrix or sparse matrix, something like `LinearConstraints` class
* Pro: compact
* Pro: shared variable labels
* Con: big change to the structure
* Con: we probably can't use scipy sparse matrices of numpy arrays, because we want them to be resizeable (mitigated with some pretty simple cython)
In either case I think we can maintain serialization compatibility by just continuing to serialize them as quadratic models
Contributor guide
Assessment
This issue has not been assessed yet.