Parallel/Distributed Constraint Solving in miniKanren

[Cole Lyman]

Hi all,

I am interested in using miniKanren to solve some large constraint based models. The models are of biological networks that are currently implemented in MiniZinc and solved using OR-tools or Chuffed. The models are very under determined because of the sparsity of data and how the network dynamics are modeled, thus it is expected that many solutions exist for any given model.

To give an example of the scale that we are dealing with, using 100 cores (via a distributed version of Chuffed) it finds ~400 solutions in 48 hours. These solutions are great, but are limited by the MiniZinc specification and the complexity of the solvers. miniKanren is appealing because of the straightforward implementation of the solvers (and it has many implementations in Lisp, huge plus in my book).

My questions are:

• Would it be possible to get somewhat similar performance using a parallel/distributed miniKanren implementation?
• I know this is difficult to judge without seeing the nuts and bolts of the current model, but any intuition as to the scalability of miniKanren would be greatly appreciated.
  
• Are there any parallel/distributed miniKanren implementations?
  
• If not, could anyone give me an estimate of how difficult it would be to parallelize miniKanren? (e.g. afternoon, week, month, PhD thesis)
• I am also aware that difficulty is hard to judge because it is based on my proficiency, but again any intuition would be appreciated. (Thinking of this xkcd,
  https://xkcd.com/1425/)
• From William Byrd's SO answer here, https://stackoverflow.com/a/28556223/1947159, he says that it is at least theoretically trivially parallelizable, which gives me hope.
  

Please let me know if any clarification is needed.

Thank you,

Cole

If you would like to learn more about the formalism that our networks take, you can refer to this paper: https://bmcsystbiol.biomedcentral.com/articles/10.1186/s12918-018-0599-1 Note that this paper uses one of the smaller networks (solved in serial in a matter of seconds using Chuffed) and we are looking to expand the number of interactions in the network that we can model.

[William Byrd]

Hi Cole!

This sounds like an interesting project, and is perhaps of relevance
to the precision medicine work we are doing with miniKanren at UAB's
Hugh Kaul Precision Medicine Institute.

As far as parallelization, I think the difficulty level is related to
the problem. Sid Kumar, Tom Gilray, and I working on running
miniKanren on big hardware for program synthesis--your application may
be close enough for us to be able to tackle both problems.

Would you be up for a video call to talk about your problem more? If
so, shoot me an email!

Cheers,

--Will

> --
> You received this message because you are subscribed to the Google Groups "minikanren" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to minikanren+...@googlegroups.com.
> To post to this group, send email to minik...@googlegroups.com.
> Visit this group at https://groups.google.com/group/minikanren.
> For more options, visit https://groups.google.com/d/optout.