Home

Introduction

Constraint programming is a declarative programming paradigm which represents problems using variables and its relations (constraints). In this paradigm, solving problems is separated two phases. They are:

• Modeling - represent problem using variables and constraints
• Solving - search values for variables satisfying constraints

iZ-C is a library developed to support this programming method in C, and Algorithm::CP::IZ is a Perl wrapper for this library.

Installation

This module needs iZ-C library, so download iZ-C and extract archive fist.

Perl module itself will be installed usual step. You can specify path to iz.h and libiz.so when executing Makefile.PL using -I and -L option.

$ perl Makefile.PL -I <path-to-iz-h> -L <path-to-libiz-so>
$ make
$ make test
$ make install

Or settting environment varialbe IZ_INC_DIR and IZ_LIB_DIR, You can install module from CPAN directly.

Simple Example

Let's start with graph coloring problem along the tradition of constraint programming.

Problem

1---2
| / |
3---4

Problem is to assign colors to nodes such that no adjacent nodes have the same color.

Model

Define variable x_i as color (color number) of node i, and variables have constraint like following:

• { x_i | 1, 2, 3 }
• node i is adjacent to node j ⇒x_i ≠ x_j

(We need 4 colors for arbitrary graph, but only 3 colors are enough for this problem)

Code

(Node numbers are mapped to 0..3 because index number starts from 0 in Perl)

use strict;
use warnings;

use Algorithm::CP::IZ;

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

########## Modeling ##########
my $COLORS = 3;

# create variables for nodes (0..3)
my @nodes = map { $iz->create_int(1, $COLORS) } (0..3);

# apply constraint "Neq" to adjacent nodes (variables).
my @edges = ([0, 1], [0, 2], [1, 2], [1, 3], [2, 3]);
for my $e (@edges) {
    $nodes[$e->[0]]->Neq($nodes[$e->[1]]);
}

########## Solving ##########
if ($iz->search(\@nodes)) {
    print $nodes[0], "---", $nodes[1], "\n";
    print "| / |\n";
    print $nodes[2], "---", $nodes[3], "\n";
}

Output:

1---2
| / |
3---1