dimod icon indicating copy to clipboard operation
dimod copied to clipboard

More performant handling of linear constraints in CQM

Open arcondello opened this issue 3 years ago • 0 comments

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
  1. 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

arcondello avatar Jan 06 '22 17:01 arcondello