What problems have you solved using constraint programming?

Question

I'd like to know about specific problems you - the SO reader - have solved using constraint programming and what constraint logic language you used.

Questions:

• What problems have you used constraint programming to solve?
• What constraint logic language did you use?

I'm looking for first-hand experiences, so please do not answer unless you have that.

Answer 1

I was doing research for 2 years using constraint problems to solve 2d packing problems. Basically arrange 2d shapes in a rectangular shape, with fixed height and infinite width (to minimize this).

At the time, the approach was using both Prolog/Sicstus coinstraint engine as well as C++/Ilog constraint solver.

I also wrote a constraint solver in C# to solve configuration problems, where you have big models but as you pick different options, you get fewer and fewer new options available. While benchmarking this I solved problems such as N-Queens and Golomb Rulers.

Answer 2

I'm not sure if this qualifies as an answer to your question since I'm not a professional (or researcher) in the area, but I have programmed in a couple of constraint programming systems. My object has been more about learning constraint programming and the systems than to solve a specific problem.

The problems has been very diverse: there is a lot of recreational mathematics and puzzles, but also traditional constraint programming problems, such as combinatorial problems as well as (decompositions) of global constraints.

The systems I have used so far are:

• MiniZinc
• Choco (Java)
• JaCoP (Java)
• Comet
• Gecode (C++)
• Gecode/R (Ruby)
• ECLiPSE (Prolog)
• SICStus Prolog
• Tailor/Essence'

For every system I start to learn, I begin with about 17 problems, so for each system there is at least these problems. However, for some systems there is a lot more models e.g. MiniZinc (over 600 models, small and large), Comet, ECLiPSe, and SICStus.

See www.hakank.org/constraint_programming/ for links to the models I've implemented in each system. Also, I blog about constraint programming at "My Constraint Programming Blog" (http://www.hakank.org/constraint_programming_blog/ )

Answer 3

Hitori solver using constraint programing

Answer 4

Hi! In my master's thesis, I used constraint programming for modeling a double auction from a trading system. Then I applied the model for verifying the output of the system in random tests. I actually found a couple of interesting failures! :) .

I created the first model in Gecode, and then I re-wrote it in Choco for a better integration with the random test framework (written in Java + JUnit).

Answer 5

I used a constraint solver to generate directed-random tests for a CPU under development.

It generated semi-random sequences of instructions based on constraints:

• Must-follow constraints based on the ISA (instruction set architecture)
• Weighted constraints particular to the test scenario being targeted (no exceptions, lots of exceptions, etc)

Generating such tests is a difficult problem and I found that a constraint solver was a worthwhile approach. The language used was a proprietary language, part of IBM's Genesys-Pro tool.