++ed by:
Toshimitsu FUJIWARA
and 1 contributors

# NAME

Algorithm::CP::IZ - Perl interface for iZ-C library

# SYNOPSIS

``````  use Algorithm::CP::IZ;

my \$iz = Algorithm::CP::IZ->new();

my \$v1 = \$iz->create_int(1, 9);
my \$v2 = \$iz->create_int(1, 9);
my \$rc = \$iz->search([\$v1, \$v2]);

if (\$rc) {
print "ok\n";
print "v1 = ", \$v1->value, "\n";
print "v2 = ", \$v2->value, "\n";
}
else {
print "fail\n";
}``````

# DESCRIPTION

Algorithm::CP::IZ is a simple interface of iZ-C constraint programming library.

Functions declared in iz.h are mapped to:

methods of Algorithm::CP::IZ

initialize, variable constructor, most of constraints and search related functions

methods of Algorithm::CP::IZ::Int

accessors of variable attributes and some relationship constraints

Please refer to iZ-C reference manual to see specific meaning of methods.

## SIMPLE CASE

In most simple case, this library will be used like following steps:

``````  # initialize
use Algorithm::CP::IZ;
my \$iz = Algorithm::CP::IZ->new();

# construct variables
my \$v1 = \$iz->create_int(1, 9);
my \$v2 = \$iz->create_int(1, 9);

# add constraints ("v1 + v2 = 12" in this case)

# search solution
my \$rc = \$iz->search([\$v1, \$v2]);

# you may get "v1 = 3, v2 = 9"
print "v1 = \$v1, v2 = \$v2\n";``````

# CONSTRUCTOR

new

Initialize iZ-C library (cs_init is called). For limitation of iZ-C, living instance of Algorithm::CP::IZ must be only one per process.

# METHODS

create_int(INT)

Create an instance of Algorithm::CP::IZ::Int. Its domain contains INT.

create_int(VALUES [, NAME])

Create an instance of Algorithm::CP::IZ::Int. Its domain contains values specified by VALUES(arrayref).

create_int(MIN, MAX, [, NAME])

Create an instance of Algorithm::CP::IZ::Int. Its domain is {MIN..MAX}.

search(VARIABLES [, PARAMS])

Try to instantiate all VARIABLES(arrayref).

PARAMS will be hashref containning following keys.

FindFreeVar

FindFreeVar specifies variable selection strategy. Choose constants from Algorithm::CP::IZ::FindFreeVar or specify your own function as coderef here.

Most simple function will be following. (select from first)

``````    sub simple_find_free_var{
my \$array = shift; # VARIABLES is in parameter
my \$n = scalar @\$array;

for my \$i (0..\$n-1) {
return \$i if (\$array->[\$i]->is_free);
}

return -1; # no free variable
};``````
Criteria

Criteria specifies value selection strategy. Specify your own function as coderef here.

``````    sub sample_criteria {
# position in VARIABLES, and candidate value
my (\$index, \$val) = @_;

# first value used in search is
# minimum value returned by criteria.
return \$val;
};``````

(If ValueSelector is specified, this parameter is ignored.)

MaxFail

Upper limit of fail count while searching solutions.

ValueSelectors

Arrayref of Algorithm::CP::IZ::ValueSelector instances created via get_value_selector or create_value_selector_simple method.

(If ValueSelector is specified, this parameter is ignored.)

MaxFailFunc

CodeRef of subroutine which returns maxfail for restart.

NoGoodSet

A Algorithm::CP::IZ::NoGoodSet instance which collects NoGoods.

Notify

``````    search_start
search_end
before_value_selection
after_value_selection
enter
leave
found``````

if OBJECT is a object, method having notification name will be called.

if OBJECT is a hashref, notification name must be a key of hash and value must be a coderef.

Returns 1 (success) or 0 (fail).

find_all(VARIABLES, CALLBACK [, PARAMS])

Find all solutions. CALLBACK(coderef) is called for each solution. (First parameter of CALLBACK is VARIABLE)

``````    # this callback collects all solutions in @r
my @r;
sub callback {
my \$var_array = shift;
push(@r, [map { \$_->value } @\$var_array]);
};``````

PARAMS will be hashref containning following keys.

FindFreeVar

Same as search method.

Returns 1 (success) or 0 (fail).

get_nb_fails

Returns fail count while searching solution.

get_nb_choice_points

Returns choice count while searching solution.

save_context

Save current status of variables and constraints.

``````  my \$v1 = \$iz->create_int(1, 9);
\$iz->save_context;    # current status is saved.
\$v1->Le(5);           # \$v1 is {1..5}
\$iz->restore_context; # \$v1 is restored to {1..9}``````

Returns integer which will be used for restore_context_until.

restore_context

Restore status of variables and constraints to last point which 'save_context' is called.

restore_context_until(LABEL)

Restore status of variables and constraints to point of label which 'save_context' returns.

restore_all

Restore status of variables and constraints to point of first 'save_context' call.

forget_save_context

Last save_context point is forgotten by calling this function.

forgest_save_context_until(LABEL)

save_context points until LABEL are forgotten by calling this function.

Cancel running search from other thread or signal handler. Context will be restored using restore_context_until if needed.

backtrack(VAR, INDEX, CALLBACK)

Set a callback function which will be called when context is restored to current status.

VAR is an instance of Algorithm::CP::IZ::Int.

INDEX is an integer value.

CALLBACK is a coderef which takes parameters like:

``````  sub callback {
# \$var = VAR, \$index = INDEX
my (\$var, \$index) = @_;
}``````
event_all_known(VARIABLES, CALLBACK, EXTRA)

Set a callback function which will be called when all variables in VARIABLES are instantiated.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

CALLBACK is a coderef and takes parameters and must return like:

``````  sub callback {
# \$variables and \$extra are same as parameter.
my (\$variables, \$extra) = @_;

# return 1(success) or 0(fail)
return 1;
}``````

EXTRA is a just a data passed to callbeck as parameter (it can be anything).

event_known(VARIABLES, CALLBACK, EXTRA)

Set a callback function which will be called when any variable in VARIABLES is instantiated.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

CALLBACK is a coderef and takes parameters and must return like:

``````  sub callback {
# \$val is instantited now.
# \$index is position in \$variables.
# \$variables and \$extra are same as parameter.
my (\$val, \$index, \$variables, \$extra) = @_;

# return 1(success) or 0(fail)
return 1;
}``````

EXTRA is a just a data passed to callbeck as parameter (it can be anything).

event_new_min(VARIABLES, CALLBACK, EXTRA)

Set a callback function which will be called when lower bound of any variable in VARIABLES is changed.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

CALLBACK is a coderef and takes parameters and must return like:

``````  sub callback {
# minimum value of \$var is changed from \$old_min.
# \$var is same as \$variables[\$index].
# \$variables and \$extra are same as parameter.
my (\$var, \$index, \$old_min, \$variables, \$extra) = @_;

# return 1(success) or 0(fail)
return 1;
}``````

EXTRA is a just a data passed to callbeck as parameter (it can be anything).

event_new_max(VARIABLES, CALLBACK, EXTRA)

Set a callback function which will be called when upper bound of any variable in VARIABLES is changed.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

CALLBACK is a coderef and takes parameters and must return like:

``````  sub callback {
# maximum value of \$var is changed from \$old_max.
# \$var is same as \$variables[\$index].
# \$variables and \$extra are same as parameter.
my (\$var, \$index, \$old_max, \$variables, \$extra) = @_;

# return 1(success) or 0(fail)
return 1;
}``````

EXTRA is a just a data passed to callbeck as parameter (it can be anything).

event_neq(VARIABLES, CALLBACK, EXTRA)

Set a callback function which will be called when value of any variable is removed in VARIABLES is changed.

VARIABLES is an arrayref contains instances Algorithm::CP::IZ::Int.

CALLBACK is a coderef and takes parameters and must return like:

``````  sub callback {
# \$val is removed from \$var.
# \$var is same as \$variables[\$index].
# \$variables and \$extra are same as parameter.
my (\$var, \$index, \$val, \$variables, \$extra) = @_;

# return 1(success) or 0(fail)
return 1;
}``````

EXTRA is a just a data passed to callbeck as parameter (it can be anything).

get_version

Returns version string like "3.5.0". undef will be returned if getVersion() is not supported in iZ-C (old version).

get_value_selector(ID)

Get built-in value selector (instance of Algorithm::CP::IZ::ValueSelector) specifed by ID. ID must be selected from following constants defined in package Algorithm::CP::IZ.

CS_VALUE_SELECTOR_MIN_TO_MAX
CS_VALUE_SELECTOR_MAX_TO_MIN
CS_VALUE_SELECTOR_LOWER_AND_UPPER
CS_VALUE_SELECTOR_UPPER_AND_LOWER
CS_VALUE_SELECTOR_MEDIAN_AND_REST

(These values are exported by Algorithm::CP::IZ and can be imported using tag 'value_selector')

Returned object will be used as a parameter ValueSelectors when calling "search" method.

``````  use Algorithm::CP::IZ qw(:value_selector);
my \$vs = \$iz->get_value_selector(CS_VALUE_SELECTOR_MIN_TO_MAX);

my \$v1 = \$iz->create_int(1, 9);
my \$v2 = \$iz->create_int(1, 9);
my \$rc = \$iz->search([\$v1, \$v2], {
ValueSelectors => [ \$vs, \$vs ],
});``````
create_value_selector_simple(CLASS_NAME)

Create user defined value-seelctor defined by class named CLASS_NAME. This class must have constructor named "new" and method namaed "next".

``````  use Algorithm::CP::IZ qw(:value_selector);

package VSSample1;
sub new {
my \$class = shift;
my (\$v, \$index) = @_;

my \$self = {
_pos => 0,
};
bless \$self, \$class;
}

sub next {
my \$self = shift;
my (\$v, \$index) = @_;

my \$pos = \$self->{_pos};
my \$domain = \$v->domain;

# return empty after enumerate all values
return if (\$pos >= @\$domain);

my @ret = (CS_VALUE_SELECTION_EQ, \$domain->[\$pos]);
\$self->{_pos} = ++\$pos;

# return pair of (CS_VALUE_SELECTION_*, value)
return @ret;
}

my \$v1 = \$iz->create_int(1, 9);
my \$v2 = \$iz->create_int(1, 9);
my \$vs = \$iz->create_value_selector_simple("VSSample1");
my \$rc = \$iz->search([\$v1, \$v2], {
ValueSelectors => [ \$vs, \$vs ],
});``````
create_no_good_set(VARIABLES, PRE_FILTER, MAX_NO_GOOD, EXT)

Create an instance of Algorithm::CP::IZ::NoGoodSet. Returned object will be used as a parameter NoGoodSet when calling "search" method.

# METHODS (Constraints)

Create an instance of Algorithm::CP::IZ::Int constrainted to be:

``  Created_instance  = VAR1 + VAR2 + ....``
Mul(VAR1, VAR2 [, VAR3....])

Create an instance of Algorithm::CP::IZ::Int constrainted to be:

``  Created_instance = VAR1 * VAR2 * ....``
Sub(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int constrainted to be:

``  Created_instance = VAR1 - VAR2``
Div(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int constrainted to be:

``  Created_instance = VAR1 / VAR2``
ScalProd(VARIABLES, COEFFICIENTS)

Create an instance of Algorithm::CP::IZ::Int constrainted to be:

``  Created_instance = COEFFICIENTS[0]*VARIABLES[0] + COEFFICIENTS[1]*VARIABLES[1] + ...``

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int, and COEFFICIENTS is an arreyref contains integer values.

AllNeq(VARIABLES)

Constraint all variables in VARIABLES to be different each other.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

Returns 1 (success) or 0 (fail).

Sigma(VARIABLES)

Create an Algorithm::CP::IZ::Int instance constrainted to be:

``  Created_instance = VARIABLES[0] + VARIABLES[1] + ...``

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

Abs(VAR)

Create an instance of Algorithm::CP::IZ::Int constrainted to be:

``  Created_instance = abs(VAR)``
Min(VARIABLES)

Create an instance of Algorithm::CP::IZ::Int constrainted to be:

``  Created_value = minimum value of (VARIABLES[0], VARIABLES[1], ...)``

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

Max(VARIABLES)

Create an instance of Algorithm::CP::IZ::Int to be:

``  Created_instance = maximum value of (VARIABLES[0], VARIABLES[1], ...)``

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

IfEq(VAR1, VAR2, VAL1, VAL2)

Constraint VAR1 and VAR2 to be:

``````  VAR1 is instantiated to VAL1 and VAR2 is instantiated to VAL2.
VAR2 is instantiated to VAL2 and VAR1 is instantiated to VAL1.``````

Returns 1 (success) or 0 (fail).

IfNeq(VAR1, VAR2, VAL1, VAL2)

Constraint VAR1 and VAR2 to be:

``  pair (VAR1, VAR2) != pair (VAL1, VAL2)``

Returns 1 (success) or 0 (fail).

OccurDomain(VAL, VARIABLES)

Create instance of Algorithm::CP::IZ::Int represents count of VAL in VARIABLES.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

OccurConstraints(VAR, VAL, VARIABLES)

Constraint VAR to represent count of VAL in VARIABLES.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

Returns 1 (success) or 0 (fail).

Index(VARIABLES, VAL)

Create an instance of Algorithm::CP::IZ::Int represents position of VAL in VARIABLES.

``  VAL = VARIABLES[CREATED]``

VARIABLES is an arrayref contains instances Algorithm::CP::IZ::Int.

Element(VAR, VALUES)

Create an instance of Algorithm::CP::IZ::Int represents a value at VAR in VALUES. This relation is:

``  Created_instance = VALUES[VAR]``

VALUES is an arrayref contains integer values.

VarElement(VAR, VARIABLES)

Create an instance of Algorithm::CP::IZ::Int represents a value at VAR in VARIABLES. This relation is:

``  Created_instance = VARIABLES[VAR]``

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

VarElementRange(VAR, VARIABLES)

Create an instance of Algorithm::CP::IZ::Int represents a value at VAR in VARIABLES. This relation is:

``  Created_instance = VARIABLES[VAR]``

In contrast to VarElement, constraint propagation for variables in VARIABLES will occur only when upper or lower bound is changed.

VARIABLES is an arrayref contains instances of Algorithm::CP::IZ::Int.

Cumulative(START_VARS, DURATION_VARS, RESOUCE_VARS, LIMIT_VAR)

Constraint variables as "Cumulative".

START_VARS, DURATION_VARS and RESOUCE_VARS are an arrayref contains instances of Algorithm::CP::IZ::Int and LIMIT_VAR is an instance of Algorithm::CP::IZ::Int.

Disjunctive(START_VARS, DURATION_VARS)

Constraint variables as "Disjunctive".

START_VARS and DURATION_VARS are an arrayref contains instances of Algorithm::CP::IZ::Int.

Regular(VARIABLES, TRANSITION_TABLE, Q0, F_VALUES)

Constraint VARIABLES to be input sequence accepted by DFA defined by TRANSITION_TABLE, Q0 and F_VALUES.

TRANSITION_TABLE is an arrayref of arrayref, and each value TRANSITION_TABLE->[q]->[s] defines next state (index of TRANSITION_TABLE) at input s (index of TRANSITION_TABLE->[q]).

Q0 is initial state of DFA.

F_VALUES is an arrayref of acceptable states of DFA.

ReifEq(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int represents state of VAR1 == VAR2. Created variable will be instantiated to 1 when VAR1 == VAR2 otherwise to 0.

ReifNeq(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int represents state of VAR1 != VAR2. Created variable will be instantiated to 1 when VAR1 != VAR2 otherwise to 0.

ReifLt(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int represents state of VAR1 < VAR2. Created variable will be instantiated to 1 when VAR1 < VAR2 otherwise to 0.

ReifLe(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int represents state of VAR1 <= VAR2. Created variable will be instantiated to 1 when VAR1 <= VAR2 otherwise to 0.

ReifGt(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int represents state of VAR1 > VAR2. Created variable will be instantiated to 1 when VAR1 > VAR2 otherwise to 0.

ReifGe(VAR1, VAR2)

Create an instance of Algorithm::CP::IZ::Int represents state of VAR1 >= VAR2. Created variable will be instantiated to 1 when VAR1 >= VAR2 otherwise to 0.

# AUTHOR

Toshimitsu FUJIWARA, <tttfjw at gmail.com>

Copyright (C) 2015 by Toshimitsu FUJIWARA

This program is free software; you can redistribute it and/or modify it under the terms of the the Artistic License (2.0). You may obtain a copy of the full license at: