# module Gecode::Mixin

Mixin contains the base functionality needed to formulate problems.

## Formulating problems¶ ↑

Problems are formulated by building a model that represents the problem. A model is a class that mixes in Mixin and uses its functionality to define variables and constraints that describe the problem. Below is an example of a model that formulates the problem of finding a solution to the following equation system.

Equation system:

```x + y = z
x = y - 3
0 <= x,y,z <= 9```

Model:

```class EquationProblem
include Gecode::Mixin

attr :vars

def initialize
x, y, z = @vars = int_var_array(3, 0..9)

(x + y).must == z
x.must == y - 3

branch_on @vars
end
end
```

A model typically consists of three main parts:

Variables

Variables specify how to view the problem. A solution is an assignment of the variables. In the example above we created an array of three integer variables with domains 0..9 and gave it the name `variables`.

There are three types of variables: integer variables (Gecode::IntVar, can be assigned one of many possible integer values), boolean variables (Gecode::BoolVar, can be assigned either true or false) and set variables (Gecode::SetVar, can be assigned a set of integers). Variables of the different types are constructed using int_var, int_var_array, int_var_matrix, bool_var, bool_var_array, bool_var_matrix, set_var, set_var_array and set_var_matrix .

The various variables all have the functionality of Operand and have many properties depending on their type. For instance integer variables have the properties defined in Gecode::Int::IntOperand and enumerations of integer variables (such as the array `variables` we used) have the properties defined in

Constraints

Constraints are placed on the variables to ensure that a valid assignment of the variables must also be a solution. In the example above we constrained the variables so that all equations were satisfied (which is exactly when we have found a solution).

The various constraints that can be placed on the various kinds of operands are found in the respective constraint receivers. For instance, the constraints that can be placed on integer operands are found in Gecode::Int::IntConstraintReceiver and the constraints that can be placed on enumerations of integer operands are found in Gecode::IntEnum::IntEnumConstraintReceiver .

Branching

“branch_on variables” in the example tells Gecode that it should explore the search space until it has assigned `variables` (or exhausted the search space). It also tells Gecode in what order the search space should be explore, which can have a big effect on the search performance. See branch_on for details.

## Finding solutions¶ ↑

Solutions to a formulated problem are found are found by using methods such as solve!, solution, each_solution . If one wants to find a solution that optimizes a certain quantity (i.e. maximizes a certain variable) then one should have a look at maximize!, minimize! and optimize! .

The first solution to the example above could for instance be found using

```puts EquationProblem.new.solve!.vars.values.join(', ')
```

which would find the first solution to the problem, access the assigned values of `variables` and print them (in order x, y, z).

## Shorter ways of formulating problems¶ ↑

Problems can also be formulated without defining a new class by using Gecode#solve et al.

Additionally one can use “foo_is_an …” to create an accessor of name foo, without having to use instance variables. The above problem becomes

```class EquationProblem
include Gecode::Mixin

def initialize
x, y, z = vars_is_an int_var_array(3, 0..9)

(x + y).must == z
x.must == y - 3

branch_on vars
end
end
```

### Constants

LARGEST_INT_DOMAIN

The largest possible domain for an integer variable.

LARGEST_SET_BOUND

The largest possible bound for a set variable.

MAX_INT

The largest integer allowed in the domain of an integer variable.

MIN_INT

The smallest integer allowed in the domain of an integer variable.

NON_NEGATIVE_INT_DOMAIN

The largest possible domain, without negative integers, for an integer variable.

SET_MAX_INT

The largest integer allowed in the domain of a set variable.

SET_MIN_INT

The smallest integer allowed in the domain of a set variable.

### Public Instance Methods

any(*regexps) click to toggle source

Matches any of the specified `regexps`.

```# File lib/gecoder/interface/constraints/extensional_regexp.rb, line 49
def any(*regexps)
regexps.inject(Gecode::Raw::REG.new) do |result, regexp|
result | Util::Extensional.parse_regexp(regexp)
end
end```
at_least_once(regexp) click to toggle source

Matches `regexp` repeated at least one time (i.e. like ‘+’ in normal regexps). Produces the same result as calling

```repeat(regexp, 1)
```
```# File lib/gecoder/interface/constraints/extensional_regexp.rb, line 44
def at_least_once(regexp)
repeat(regexp, 1)
end```
at_most_once(regexp) click to toggle source

Matches `regexp` repeated zero or one time (i.e. like ‘?’ in normal regexps). Produces the same result as calling

```repeat(regexp, 0, 1)
```
```# File lib/gecoder/interface/constraints/extensional_regexp.rb, line 36
def at_most_once(regexp)
repeat(regexp, 0, 1)
end```
bool_var() click to toggle source

Creates a new boolean variable.

```# File lib/gecoder/interface/mixin.rb, line 168
def bool_var
BoolVar.new(self, variable_creation_space.new_bool_var)
end```
bool_var_array(count) click to toggle source

Creates an array containing the specified number of boolean variables.

```# File lib/gecoder/interface/mixin.rb, line 173
def bool_var_array(count)
build_var_array(count) do
BoolVar.new(self, variable_creation_space.new_bool_var)
end
end```
bool_var_matrix(row_count, col_count) click to toggle source

Creates a matrix containing the specified number rows and columns of boolean variables.

```# File lib/gecoder/interface/mixin.rb, line 181
def bool_var_matrix(row_count, col_count)
build_var_matrix(row_count, col_count) do
BoolVar.new(self, variable_creation_space.new_bool_var)
end
end```
branch_on(variables, options = {}) click to toggle source

Specifies which variables that should be branched on (given as an enum of operands or as a single operand). One can optionally also select which of the variables that should be used first with the :variable option and which value in that variable’s domain that should be used with the :value option. If nothing is specified then :variable uses :none and value uses :min.

The following values can be used with :variable for integer and boolean enums:

:none

The first unassigned variable.

:smallest_min

The one with the smallest minimum.

:largest_min

The one with the largest minimum.

:smallest_max

The one with the smallest maximum.

:largest_max

The one with the largest maximum.

:smallest_size

The one with the smallest size.

:largest_size

The one with the larges size.

:smallest_degree

The one with the smallest degree. The degree of a variable is defined as the number of dependant propagators. In case of ties, choose the variable with smallest domain.

:largest_degree

The one with the largest degree. The degree of a variable is defined as the number of dependant propagators. In case of ties, choose the variable with smallest domain.

:smallest_min_regret

The one with the smallest min-regret. The min-regret of a variable is the difference between the smallest and second-smallest value still in the domain.

:largest_min_regret

The one with the largest min-regret. The min-regret of a variable is the difference between the smallest and second-smallest value still in the domain.

:smallest_max_regret

The one with the smallest max-regret The max-regret of a variable is the difference between the largest and second-largest value still in the domain.

:largest_max_regret

The one with the largest max-regret. The max-regret of a variable is the difference between the largest and second-largest value still in the domain.

The following values can be used with :value for integer and boolean enums:

:min

Selects the smallest value.

:med

Select the median value.

:max

Selects the largest vale

:split_min

Selects the lower half of the domain.

:split_max

Selects the upper half of the domain.

The following values can be used with :variable for set enums:

:none

The first unassigned set.

:smallest_cardinality

The one with the smallest cardinality.

:largest_cardinality

The one with the largest cardinality.

:smallest_unknown

The one with the smallest number of unknown elements

:largest_unknown

The one with the largest number of unknown elements

The following values can be used with :value set enums:

:min

Selects the smallest value in the unknown part of the set.

:max

Selects the largest value in the unknown part of the set.

```# File lib/gecoder/interface/branch.rb, line 64
def branch_on(variables, options = {})
if variables.respond_to?(:to_int_var) or
variables.respond_to?(:to_bool_var) or
variables.respond_to?(:to_set_var)
variables = wrap_enum [variables]
end

if variables.respond_to? :to_int_enum
Constants::BRANCH_INT_VAR_CONSTANTS,
Constants::BRANCH_INT_VALUE_CONSTANTS)
elsif variables.respond_to? :to_bool_enum
Constants::BRANCH_INT_VAR_CONSTANTS,
Constants::BRANCH_INT_VALUE_CONSTANTS)
elsif variables.respond_to? :to_set_enum
Constants::BRANCH_SET_VAR_CONSTANTS,
Constants::BRANCH_SET_VALUE_CONSTANTS)
else
raise TypeError, "Unknown type of variable enum #{variables.class}."
end
end```
combined_method_missing(*args) click to toggle source
```# File lib/gecoder/interface/mixin.rb, line 335
def combined_method_missing(*args)
begin
mixin_method_missing(*args)
rescue NoMethodError => e
mixee_method_missing(*args)
end
end```
each_solution() { |self| ... } click to toggle source

Yields each solution that the model has.

```# File lib/gecoder/interface/search.rb, line 63
def each_solution(&block)
dfs = dfs_engine
next_solution = nil
while not (next_solution = dfs.next).nil?
self.active_space = next_solution
@gecoder_mixin_statistics = dfs.statistics
yield self
end
self.reset!
end```
int_var(domain = LARGEST_INT_DOMAIN) click to toggle source

Creates a new integer variable with the specified domain. The domain can either be a range, a single element, or an enumeration of elements. If no domain is specified then the largest possible domain is used.

```# File lib/gecoder/interface/mixin.rb, line 140
def int_var(domain = LARGEST_INT_DOMAIN)
args = domain_arguments(domain)
IntVar.new(self, variable_creation_space.new_int_var(*args))
end```
int_var_array(count, domain = LARGEST_INT_DOMAIN) click to toggle source

Creates an array containing the specified number of integer variables with the specified domain. The domain can either be a range, a single element, or an enumeration of elements. If no domain is specified then the largest possible domain is used.

```# File lib/gecoder/interface/mixin.rb, line 149
def int_var_array(count, domain = LARGEST_INT_DOMAIN)
args = domain_arguments(domain)
build_var_array(count) do
IntVar.new(self, variable_creation_space.new_int_var(*args))
end
end```
int_var_matrix(row_count, col_count, domain = LARGEST_INT_DOMAIN) click to toggle source

Creates a matrix containing the specified number rows and columns of integer variables with the specified domain. The domain can either be a range, a single element, or an enumeration of elements. If no domain is specified then the largest possible domain is used.

```# File lib/gecoder/interface/mixin.rb, line 160
def int_var_matrix(row_count, col_count, domain = LARGEST_INT_DOMAIN)
args = domain_arguments(domain)
build_var_matrix(row_count, col_count) do
IntVar.new(self, variable_creation_space.new_int_var(*args))
end
end```
maximize!(var) click to toggle source

Finds the solution that maximizes a given integer variable. The name of the method that accesses the variable from the model should be given. To for instance maximize a variable named “profit”, that’s accessible through the model, one would use the following.

```model.maximize! :profit
```

Raises Gecode::NoSolutionError if no solution can be found.

```# File lib/gecoder/interface/search.rb, line 154
def maximize!(var)
variable = self.method(var).call
unless variable.kind_of? Gecode::IntVar
raise ArgumentError.new("Expected integer variable, got #{variable.class}.")
end

optimize! do |model, best_so_far|
model.method(var).call.must > best_so_far.method(var).call.value
end
end```
method_missing(method, *args) click to toggle source

Wraps method missing to handle foo_is_a and foo_is_an .

“<variable_name>_is_a <variable>” or “<variable_name>_is_an <variable>”, # replacing “<variable_name>” with the variable’s name and “<variable>” with the variable, adds an instance variable and accessor with the specified name.

The method also returns the variable given.

#### Example¶ ↑

```# Add an instance variable and accessor named "foo" that return
# the integer variable.
foo_is_an int_var(0..9)

# Add an instance variable and accessor named "bar" that return
# the boolean variable array.
bar_is_a bool_var_array(2)
```
```# File lib/gecoder/interface/mixin.rb, line 296
def method_missing(method, *args)
name = method.to_s
if name =~ /._is_an?\$/
name.sub!(/_is_an?\$/, '')
unless args.size == 1
raise ArgumentError,
"Wrong number of argmuments (#{args.size} for 1)."
end
if respond_to? name
raise ArgumentError, "Method with name #{name} already exists."
end
if instance_variable_defined? "@#{name}"
raise ArgumentError,
"Instance variable with name @#{name} already exists."
end

# We use the meta class to avoid defining the variable in all
# other instances of the class.
eval <<-"end_eval"
@#{name} = args.first
class <<self
attr :#{name}
end
end_eval
return args.first
else
pre_gecoder_method_missing(method, *args)
end
end```
minimize!(var) click to toggle source

Finds the solution that minimizes a given integer variable. The name of the method that accesses the variable from the model should be given. To for instance minimize a variable named “cost”, that’s accessible through the model, one would use the following.

```model.minimize! :cost
```

Raises Gecode::NoSolutionError if no solution can be found.

```# File lib/gecoder/interface/search.rb, line 173
def minimize!(var)
variable = self.method(var).call
unless variable.kind_of? Gecode::IntVar
raise ArgumentError.new("Expected integer variable, got #{variable.class}.")
end

optimize! do |model, best_so_far|
model.method(var).call.must < best_so_far.method(var).call.value
end
end```
optimize!() { |self, self| ... } click to toggle source

Finds the optimal solution. Optimality is defined by the provided block which is given two parameters, the model and the best solution found so far to the problem. The block should constrain the model so that that only “better” solutions can be new solutions. For instance if one wants to optimize a variable named price (accessible from the model) to be as low as possible then one should write the following.

```model.optimize! do |model, best_so_far|
model.price.must < best_so_far.price.value
end
```

Raises Gecode::NoSolutionError if no solution can be found.

```# File lib/gecoder/interface/search.rb, line 108
def optimize!(&block)
# Execute constraints.
perform_queued_gecode_interactions

# Set the method used for constrain calls by the BAB-search.
Mixin.constrain_proc = lambda do |home_space, best_space|
self.active_space = best_space
@gecoder_mixin_variable_creation_space = home_space
yield(self, self)
self.active_space = home_space
@gecoder_mixin_variable_creation_space = nil

perform_queued_gecode_interactions
end

# Perform the search.
options = Gecode::Raw::Search::Options.new
options.c_d = Gecode::Raw::Search::Config::MINIMAL_DISTANCE
options.stop = nil
bab = Gecode::Raw::BAB.new(selected_space, options)

result = nil
previous_solution = nil
until (previous_solution = bab.next).nil?
result = previous_solution
end
@gecoder_mixin_statistics = bab.statistics

# Reset the method used constrain calls and return the result.
Mixin.constrain_proc = nil
raise Gecode::NoSolutionError if result.nil?

# Switch to the result.
self.active_space = result
return self
end```
repeat(regexp, at_least = nil, at_most = nil) click to toggle source

Specifies an integer regexp that matches `regexp` repeated between `at_least` and `at_most` times (inclusive). If `at_most` is omitted then no upper bound is placed. If both `at_least` and `at_most` are omitted then no bounds are placed.

See IntEnum::Extensional::RegexpConstraint for the allowed syntax of `regexp`.

```# File lib/gecoder/interface/constraints/extensional_regexp.rb, line 10
def repeat(regexp, at_least = nil, at_most = nil)
unless at_least.nil? or at_least.kind_of? Fixnum
raise TypeError,
"Expected the at_least argument to be a Fixnum, got #{at_least.class}"
end
unless at_most.nil? or at_most.kind_of?(Fixnum)
raise TypeError,
"Expected the at_most argument to be a Fixnum, got #{at_most.class}"
end

reg = Util::Extensional.parse_regexp regexp
if at_most.nil?
if at_least.nil?
reg.send '*'
else
reg.send('()', at_least)
end
else
reg.send('()', at_least, at_most)
end
end```
reset!() click to toggle source

Returns to the original state, before any search was made (but propagation might have been performed). Returns the reset model.

```# File lib/gecoder/interface/search.rb, line 42
def reset!
self.active_space = base_space
@gecoder_mixin_statistics = nil
return self
end```
search_stats() click to toggle source

Returns search statistics providing various information from Gecode about the search that resulted in the model’s current variable state. If the model’s variables have not undergone any search then nil is returned. The statistics is a hash with the following keys:

:propagations

The number of propagation steps performed.

:failures

The number of failed nodes in the search tree.

:clones

The number of clones created.

:commits

The number of commit operations performed.

:memory

The peak memory allocated to Gecode.

```# File lib/gecoder/interface/search.rb, line 83
def search_stats
return nil if @gecoder_mixin_statistics.nil?

return {
:propagations => @gecoder_mixin_statistics.propagate,
:failures     => @gecoder_mixin_statistics.fail,
:clones       => @gecoder_mixin_statistics.clone,
:commits      => @gecoder_mixin_statistics.commit,
:memory       => @gecoder_mixin_statistics.memory
}
end```
set_var(glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) click to toggle source

Creates a set variable with the specified domain for greatest lower bound and least upper bound (specified as either a fixnum, range or enum). If no bounds are specified then the empty set is used as greatest lower bound and the largest possible set as least upper bound.

A range for the allowed cardinality of the set can also be specified, if none is specified, or nil is given, then the default range (anything) will be used. If only a single Fixnum is specified as cardinality_range then it’s used as lower bound.

```# File lib/gecoder/interface/mixin.rb, line 196
def set_var(glb_domain = [], lub_domain = LARGEST_SET_BOUND,
cardinality_range = nil)
args = set_bounds_to_parameters(glb_domain, lub_domain, cardinality_range)
SetVar.new(self, variable_creation_space.new_set_var(*args))
end```
set_var_array(count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) click to toggle source

Creates an array containing the specified number of set variables. The parameters beyond count are the same as for set_var .

```# File lib/gecoder/interface/mixin.rb, line 204
def set_var_array(count, glb_domain = [], lub_domain = LARGEST_SET_BOUND,
cardinality_range = nil)
args = set_bounds_to_parameters(glb_domain, lub_domain, cardinality_range)
build_var_array(count) do
SetVar.new(self, variable_creation_space.new_set_var(*args))
end
end```
set_var_matrix(row_count, col_count, glb_domain = [], lub_domain = LARGEST_SET_BOUND, cardinality_range = nil) click to toggle source

Creates a matrix containing the specified number of rows and columns filled with set variables. The parameters beyond row and column counts are the same as for set_var .

```# File lib/gecoder/interface/mixin.rb, line 215
def set_var_matrix(row_count, col_count, glb_domain = [],
lub_domain = LARGEST_SET_BOUND, cardinality_range = nil)
args = set_bounds_to_parameters(glb_domain, lub_domain, cardinality_range)
build_var_matrix(row_count, col_count) do
SetVar.new(self, variable_creation_space.new_set_var(*args))
end
end```
solution() { |solution| ... } click to toggle source

Yields the first solution (if any) to the block. If no solution is found then the block is not used. Returns the result of the block (nil in case the block wasn’t run).

```# File lib/gecoder/interface/search.rb, line 51
def solution(&block)
begin
solution = self.solve!
res = yield solution
self.reset!
return res
rescue Gecode::NoSolutionError
return nil
end
end```
solve!(options = {}) click to toggle source

Finds the first solution to the modelled problem and updates the variables to that solution. The found solution is also returned. Raises Gecode::NoSolutionError if no solution can be found.

The following options can be specified in a hash with symbols as keys when calling the method:

:time_limit

The number of milliseconds that the solver should be allowed to use when searching for a solution. If it can not find a solution fast enough, then Gecode::SearchAbortedError is raised.

```# File lib/gecoder/interface/search.rb, line 30
def solve!(options = {})
dfs = dfs_engine(options)
space = dfs.next
@gecoder_mixin_statistics = dfs.statistics
raise Gecode::SearchAbortedError if dfs.stopped
raise Gecode::NoSolutionError if space.nil?
self.active_space = space
return self
end```
wrap_enum(enum) click to toggle source

Wraps a custom enumerable so that constraints can be specified using it. The argument is altered and returned.

```# File lib/gecoder/interface/enum_wrapper.rb, line 5
def wrap_enum(enum)
unless enum.kind_of? Enumerable
raise TypeError, 'Only enumerables can be wrapped.'
end
if enum.kind_of? Gecode::EnumMethods
raise ArgumentError, 'The enumration is already wrapped.'
end
elements = enum.to_a
if elements.empty?
raise ArgumentError, 'Enumerable must not be empty.'
end

if elements.all?{ |var| var.respond_to? :to_int_var }
elements.map!{ |var| var.to_int_var }
class <<enum
include Gecode::IntEnumMethods
end
elsif elements.all?{ |var| var.respond_to? :to_bool_var }
elements.map!{ |var| var.to_bool_var }
class <<enum
include Gecode::BoolEnumMethods
end
elsif elements.all?{ |var| var.respond_to? :to_set_var }
elements.map!{ |var| var.to_set_var }
class <<enum
include Gecode::SetEnumMethods
end
elsif elements.all?{ |var| var.kind_of? Fixnum }
class <<enum
end
else
raise TypeError, "Enumerable doesn't contain operands #{enum.inspect}."
end

enum.model = self
return enum
end```

### Public Class Methods

included(mod) click to toggle source
```# File lib/gecoder/interface/mixin.rb, line 275
def self.included(mod)
mod.class_eval do
alias_method :pre_gecoder_method_missing, :method_missing
# Wraps method missing to handle #foo_is_a and #foo_is_an .
#
# "<variable_name>_is_a <variable>" or "<variable_name>_is_an
# <variable>", # replacing "<variable_name>" with the variable's
# name and "<variable>" with the variable, adds an instance
# variable and accessor with the specified name.
#
# The method also returns the variable given.
#
# ==== Example
#
#   # Add an instance variable and accessor named "foo" that return
#   # the integer variable.
#   foo_is_an int_var(0..9)
#
#   # Add an instance variable and accessor named "bar" that return
#   # the boolean variable array.
#   bar_is_a bool_var_array(2)
def method_missing(method, *args)
name = method.to_s
if name =~ /._is_an?\$/
name.sub!(/_is_an?\$/, '')
unless args.size == 1
raise ArgumentError,
"Wrong number of argmuments (#{args.size} for 1)."
end
if respond_to? name
raise ArgumentError, "Method with name #{name} already exists."
end
if instance_variable_defined? "@#{name}"
raise ArgumentError,
"Instance variable with name @#{name} already exists."
end

# We use the meta class to avoid defining the variable in all
# other instances of the class.
eval <<-"end_eval"
@#{name} = args.first
class <<self
attr :#{name}
end
end_eval
return args.first
else
pre_gecoder_method_missing(method, *args)
end
end
alias_method :mixin_method_missing, :method_missing

if method == :method_missing && !@redefining_method_missing
# The class that is mixing in the mixin redefined method
# missing. Redefine method missing again to combine the two
# definitions.
@redefining_method_missing = true
class_eval do
alias_method :mixee_method_missing, :method_missing
def combined_method_missing(*args)
begin
mixin_method_missing(*args)
rescue NoMethodError => e
mixee_method_missing(*args)
end
end
alias_method :method_missing, :combined_method_missing
end
end
end
end
end```
```# File lib/gecoder/interface/mixin.rb, line 327
if method == :method_missing && !@redefining_method_missing
# The class that is mixing in the mixin redefined method
# missing. Redefine method missing again to combine the two
# definitions.
@redefining_method_missing = true
class_eval do
alias_method :mixee_method_missing, :method_missing
def combined_method_missing(*args)
begin
mixin_method_missing(*args)
rescue NoMethodError => e
mixee_method_missing(*args)
end
end
alias_method :method_missing, :combined_method_missing
end
end
end```