dwavesystems / dwavesystems/dimod

More performant handling of linear constraints in CQM

Open
#1,072 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

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

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.