search

chocoteam / choco-solver

An open-source Java library for Constraint Programming
http://choco-solver.org/
BSD 4-Clause "Original" or "Old" License
687 stars 137 forks source link

[FEATURE] MultivaluedDecisionDiagram : Making the compact method optionnal #1089

Closed ib31 closed 3 months ago

ib31 commented 6 months ago

I'm currently working on utilizing the MultivaluedDecisionDiagram class to handle an MDD I've constructed through knowledge compilation. This MDD is quite large, and I've already applied heuristics to minimize its size. However, I've encountered an issue with the mandatory compact() method in the MultivaluedDecisionDiagram class. This method for detecting and removing isomorphisms seems to have exponential time complexity, which becomes problematic for the largest instances, leading to out of memory errors.

Do you think it is possible to have a constructor to handle mdds as it is instead of trying to compact() them? It would call the method init(int[][] TRANSITIONS) but without calling the method compact(). Thus the call for compact() would be optionnal.

So far i've tried this on my local sources of choco-solver and it works for my large instances of MDD.

cprudhom commented 3 months ago

What you are looking for is to totally disable compaction? I suppose I can change the boolean parameter to an int (0: no compaction, 1: compact once, otherwise compact after each tuple addition), what do you think?

ib31 commented 3 months ago

Yes please it would be great !

Additionally, i can give you the model (variables and transitions array) that makes this method run endlessly.