core.logic for constraint logic programming

[nathanmarz]

I'm looking into rewriting Storm's resource scheduler using
core.logic. I want to be able to say constraints like:

1. Topology A's slots should be <= 10 and as close to 10 as possible
(minimize the delta between assigned slots and 10)
2. All topologies should use less than 200 CPU's and less than 600 GB
of memory
3. Topology B should run at most 2 workers on each host
4. Each worker for topology C should run at most one task for
component X and one task for component Y
5. Should minimize the amount of reassignment to running topologies in
order to satisfy constraints
6. Should only be allowed to reassign workers for an individual
topology whose individual constraints are satisfied once every 10
minutes

And so on. I have two questions:

1. How good is core.logic at culling the search space using arithmetic
logic? For example, if it knows that x + y <= 5, x>=0, and y>=0, it
should never bother with areas of the search space where x or y are
>=5.
2. Can core.logic do things like search the space for which my
evaulation criteria are minimized? Or is what we're trying to do a
better fit for different techniques like linear programming?

[David Nolen]

On Wed, Oct 24, 2012 at 4:56 PM, nathanmarz <natha...@gmail.com> wrote:

I'm looking into rewriting Storm's resource scheduler using
core.logic. I want to be able to say constraints like:

1. Topology A's slots should be <= 10 and as close to 10 as possible
(minimize the delta between assigned slots and 10)

The minimization bit is not in core.logic yet. But basically anything in Mozart/OZ's Finite Domain Constraint Programming feature set is on the table for core.logic :)

 

2. All topologies should use less than 200 CPU's and less than 600 GB
of memory
3. Topology B should run at most 2 workers on each host
4. Each worker for topology C should run at most one task for
component X and one task for component Y
5. Should minimize the amount of reassignment to running topologies in
order to satisfy constraints
6. Should only be allowed to reassign workers for an individual
topology whose individual constraints are satisfied once every 10
minutes

Yep definitely sounds like the kind of thing I'd like core.logic to be used for.

 

And so on. I have two questions:

1. How good is core.logic at culling the search space using arithmetic
logic? For example, if it knows that x + y <= 5, x>=0, and y>=0, it
should never bother with areas of the search space where x or y are
>=5.

While there's always room to improve it already does this well.

 

2. Can core.logic do things like search the space for which my
evaulation criteria are minimized? Or is what we're trying to do a
better fit for different techniques like linear programming?

It can, but I need to sit down and figure out how to make that work. If I recall the Mozart/OZ work is pretty clear about their approach and I think it can easily be adapted. I'll try to find some time and get back to you on that.

David 

[nathanmarz]

Cool, thanks for the quick response. We'll be looking into this pretty
soon. I ultimately want the logic engine itself being exposed to users
so they can add their own company-specific constraints to resource
scheduling – which will be totally badass. If you're interested in
tracking this, I opened up an issue on Storm: https://github.com/nathanmarz/storm/issues/383

On Oct 24, 2:07 pm, David Nolen <dnolen.li...@gmail.com> wrote:

[Ben Mabey]

I don't know enough about core.logic to comment on that, but my first impression upon reading your problem description is that integer programming would solve the problem (core.logic may be a better fit though).  However, I'm not sure how you would model in your last requirement (but I don't have too much experience with LP/IP modelling).  In the past I've used GLPK[1] for these types of problems which has java bindings [2].

This (older) paper[3] discusses the difference between mathematical programming (LP/IP) and constraint programming.  If you jump to the summary it provides some guidelines on when each approach makes more sense than the other.  I just reread the summary and it seems like constraint-based or perhaps a hybrid solution would be best.  So, in my unqualified opinion, if you can make core.logic work that may be the best fit and may simplify your life (GLPK is a big dep).

-Ben

1. http://www.gnu.org/software/glpk/
2. http://glpk-java.sourceforge.net/
3. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.6862

[David Nolen]

On Wed, Oct 24, 2012 at 5:17 PM, nathanmarz <natha...@gmail.com> wrote:

Cool, thanks for the quick response. We'll be looking into this pretty
soon. I ultimately want the logic engine itself being exposed to users
so they can add their own company-specific constraints to resource
scheduling – which will be totally badass. If you're interested in
tracking this, I opened up an issue on Storm: https://github.com/nathanmarz/storm/issues/383

Interesting, in what form will you expose this functionality to users? As some kind of DSL?

I actually thought about minimization for a few more minutes. Minimization is not hard, it's really just about which values in a domain should be tried first. These are called distribution strategies in Mozart/Oz and I already sketched out how this might work in core.logic.

I will add that JaCoP http://www.jacop.eu looks pretty mature / performant. I'm not sure how much interoperability with existing Clojure data structures comes into play for your particular use case.

David

[Andy Fingerhut]

Nathan:

I don't know core.logic's capabilities, and I haven't looked at the kinds of constraints you describe in enough detail to say for sure, but my initial reaction is that linear/integer programming might be a better fit.

It has been about 5-10 years, but in the past I've had success with relatively small to medium scale problems using an open source package called lp_solve for such things. I haven't tried it with more than a few hundred variables and constraints to see how well it performs there.

http://sourceforge.net/projects/lpsolve/

Besides SourceForge, it is also available as a MacPorts package called lp_solve, or an Ubuntu 12.04 package "lp-solve" (probably Debian and other Ubuntu versions, too, but I only checked that one).

Andy

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

[David Nolen]

On Wed, Oct 24, 2012 at 5:35 PM, Andy Fingerhut <andy.fi...@gmail.com> wrote:

Nathan:

I don't know core.logic's capabilities, and I haven't looked at the kinds of constraints you describe in enough detail to say for sure, but my initial reaction is that linear/integer programming might be a better fit.

I'm not sure if this is true if you want non-expert users to easily customize it. Constraint Logic Programming tends to allow descriptions closer to the domain -

I may be offbase here but I found this comparison of the techniques highly illuminating - 

"Constraint Logic Programming and Integer Programming approaches and their collaboration in solving an assignment scheduling problem" - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.1461

David

[Jamie Brandon]

It sounds like something that would benefit from good constraint
propagation. If I remember correctly, core.logic only support
propagating equality/inequality constraints which can be pretty slow
for exploring large domains. Something like gecode
(http://www.gecode.org) might be a better fit if you want to use large
integer domains.

Where core.logic lvars can only be assigned or fresh, gecode
explicitly represents the domain of each variable and can efficiently
propagate constraints across them. In your example, x and y would both
have domain [0,5]. If you added the constraint x >=3, after
propagation you would have x: [3,5] y:[0,2]

Gecode also has support for custom search strategies which would allow
writing heuristics for minimisation. I'm not sure if gecode would ever
be as fast as a linear programming solution but it's certainly more
flexible.

I wrote a constraint solver in clojoure based on the same ideas -
https://github.com/jamii/mist/tree/master/src/shackles . It's only a
toy and it could do with some macro love to hide the state threading
but it demonstrates the basic ideas.

[David Nolen]

On Wed, Oct 24, 2012 at 6:07 PM, Jamie Brandon <ja...@scattered-thoughts.net> wrote:

It sounds like something that would benefit from good constraint
propagation. If I remember correctly, core.logic only support
propagating equality/inequality constraints which can be pretty slow
for exploring large domains. Something like gecode
(http://www.gecode.org) might be a better fit if you want to use large
integer domains.

Where core.logic lvars can only be assigned or fresh, gecode
explicitly represents the domain of each variable and can efficiently
propagate constraints across them. In your example, x and y would both
have domain [0,5]. If you added the constraint x >=3, after
propagation you would have x: [3,5] y:[0,2]

Not true anymore - we have interval propagation and we actually leverage it unlike the Scheme cKanren implementation. There's still plenty of room for improvement.

 

Gecode also has support for custom search strategies which would allow
writing heuristics for minimisation. I'm not sure if gecode would ever
be as fast as a linear programming solution but it's certainly more
flexible.

Yes this what I was talking about when I referred to the Mozart/Oz distribute facility. This is pretty simple to add to core.logic as far as I can tell as I've stated earlier.

[Jamie Brandon]

Ok, clearly I've not been keeping up, sorry :)

[nathanmarz]

Wow, thanks for the great information everyone.

David – I don't know how we'll make it pluggable, I was thinking users
could provide functions that return a set of constraints. And there
would probably be a cost function that users could override as well.

On Oct 24, 3:26 pm, Jamie Brandon <ja...@scattered-thoughts.net>
wrote:

> Ok, clearly I've not been keeping up, sorry :)
>