As a person not heavily invested in Prolog, can you explain how that works? Is it just branching by choices from the different groups and it backtracks/fails back up to the last choice if constraints are not met?
I must say I'm not familiar at all with constraint programming, but it looks like something I've been wanting to know for a long time.
A practical problem I have right now is writing a device driver that needs to configure Phase Locked Loops in order to generate certain frequencies. However the setup is not straightforward, I have to configure a set of divisors, multipliers and some muxes. To make matters worse, at each step I have constraints for the possible frequency range at that point. And finally I sometimes have several of those PLL in series.
The only solution I have right now is using a C program that bruteforces all combinations, checks if the constraints are satisfied and outputs an array of configs for the subset of frequencies I need. If I need a new frequency I have to re-run my program and update the array. It works but is far from ideal.
Unfortunately all the tutorials I find online for this CP thing are using prolog or some third party library in C++, which is of course not practical for kernel programming...
If I could implement a clever solver that would run fast enough (unlike my bruteforce solution) I could just do it dynamically in the driver and it'd be much more elegant.
But I really don't know where to start. Any pointers/things to google for?
Are you proposing to write a simple constraint solver in C? If it's specific to your problem i.e. not too general, it's not the craziest idea I've ever heard.
I don't mind fielding questions over the basic theory if you want to email me (iain at my domain).
I think the best advice I could give you is to be aware that what you're hoping for -- an algorithm with performance bounds tight enough that you can use it in a device driver -- probably doesn't exist. There is some chance, admittedly, that you will get lucky and find some structure in the problem that you can exploit to produce such an algorithm. But it's also entirely possible that there isn't any such structure, and the fact that you've resorted to brute force search to this point suggests there may not be.
Even if there isn't, there is still hope for ways to search the space faster. This problem sounds like something that an SMT solver might work well on. I would give that a try.
Here is a collection of open source Operations Research (CP and LP falls under the umbrella of Operations Research) projects: http://www.coin-or.org/projects/
There are many fantastic open source libraries in there to handle many types of optimization or assignment.
First we start with what 'mathematical' programming
(optimization) is. For a reasonably general definition,
let R denote the set of real numbers and m and n be
positive integers. Let R^n be real n-dimensional
space, that is, the set of n-tuples of real numbers.
Let x be in R^n.
Next we have two functions. We have an 'objective'
function f: R^n --> R, and we have a 'constraint'
function g: R^n --> R^m. We can think of g as
m functions mapping R^n --> R. Then the optimization
problem is to find x so that f(x) is as large as
possible while g(x) = 0 where here 0 is the
point in R^m with all components 0. Or we can
ask that g(x) <= 0 by which we mean that each of
the m components of g(x) is <= 0 in R. In 'linear
programming', functions f and g are both linear.
So, function f is given by just n coefficients, and
function g is given by an m x n matrix.
If there exists x in R^n so that g(x) = 0
(or <= 0 for that version of the problem), then
x is a 'feasible' solution. If x is feasible
and for any feasible solution u in R^n we have
that f(x) >= f(u), then x is an 'optimal'
solution.
Linear programming where we ask that all the
components of x be integers is 'integer' linear
programming (ILP) and is in NP-complete. Industry
is awash in important ILP problems, e.g., airline
scheduling. There is an enormous literature on
practical means of solving ILP problems; Google
Nemhauser long at Georgia Tech.
The problem may fail to be feasible. If the problem
is feasible, it may fail to have an optimal solution.
Constraint programming is the same except we have
no objective function and are looking for just
feasible solutions.
Since in principle finding a feasible solution is
as hard as finding an optimal solution, constraint
programming is essentially the same subject as
mathematical programming (optimization).
Constraint programming is nice when a planner is
just trying to get some work done and knows that
the cost will be the same for all alternatives.
E.g., maybe yesterday they killed 5000 hogs,
overnight chilled them down, today are cutting
them into pieces and putting the pieces into
boxes, and during the day want to back 18 wheel
refrigerated trucks into the small loading dock
in the right order to get all the boxes loaded
and each truck with the boxes it needs for its
deliveries. Once a real problem.
SAP in Germany has wanted to offer constraint
programming as part of its software suite.
Since constraint programming is essentially
the same (mostly just different in how the
user sees it and, thus, the user interface)
as mathematical progamming, at one time SAP
worked with C-PLEX, with some of the best
software for linear and integer programming,
the company of R. Bixby, long at Rice U.
His restaurant problem is a special case of
the knapsack problem where we have some items
to carry, a value of each, and a weight of each,
and a knapsack with a maximum weight we can carry, and we want
to know what items to put in the knapsack to
maximize the value but not exceed the
maximum weight.
For the restaurant problem, for each
item on the menu, just set both the
value and the weight to the price,
and for the maximum weight of the knapsack
just use the budget.
Now, knapsack problems are in NP-complete,
as I recall, but they are, in practice,
among the easiest to solve. The usual
recommendation for solving a large
knapsack problem is via dynamic programming.
Something is missing from this discussion. The sample problem in the xkcd comic is from a class of NP-complete problems, but being small, it has a solution in "pseudo-polynomial time"[1] that can be solved by a variety of tools, as demonstrated in these comments.
Even though this simple example can be solved, the general problem (from a set of N integers, find all subsets that add up to a given integer x) is nonetheless NP-complete. The method of computation (Excel, Prolog, constraint programming, Turing machine) does not change this fact.
Why 0..10? I think it would be instructional to mention how you chose these domains. Is minizinc smart enough to only go as high as necessary? If you had put 0..1000 would it have tested all 10001000100010001000*1000 combinations, or is it smart enough to ignore fruit > 7 and salad > 2?
There are three phases to Constraint Programming: (1) Model (2) Constraints (3) Search & Propagation.
The first step in solving a problem with CP is to come up with a representation for a solution. This involves deciding what your variables will represent (in this case, "How many orders of each appetiser") and what is their possible domain of values (in this case, "0 to 10" has been chosen, quite arbitrarily).
The solver itself is generally dumb. It will propagate some constraints sensibly but mostly it will just search over the entire space - equal to the size of the domain to the power of the number of variables. 11^6 = 1.8 million, quite a small CP problem.
There's a bit of an art in creating a good model for a CSP (Constraint Satisfaction Problem) to keep the search space as small as it needs to be.
EDIT: Just to be clear...
The way constraint solvers work is to make a decisions in a Depth First Search manner and judge the validity of the new state after each choice. So after fruit > 7 and salad > 2, bounds consistency on the constraint will rule out the possibility of reaching a solution from that node in the search tree.
Yup though the solver does this for us anyway. Constraint propagation allows the solver to reduce the search space, reducing the domains of variables before traversing the tree.
It is "smart" enough. Before and then during searching the problem space the solver performs constraint propagation, which is a bunch of clever algorithms (the maths for I am yet to grok) that reduce the domains of variables. This allows it to reduce the problem space to something reasonable.
So why 10? I guess I was being lazy! But you are right I will do an update with some more in the domains.
You can set an upper limit that is total/price, I guess he chose 0..10 since it's obvious that 10 of anything is already too much, and I think minizinc tightens the bounds anyway, since that's something it can do independently of giving a complete solution.
This is just a linear programming problem. One-liner solution in Mathematica, just for kicks:
In[1]:= Solve[
Rationalize[2.15 a + 2.75 b + 3.35 c + 3.55 d + 4.20 e + 5.80 f == 15.05] &&
a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0 && f >= 0,
{a, b, c, d, e, f}, Integers
]
Out[1]= {{a -> 1, b -> 0, c -> 0, d -> 2, e -> 0, f -> 1},
{a -> 7, b -> 0, c -> 0, d -> 0, e -> 0, f -> 0}}
Linear programming as it's usually defined allows for the solution to involve arbitrary real numbers, and it's that flexibility that allows general LPs to be solved in polynomial time. The restriction to integers turns this into an integer programming problem, which is NP-Complete. Though that doesn't seem to bother Mathematica (which presumably has a similar sort of constraint solver working under the hood). :-)
> So it’s not even that I figured out something clever. It’s just I have the patience to do the thing that no one would think of, or that anyone would ever bother to do. And sometimes that’s key. It’s just like I have that much free time.
Is the Z3 theorem prover an example of a CP tool? For those interested, Z3 is one of the world's fastest theorem provers and has been open sourced by Microsoft. Theorem provers have many interesting applications, but one of my favorites is using them to represent a program's state and reasoning about the exploitability of bugs. It has bindings to C, C++, .NET and Python. Check it out if it interests you:
http://z3.codeplex.com/ or try it online at http://rise4fun.com/z3py
Before you download Z3 and dive in, be aware that Z3 is not Open Source. It's licensed under a non-commercial license[0], which is not compatible with the Open Source definition[1]. Muddying the term Open Source will diminish its descriptive usefulness.
Z3 is based on SMT (satisfiability-modulo-theories), not constraint programming. You can probably do some constraint programming in it, but that's not what it's designed for.
We use CPLEX for LPs but I've not read much on the CPLEX CP solver. Maybe because it isn't free so the academics stick with the OSS ones? How does it compare to gecode?
cp is fascinating. if people are interested, here's a write-up from a similar exploration, using choco (a constraint solver in java) to solve a problem on stackoverflow:
I agree, it is! I did a light comparison[0] between a logic programming solution to sudoku (Prolog) and one using constraint programming (Scala + JaCoP). I thought Prolog was a little nicer because it was shorter and more declarative, but the JaCoP solution was still great compared to any non CP-solution.
It is not, because it is a single linear equality and all variables are >= 0. This is not just nitpicking: solving Diophantine problems is in general undecidable, but this problem can be solved in pseudo-polynomial time (linear in the sum of all coefficients)
Does anyone know what algorithm this CP implementation is using behind the scenes? I'd be a lot more impressed if it were using dynamic programming than plain brute force.
[+] [-] lake99|13 years ago|reply
[+] [-] maaaats|13 years ago|reply
[+] [-] swannodette|13 years ago|reply
[+] [-] amouat|13 years ago|reply
I think the original post has one of the prices wrong.
BTW thanks for working on this stuff swannodette - I hope to look into core.logic in the not too distant future...
EDIT: Yes, his price for salad is 3.25 instead of 3.35
[+] [-] simias|13 years ago|reply
A practical problem I have right now is writing a device driver that needs to configure Phase Locked Loops in order to generate certain frequencies. However the setup is not straightforward, I have to configure a set of divisors, multipliers and some muxes. To make matters worse, at each step I have constraints for the possible frequency range at that point. And finally I sometimes have several of those PLL in series.
The only solution I have right now is using a C program that bruteforces all combinations, checks if the constraints are satisfied and outputs an array of configs for the subset of frequencies I need. If I need a new frequency I have to re-run my program and update the array. It works but is far from ideal.
Unfortunately all the tutorials I find online for this CP thing are using prolog or some third party library in C++, which is of course not practical for kernel programming...
If I could implement a clever solver that would run fast enough (unlike my bruteforce solution) I could just do it dynamically in the driver and it'd be much more elegant.
But I really don't know where to start. Any pointers/things to google for?
[+] [-] lifebeyondfife|13 years ago|reply
I don't mind fielding questions over the basic theory if you want to email me (iain at my domain).
[+] [-] ScottBurson|13 years ago|reply
Even if there isn't, there is still hope for ways to search the space faster. This problem sounds like something that an SMT solver might work well on. I would give that a try.
[+] [-] pvarangot|13 years ago|reply
[+] [-] mipmap|13 years ago|reply
There are many fantastic open source libraries in there to handle many types of optimization or assignment.
[+] [-] graycat|13 years ago|reply
First we start with what 'mathematical' programming (optimization) is. For a reasonably general definition, let R denote the set of real numbers and m and n be positive integers. Let R^n be real n-dimensional space, that is, the set of n-tuples of real numbers. Let x be in R^n.
Next we have two functions. We have an 'objective' function f: R^n --> R, and we have a 'constraint' function g: R^n --> R^m. We can think of g as m functions mapping R^n --> R. Then the optimization problem is to find x so that f(x) is as large as possible while g(x) = 0 where here 0 is the point in R^m with all components 0. Or we can ask that g(x) <= 0 by which we mean that each of the m components of g(x) is <= 0 in R. In 'linear programming', functions f and g are both linear. So, function f is given by just n coefficients, and function g is given by an m x n matrix.
If there exists x in R^n so that g(x) = 0 (or <= 0 for that version of the problem), then x is a 'feasible' solution. If x is feasible and for any feasible solution u in R^n we have that f(x) >= f(u), then x is an 'optimal' solution.
Linear programming where we ask that all the components of x be integers is 'integer' linear programming (ILP) and is in NP-complete. Industry is awash in important ILP problems, e.g., airline scheduling. There is an enormous literature on practical means of solving ILP problems; Google Nemhauser long at Georgia Tech.
The problem may fail to be feasible. If the problem is feasible, it may fail to have an optimal solution.
Constraint programming is the same except we have no objective function and are looking for just feasible solutions.
Since in principle finding a feasible solution is as hard as finding an optimal solution, constraint programming is essentially the same subject as mathematical programming (optimization).
Constraint programming is nice when a planner is just trying to get some work done and knows that the cost will be the same for all alternatives. E.g., maybe yesterday they killed 5000 hogs, overnight chilled them down, today are cutting them into pieces and putting the pieces into boxes, and during the day want to back 18 wheel refrigerated trucks into the small loading dock in the right order to get all the boxes loaded and each truck with the boxes it needs for its deliveries. Once a real problem.
SAP in Germany has wanted to offer constraint programming as part of its software suite. Since constraint programming is essentially the same (mostly just different in how the user sees it and, thus, the user interface) as mathematical progamming, at one time SAP worked with C-PLEX, with some of the best software for linear and integer programming, the company of R. Bixby, long at Rice U.
[+] [-] graycat|13 years ago|reply
For the restaurant problem, for each item on the menu, just set both the value and the weight to the price, and for the maximum weight of the knapsack just use the budget.
Now, knapsack problems are in NP-complete, as I recall, but they are, in practice, among the easiest to solve. The usual recommendation for solving a large knapsack problem is via dynamic programming.
[+] [-] 205guy|13 years ago|reply
Even though this simple example can be solved, the general problem (from a set of N integers, find all subsets that add up to a given integer x) is nonetheless NP-complete. The method of computation (Excel, Prolog, constraint programming, Turing machine) does not change this fact.
[1] https://news.ycombinator.com/item?id=5780552
[+] [-] mrgoldenbrown|13 years ago|reply
[+] [-] lifebeyondfife|13 years ago|reply
The first step in solving a problem with CP is to come up with a representation for a solution. This involves deciding what your variables will represent (in this case, "How many orders of each appetiser") and what is their possible domain of values (in this case, "0 to 10" has been chosen, quite arbitrarily).
The solver itself is generally dumb. It will propagate some constraints sensibly but mostly it will just search over the entire space - equal to the size of the domain to the power of the number of variables. 11^6 = 1.8 million, quite a small CP problem.
There's a bit of an art in creating a good model for a CSP (Constraint Satisfaction Problem) to keep the search space as small as it needs to be.
EDIT: Just to be clear...
The way constraint solvers work is to make a decisions in a Depth First Search manner and judge the validity of the new state after each choice. So after fruit > 7 and salad > 2, bounds consistency on the constraint will rule out the possibility of reaching a solution from that node in the search tree.
[+] [-] simias|13 years ago|reply
Yup though the solver does this for us anyway. Constraint propagation allows the solver to reduce the search space, reducing the domains of variables before traversing the tree.
[+] [-] hartror|13 years ago|reply
So why 10? I guess I was being lazy! But you are right I will do an update with some more in the domains.
http://en.m.wikipedia.org/wiki/Constraint_propagation
[+] [-] unknown|13 years ago|reply
[deleted]
[+] [-] pliny|13 years ago|reply
[+] [-] illicium|13 years ago|reply
[+] [-] davmre|13 years ago|reply
[+] [-] stcredzero|13 years ago|reply
http://www.maa.org/mathhorizons/MH-Sep2012_XKCD.html
[+] [-] krenoten|13 years ago|reply
[+] [-] nitrogen|13 years ago|reply
[0] http://z3.codeplex.com/SourceControl/latest#LICENSE.txt
[1] http://opensource.org/osd#fields-of-endeavor
[+] [-] colanderman|13 years ago|reply
[+] [-] unknown|13 years ago|reply
[deleted]
[+] [-] mistermcgruff|13 years ago|reply
The IBM CPLEX CP optimizer is best for this kind of stuff IMHO.
[+] [-] hartror|13 years ago|reply
[+] [-] andrewcooke|13 years ago|reply
write-up - http://isti.bitbucket.org/2012/04/07/pipes-clojure-choco-5.h...
problem - http://stackoverflow.com/questions/9689436/backtracking-solu...
and another problem on stackoverflow that i was going to solve with cp, but which ended up being analytic - http://stackoverflow.com/questions/7076349/is-there-a-good-w...
[+] [-] nickknw|13 years ago|reply
[0] - http://nickknowlson.com/blog/2012/08/06/seven-languages-week...
[+] [-] bjourne|13 years ago|reply
[+] [-] woqe|13 years ago|reply
[+] [-] gkatsi|13 years ago|reply
[+] [-] mariorz|13 years ago|reply
https://github.com/mariorz/pytorovich/blob/master/examples/x...
[+] [-] igul222|13 years ago|reply
[+] [-] hartror|13 years ago|reply
[+] [-] rscale|13 years ago|reply
http://cl.ly/image/1X2S121l2C3O
No nerd cred, but it crosses the finish line.
[+] [-] swannodette|13 years ago|reply
[+] [-] mistermcgruff|13 years ago|reply
[+] [-] la-conic|13 years ago|reply
[deleted]