Frequently Asked Questions

Gecode/R

Why do I keep getting “RuntimeError: No value is assigned.” when accessing solution values?

Because the variables have not been assigned a single value in the solution. Variables are not necessarily assigned in the solution unless you tell Gecode/R to branch over them. As an example

Gecode.solve do 
  foo_is_an int_var(0..9)
  foo.must < 5
end.foo.domain

returns “0..4” (i.e. foo is not assigned) while

Gecode.solve do 
  foo_is_an int_var(0..9)
  foo.must < 5
  branch_on foo
end.foo.value

returns “0” (foo is assigned 0).

Constraint Programming

What is Constraint Programming?

Constraint programming is a declarative programming paradigm, you describe what kind of solution you want rather than how you want it computed. When using constraint programming you model the problem and then feed that model to the solver. The solver then searches for a solution by exploring the space of all possible assignments while using the constraints in the model to prune parts without having to visit them.

A popular example is sudoku, to solve a sudoku with constraint programming you feed the rules (all numbers in each row must be distinct etc) to the solver, which then searches for a solution satisfying all the constraints.

What Types of Problems are Suitable?

The ideal problems to use constraint programming on are problems that are easy to describe but where the best one can do to solve them is an exhaustive search. Typically NP-hard combinatorial problems.

If there exists an algorithm with polynomial time complexity for the problem then it will have a better worst case complexity. If the algorithm is hard to implement and/or complexity is not that important then constraint programming might still be worth testing/considering.

Won’t it be Slow?

It will always have exponential worst case complexity. However, if the model is good, it can empirically scale better.

The reason is that Gecode is smart when it comes to pruning the search space and will often not have to visit most of it due to taking advantage of the placed constraints.