Building a constraint programming solver in Julia(opensourc.es)
opensourc.es
Building a constraint programming solver in Julia
http://opensourc.es/blog/constraint-solver-1
3 comments
I tried to follow the instructions and it failed, as julia stuff always tend to fail (with unhelpful error messages).
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.
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
Could we use this for arbitrary constraints like for mechanical modeling, or 3d animation?
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!
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!
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!!
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!
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!
What about mechanical constraints that are expressed in terms of integer ratios? Could constraint programming be useful for that subset of mechanical constraints?
[deleted]
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
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?
https://cad.onshape.com/help/Content/constraints.htm
Onshape is free to demo, so give it a whirl?
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.
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.
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
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
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.
"Magic" is just jargon for a complicated algorithm.
[deleted]
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?
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
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] 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]