Searching for Solutions

Mixin#solve! and friends are used to fetch any solution to a formulated problem. Mixin#optimize! and friends are used to fetch the solution that optimizes some value.

Searching for One Solution

Mixin#solve! is used to access one solution to the problem. It destructively updates the model’s variables.

instance = MyModel.new
instance.solve!

The value assigned to a variable is then accessed using IntVar#value. If there does not exist a solution then Gecode::NoSolutionError is raised.

Note that a solution’s variable is not necessarily assigned. Use Mixin#branch_on to ensure that a variable is.

A similar form with blocks if also available through Mixin#solution.

string = instance.solution{ |solution| solution.to_s }

It gives a solution to the block and then returns the result of the block (the model instance is unaffected).

Searching for All Solutions

Mixin#each_solution iterates over all solutions to a problem.

instance.each_solution{ |solution| puts solution.to_s }

Searching for the Optimal Solution

Mixin#optimize! is used to find the optimal solution (where optimality is defined by the user). The method takes a block with two arguments: the model itself and the best solution found so far. The block should then add a constraint that constrains the model to be strictly better than the best solution so far.

Minimizing the value of a variable price is for instance done as follows.

optimal_solution = price_model_instance.optimize! do |model, best_so_far|
  model.price.must < best_so_far.price.value
end

This destructively updates price_model_instance to contain the returned solution. If there is not solution then Gecode::NoSolutionError is raised.

There exist convenience methods, named Mixin#maximize! and Mixin#minimize!, for optimizing single integer variables. The above minimization of the variable price can for instance also be done as follows.

optimal_solution = price_model_instance.minimize! :price

Convenience Methods

There exists handy convenience methods for common operations related to models.

Gecode.solve

Use Gecode.solve to create a model and search for a single solution without having to explicitly define a class.

solution = Gecode.solve do
  # Describe the model.
end

Gecode.minimize and Gecode.maximize

Use Gecode.minimize and Gecode.maximize to create a model and search for a solution that maximizes or minimizes a given variable.

optimal_solution = Gecode.minimize :price do 
  # Describe the model.
end

Limiting Search Time

The amount of time spent by the solver can be limited by specifying a number of milliseconds with the key :time_limit. If a solution can not be found withing the allotted time, then the solver stops and Gecode::SearchAbortedError is raised.

begin
  difficultProblemModel.solve!(:time_limit => 1000)
  puts difficultProblemModel.solution
rescue Gecode::SearchAbortedError
  puts "Sorry, the answer could not be computed within one second."
end

Search Statistics

Mixin#search_stats can be used after a search to obtain various statistics about the search. The most interesting one is the number of failures, which gives an idea of how much searching is needed.