Building a constraint programming solver in Julia

http://opensourc.es/blog/constraint-solver-1

by wikunia • 7 years ago

204 20 7 years ago

all22• 7 years ago

Could we use this for arbitrary constraints like for mechanical modeling, or 3d animation?

wikunia5• 7 years ago

Can you give me an example of how this would look like? This is an ongoing series so at the moment my solver can't solve much :D

all22• 7 years ago

I think this is a good example of mechanical constraints.

https://cad.onshape.com/help/Content/constraints.htm

Onshape is free to demo, so give it a whirl?

throwaway_bad• 7 years ago

I am not sure if it's what the OP meant, but g9.js has a lot of neat interactive examples: http://omrelli.ug/g9/gallery/

Basically you write a renderer for some data and have a constraint solver (just backprop I think for g9) to solve for the best data that will render something that fits the user input.

joe_the_user2• 7 years ago

I think the idea of a constraint solver is you begin with a constraint; Test(X), where X is in some large space S and Test is some expression yielding true or false.

Then the solver uses some magic to parse Test so that it can search S more efficiently than just loop over it. So if the solver is small enough, it seems like 3d animation could be done but the might need to be somewhat aware of that use.

See:

https://en.wikipedia.org/wiki/Constraint_programming

ausbah• 7 years ago

It isn't magic! To the best of my knowledge it's all about framing the problem as a graph, then performing a search on the graph to find solutions with some heuristics.

jefft255• 7 years ago

From a quick glance, this and most software doing “constraint programming” deal with discrete problems. Not saying those are useless for mechanical modeling or 3D animation, but those areas typically deal with continuous constraints which require different solvers. My experience in this is limited to a single class in CP 3 years ago so take this with a grain of salt!!

kdmccormick• 7 years ago

What about mechanical constraints that are expressed in terms of integer ratios? Could constraint programming be useful for that subset of mechanical constraints?

tobmlt2• 7 years ago

Using interval arithmetic and interval analysis, constraint solving can be extended to continuous problems. This seems first to have been done in the 80s by extending Prolog. As you say, most constraint software does not do this, but I vouch that it both exists and works!

I wrote a relational interval constraint solver for automated CAD design. It used constraints to eliminate infeasible regions of a design space before a nonlinear solver would generate the actual geometry. It was pretty fun puzzling out how to build this thing!

tobmlt2• 7 years ago

As part of my PhD dissertation, I wrote an "interval valued" constraint solver and a Python internal DSL based originally on miniKanren, that ran it. The intervals handle the floating point in interval chunks, allowing for set-like reasoning and relational constraint programming atop floating point.

I used it to operate on a design space as a single entity, or sliced into finite chunks, and to cut out sub-spaces of infeasible designs by constraint propagation.

I think interval valued relational constraint programming could be extended (and probably already has) for mechanical modeling, and 3D animation, yes. But the utility of a purely discrete constraint solver, such as the one posted here, is maybe less for these types of cases. Interval systems methods (for solving nonlinear equations) have a long history in optimization and motion planning. No reason a constraint solver couldn't be applied there. Similarly, if you have a specific use case, I could try and offer more about constraint solving for it.

I should also note that constraint solving with real or and especially interval data goes back to at least the 80s. I just made use of some low hanging fruit!

enriquto• 7 years ago

This is very cool! How does it compare with the features offered by GLPK? It seems to solve a super-set of glpk's problems? What are the tradeoffs of this generalization?

wikunia5• 7 years ago

This is not able to solve linear problems as it's built only for discrete variables in mind. The approach is more removing values from the search space to find a feasible solution whereas LP focuses on optimization. There are problems were both approaches can be used. Currently my solver is quite limited. Stay tuned

dnautics• 7 years ago

not sure if you were aware, but you could have initialized the grid like this:

    grid = 
      Int8[0 0 0 5 4 6 0 0 9
           0 2 0 0 0 0 0 0 7
           0 0 3 9 0 0 0 0 4
           9 0 5 0 0 0 0 7 0
           7 0 0 0 0 0 0 2 0
           0 0 0 0 9 3 0 0 0
           0 5 6 0 0 8 0 0 0
           0 1 0 0 3 9 0 0 0
           0 0 0 0 0 0 8 0 6]

siproprio2• 7 years ago

I tried to follow the instructions and it failed, as julia stuff always tend to fail (with unhelpful error messages).

    (ConstraintSolver) pkg> develop .
    [ Info: Assigning UUID 761e04fa-38db-5968-92db-bac8a6ce9725 to user_name
 Resolving package versions...
    ERROR: IOError: stat: unknown error (UNKNOWN)

wikunia5• 7 years ago

You probably want to develop on the Constraint solver instead of just installing, right? Then you can use `] dev https://github.com/Wikunia/ConstraintSolver.jl` You currently try to develop a package which already exists and that doesn't work. Yes the error message is unhelpful.

wikunia5• 7 years ago

looks like you used `activate .` to get into `ConstraintSolver Pkg>` then it's already done and you don't need develop or dev anymore Hope it helps

Building a constraint programming solver in Julia

Related Stories