3 ms·

Every time some OR or constraint programming language comes up, Håkan Kjellerstrand is an obligatory mention. He has a whole page dedicated to problems and exam

Every time some OR or constraint programming language comes up, Håkan Kjellerstrand is an obligatory mention. He has a whole page dedicated to problems and examples for those, including MiniZinc: http://www.hakank.org/minizinc/index.html http://www.hakank.org/minizinc/index.html

placebo 9y ago
Yes, an impressive set of problems solved with an impressive set of solvers. Quite a bit of experience stored on that site. One thing I'm interested to know (as someone with less experience in constraint programming), is when does one employ constraint programming engines like Choco, Gecode, MiniZinc etc, vs. when metaheuristics (such as simulated annealing, genetic algorithms, etc.) are a more practical solution. Is there a rule of thumb regarding the size search space, type of problem etc. ?
- jahewson 9y ago
  Constraint satisfaction is NP-complete and for optimization it’s NP-hard. In theory that means it’s going to be equally hard to determine how many steps solving the problem takes as it is to simply solve the problem. Local search is always going to outperform global search but there’s no guarantee of a solution or an optimal one. So it really depends on your needs and how long you’re prepared to wait. Modern CSP solvers can handle impressively large problems with multiple thousands of clauses (1m+ for SAT), but it really depends on what your constraints look like.
- CJefferson 9y ago
  One easy rule is use CP when One of these are true. You need to know the actual optimal answer (metaheurisitics can never prove they have the optimal). You need all solutions to your problem. Your problem is just true/false, not optimisation, and there is no obvious way to measure the quality of a partial solution (so metaheurisitics will struggle). In general, CP does better on smaller, harder problems.

placebo 9y ago

Yes, an impressive set of problems solved with an impressive set of solvers. Quite a bit of experience stored on that site. One thing I'm interested to know (as someone with less experience in constraint programming), is when does one employ constraint programming engines like Choco, Gecode, MiniZinc etc, vs. when metaheuristics (such as simulated annealing, genetic algorithms, etc.) are a more practical solution. Is there a rule of thumb regarding the size search space, type of problem etc. ?

jahewson 9y ago
Constraint satisfaction is NP-complete and for optimization it’s NP-hard. In theory that means it’s going to be equally hard to determine how many steps solving the problem takes as it is to simply solve the problem. Local search is always going to outperform global search but there’s no guarantee of a solution or an optimal one. So it really depends on your needs and how long you’re prepared to wait. Modern CSP solvers can handle impressively large problems with multiple thousands of clauses (1m+ for SAT), but it really depends on what your constraints look like.
CJefferson 9y ago
One easy rule is use CP when One of these are true. You need to know the actual optimal answer (metaheurisitics can never prove they have the optimal). You need all solutions to your problem. Your problem is just true/false, not optimisation, and there is no obvious way to measure the quality of a partial solution (so metaheurisitics will struggle). In general, CP does better on smaller, harder problems.