bindings for the Gecode constraint-programming library

## Project description

==========================================

gecode-python - Gecode bindings for Python

==========================================

Requirements

============

* Python 2.6, 2.7, or 3.2

* Gecode >= 3.6.0

Installation

============

see also file INSTALL for easier/alternative installation methods.

To install globally:

python setup.py install

or to install in your home directory:

python setup.py install --prefix $HOME

which would install the package under ~/lib/python2.7/site-packages (if using

version 2.7 of Python). If you install in your home, you also need to adjust

environment variable PYTHONPATH to search in $HOME/python2.7 and

$HOME/python2.7/site-packages.

If Gecode is installed in a non standard location, before you can build and

install, you need to adjust environment variables CXXFLAGS, LDFLAGS, and

LD_LIBRARY_PATH.

Documentation

=============

There are many constants in the gecode package. It is probably easiest to

import everything:

from gecode import *

IntSet

~~~~~~

intset(int,int)

intset(SPEC)

returns an IntSet for the corresponding domain. SPEC is a list of ints and

pairs of ints (interval). It might be tempting to simply represent an

intset as a list of specs, but this would be ambiguous with IntArgs which,

here, are represented as lists of ints.

Space

~~~~~

space()

this function creates a Space.

Variables

~~~~~~~~~

Unlike in Gecode, variable objects are not bound to a specific Space. Each one

actually contains an index with which it is possible to access a Space-bound

Gecode variable. Variables can be created using the following methods of a

Space:

Space.intvar(int,int)

Space.intvar(IntSet)

returns an IntVar initialized with the corresponding domain.

Space.boolvar()

returns a BoolVar initialized with the domain [0,1]

Space.setvar(int glbMin, int glbMax, int lubMin, int lubMax, int cardMin=MIN, int cardMax=MAX)

Space.setvar(int glbMin, int glbMax, IntSet lub, int cardMin=MIN, int cardMax=MAX)

Space.setvar(IntSet glb, int lubMin, int lubMax, int cardMin=MIN, int cardMax=MAX)

Space.setvar(IntSet glb, IntSet lub, int cardMin=MIN, int cardMax=MAX)

returns a SetVar initialized with the corresponding domain.

Space.intvars(int N, ...)

Space.boolvars(int N)

Space.setvars(int N, ...)

returns a list of N variables initialized with the domain as stipulated by

the remaining arguments "...".

An advantage of non Space-bound variables, is that you can use them both to

post constraints in the original space AND to consult their values in

solutions. Below are Space methods for looking up information about variables.

Each of these methods can either take a variable as argument, or a list (or

tuple) of variables, and returns resp. either a value, or a list of values:

Space.assigned(X)

returns True if variable X is assigned (determined) in the Space, False

otherwise.

Space.min(X)

Space.max(X)

Space.med(X)

Space.val(X)

Space.size(X)

Space.width(X)

Space.regret_min(X)

Space.regret_max(X)

These can be used for both IntVars and BoolVars and have the same meaning

as in Gecode.

Space.ranges(IntVar)

Space.values(IntVar)

Return resp. a list of pairs and a list of ints representing the domain of

the argument variable.

Space.values(BoolVar)

same for boolean variables.

Space.glbSize(SetVar)

Space.lubSize(SetVar)

Space.unknownSize(SetVar)

Space.cardMin(SetVar)

Space.cardMax(SetVar)

Space.lubMin(SetVar)

Space.lubMax(SetVar)

Space.glbMin(SetVar)

Space.glbMax(SetVar)

These can be used for SetVars and have the same meaning as in Gecode.

Space.glbRanges(SetVar)

Space.lubRanges(SetVar)

Space.unknownRanges(SetVar)

These return lists of pairs of ints representing the corresponding set

bounds.

Space.glbValues(SetVar)

Space.lubValues(SetVar)

Space.unknownValues(SetVar)

These return lists of ints representing the corresponding set bounds.

Space.keep(Var)

Space.keep(Vars)

Variables can be marked as "kept". In this case, only such variables

will be explicitly copied during search. This could bring substantial

benefits in memory usage. Of course, in a solution, you can then only

look at variables that have been "kept". If no variable is marked as

"kept", then they are all kept. Thus marking variables as "kept" is

purely an optimization.

Space.status()

returns the status of the space

Space.choice()

returns a Choice object

Space.commit(Choice c, int a)

commits the space to alternative a in Choice object c

Space.constrain(Space sol)

constrain the space to be better than solution sol

Choice

~~~~~~

Choice.alternatives()

returns the number of alternatives in this Choice object

Search

~~~~~~

Space.search(restart=False, threads=None, c_d=None, a_d=None,

statistics=None, memory_limit=-1, node_limit=-1, fail_limit=-1,

time_limit=-1)

returns an iterator of solutions. Each solution is a Space.

The restart option selects the Restart search engine, but only if an

optimization criterion has been specified. The threads option selects

and controls the parallel variant of the search engine. The c_d and a_d

options control recomputation.

If provided, statistics should be an object whose attributes (propagate,

wmp, fail, node, depth, memory) are cumulatively updated after each

iteration (i.e. after each implicit call to next to search for a next

solution).

If one or more limit arguments are provided, then an appropriate stop

object is created and will be used by the underlying search engine to

stop the search when any given limit is exceeded.

In order to search for optimal solutions, it is necessary to indicate what

needs to be optimized:

Space.minimize(IntVar x)

Space.maximize(IntVar x)

search for a solution minimizing (resp. maximizing) x.

Space.minimize(IntVar x,IntVar y)

Space.maximize(IntVar x,IntVar y)

search for a solution minimizing (resp. maximizing) the ratio x/y.

Gist

~~~~

Space.gist(onclick=None, threads=None, c_d=None, a_d=None)

if your installation of Gecode has Gist support, then this will invoke it.

onclick is an inspector or an iterable of inspectors. An inspector is

a callable, or a class whose instances are callables, that has/have been

specially annoted by a decorator:

@inspector("My Inspector 1")

def show1(s2):

print s2.values([X1,X2])

Note that s2 is not necessarily a solution! You may also define a

textinspector to show textual output in a graphical window:

@textinspector("My Inspector 2")

def show2(s2):

return "X1=%s X2=%s" % s2.values([X1,X2])

A textinspector must return a string.

Bound Variables

~~~~~~~~~~~~~~~

A bound variable is essentially a pair of a non-bound variable and a Space.

IntVal.__call__(Space)

BoolVar.__call__(Space)

SetVar.__call__(Space)

a bound variable can be created by applying a non-bound variable to a

Space.

Space.bind(X)

returns a bound variable for X, bound to this space; if X is a list of

variables, this returns a list of bound variables.

Constants

~~~~~~~~~

All constants used in Gecode are available with the same names in these

bindings.

Constraints

~~~~~~~~~~~

In Gecode, all constraints take a space as first argument. In these bindings,

all constraints are methods of Space. Everywhere Gecode would use an XXXArgs

argument, here, you should simply use a list (or tuple) of XXX. All gecode

constraints are available (except "extensional", which are not yet

implemented). All branchings are available except those with parameters that

require additional implementation in C++. Please refer to the Gecode

documentation.

Half-Reification

~~~~~~~~~~~~~~~~

Starting with version 4.0.0 Gecode also supports half-reification. Full

reification is C <-> B; half-reification is C -> B (resp. C <- B). Where

previously B, a BoolVar, was supplied, now a reification spec is also accepted:

Reify(B,RM_EQV) is for full reification (C <-> B)

Reify(B,RM_IMP) is for half reification (C -> B)

Reify(B,RM_PMI) is for half reification (C <- B)

DISJUNCTORS

~~~~~~~~~~~

Disjunctors are an experimental extension to Gecode implemented by the

gecode-python bindings. They provide support for disjunctions of clauses,

where each clause is a conjunction of constraints:

C1 or C2 or ... or Cn

Each clause is executed "speculatively": this means it does not affect the main

space. When a clause becomes failed, it is discarded. When only one clause

remains, it is committed: this means that it now affects the main space.

Example:

Consider the problem where either X=Y=0 or X=Y+(1 or 2) for variable X and Y

that take values in 0..3.

s = space()

x,y = s.intvars(2,0,3),

First, we must create a disjunctor as a manager for our 2 clauses:

d = s.disjunctor()

We can now create our first clause:

c1 = d.clause()

This clause wants to constrain x and y to 0. However, since it must be

executed "speculatively", it must operate on new variables x1 and y1 that

shadow x and y:

x1,y1 = c1.intvars(2,0,3)

c1.forward([x,y],[x1,y1])

The forward(...) stipulation indicates which global variable is shadowed by

which clause-local variable. Now we can post the speculative clause-local

constraints for X=Y=0:

c1.rel(x1,IRT_EQ,0),

c1.rel(y1,IRT_EQ,0),

We now create the second clause which uses x2 and y2 to shadow x and y:

c2 = d.clause()

x2,y2 = c2.intvars(2,0,3)

c2.forward([x,y],[x2,y2])

However, this clause also needs a clause-local variable z2 taking values 1 or

2 in order to post the clause-local constraint x2=y2+z2:

z2 = c2.intvar(1,2)

c2.linear([-1,1,1],[x2,y2,z2],IRT_EQ,0)

Finally, we can branch and search:

s.branch([x,y],INT_VAR_SIZE_MIN,INT_VAL_MIN)

for sol in s.search():

print sol.val([x,y])

gecode.fsa

~~~~~~~~~~

This module provides support for building finite state automata for use in the

extensional constraint. It exports the class FSA for creating arbitrary finite

state automata explicitly (see help(gecode.fsa)), and the object RE for

creating automata using regular expressions.

REGULAR EXPRESSIONS:

RE() empty regular expression

RE(x) regular expression matching integer x

RE(x,y) regular expression matching integers in [x,y]

r1>>r2 sequential composition

r1|r2 parallel composition (disjunction)

r.OPT matches an optional r

r.STAR matches r 0 or more times

r.PLUS matches r 1 or more times

r.REPEAT(n) matches r at least n times

r.REPEAT(n,m) matches r at least n times and at most m times

gecode.domain

~~~~~~~~~~~~~

This module provides support for coding finite domains of values using

integers. It exports the class Domain.

Domain([v0,...,vN])

create a domain for these values

see help(gecode.domain) for further documentation.

gecode-python - Gecode bindings for Python

==========================================

Requirements

============

* Python 2.6, 2.7, or 3.2

* Gecode >= 3.6.0

Installation

============

see also file INSTALL for easier/alternative installation methods.

To install globally:

python setup.py install

or to install in your home directory:

python setup.py install --prefix $HOME

which would install the package under ~/lib/python2.7/site-packages (if using

version 2.7 of Python). If you install in your home, you also need to adjust

environment variable PYTHONPATH to search in $HOME/python2.7 and

$HOME/python2.7/site-packages.

If Gecode is installed in a non standard location, before you can build and

install, you need to adjust environment variables CXXFLAGS, LDFLAGS, and

LD_LIBRARY_PATH.

Documentation

=============

There are many constants in the gecode package. It is probably easiest to

import everything:

from gecode import *

IntSet

~~~~~~

intset(int,int)

intset(SPEC)

returns an IntSet for the corresponding domain. SPEC is a list of ints and

pairs of ints (interval). It might be tempting to simply represent an

intset as a list of specs, but this would be ambiguous with IntArgs which,

here, are represented as lists of ints.

Space

~~~~~

space()

this function creates a Space.

Variables

~~~~~~~~~

Unlike in Gecode, variable objects are not bound to a specific Space. Each one

actually contains an index with which it is possible to access a Space-bound

Gecode variable. Variables can be created using the following methods of a

Space:

Space.intvar(int,int)

Space.intvar(IntSet)

returns an IntVar initialized with the corresponding domain.

Space.boolvar()

returns a BoolVar initialized with the domain [0,1]

Space.setvar(int glbMin, int glbMax, int lubMin, int lubMax, int cardMin=MIN, int cardMax=MAX)

Space.setvar(int glbMin, int glbMax, IntSet lub, int cardMin=MIN, int cardMax=MAX)

Space.setvar(IntSet glb, int lubMin, int lubMax, int cardMin=MIN, int cardMax=MAX)

Space.setvar(IntSet glb, IntSet lub, int cardMin=MIN, int cardMax=MAX)

returns a SetVar initialized with the corresponding domain.

Space.intvars(int N, ...)

Space.boolvars(int N)

Space.setvars(int N, ...)

returns a list of N variables initialized with the domain as stipulated by

the remaining arguments "...".

An advantage of non Space-bound variables, is that you can use them both to

post constraints in the original space AND to consult their values in

solutions. Below are Space methods for looking up information about variables.

Each of these methods can either take a variable as argument, or a list (or

tuple) of variables, and returns resp. either a value, or a list of values:

Space.assigned(X)

returns True if variable X is assigned (determined) in the Space, False

otherwise.

Space.min(X)

Space.max(X)

Space.med(X)

Space.val(X)

Space.size(X)

Space.width(X)

Space.regret_min(X)

Space.regret_max(X)

These can be used for both IntVars and BoolVars and have the same meaning

as in Gecode.

Space.ranges(IntVar)

Space.values(IntVar)

Return resp. a list of pairs and a list of ints representing the domain of

the argument variable.

Space.values(BoolVar)

same for boolean variables.

Space.glbSize(SetVar)

Space.lubSize(SetVar)

Space.unknownSize(SetVar)

Space.cardMin(SetVar)

Space.cardMax(SetVar)

Space.lubMin(SetVar)

Space.lubMax(SetVar)

Space.glbMin(SetVar)

Space.glbMax(SetVar)

These can be used for SetVars and have the same meaning as in Gecode.

Space.glbRanges(SetVar)

Space.lubRanges(SetVar)

Space.unknownRanges(SetVar)

These return lists of pairs of ints representing the corresponding set

bounds.

Space.glbValues(SetVar)

Space.lubValues(SetVar)

Space.unknownValues(SetVar)

These return lists of ints representing the corresponding set bounds.

Space.keep(Var)

Space.keep(Vars)

Variables can be marked as "kept". In this case, only such variables

will be explicitly copied during search. This could bring substantial

benefits in memory usage. Of course, in a solution, you can then only

look at variables that have been "kept". If no variable is marked as

"kept", then they are all kept. Thus marking variables as "kept" is

purely an optimization.

Space.status()

returns the status of the space

Space.choice()

returns a Choice object

Space.commit(Choice c, int a)

commits the space to alternative a in Choice object c

Space.constrain(Space sol)

constrain the space to be better than solution sol

Choice

~~~~~~

Choice.alternatives()

returns the number of alternatives in this Choice object

Search

~~~~~~

Space.search(restart=False, threads=None, c_d=None, a_d=None,

statistics=None, memory_limit=-1, node_limit=-1, fail_limit=-1,

time_limit=-1)

returns an iterator of solutions. Each solution is a Space.

The restart option selects the Restart search engine, but only if an

optimization criterion has been specified. The threads option selects

and controls the parallel variant of the search engine. The c_d and a_d

options control recomputation.

If provided, statistics should be an object whose attributes (propagate,

wmp, fail, node, depth, memory) are cumulatively updated after each

iteration (i.e. after each implicit call to next to search for a next

solution).

If one or more limit arguments are provided, then an appropriate stop

object is created and will be used by the underlying search engine to

stop the search when any given limit is exceeded.

In order to search for optimal solutions, it is necessary to indicate what

needs to be optimized:

Space.minimize(IntVar x)

Space.maximize(IntVar x)

search for a solution minimizing (resp. maximizing) x.

Space.minimize(IntVar x,IntVar y)

Space.maximize(IntVar x,IntVar y)

search for a solution minimizing (resp. maximizing) the ratio x/y.

Gist

~~~~

Space.gist(onclick=None, threads=None, c_d=None, a_d=None)

if your installation of Gecode has Gist support, then this will invoke it.

onclick is an inspector or an iterable of inspectors. An inspector is

a callable, or a class whose instances are callables, that has/have been

specially annoted by a decorator:

@inspector("My Inspector 1")

def show1(s2):

print s2.values([X1,X2])

Note that s2 is not necessarily a solution! You may also define a

textinspector to show textual output in a graphical window:

@textinspector("My Inspector 2")

def show2(s2):

return "X1=%s X2=%s" % s2.values([X1,X2])

A textinspector must return a string.

Bound Variables

~~~~~~~~~~~~~~~

A bound variable is essentially a pair of a non-bound variable and a Space.

IntVal.__call__(Space)

BoolVar.__call__(Space)

SetVar.__call__(Space)

a bound variable can be created by applying a non-bound variable to a

Space.

Space.bind(X)

returns a bound variable for X, bound to this space; if X is a list of

variables, this returns a list of bound variables.

Constants

~~~~~~~~~

All constants used in Gecode are available with the same names in these

bindings.

Constraints

~~~~~~~~~~~

In Gecode, all constraints take a space as first argument. In these bindings,

all constraints are methods of Space. Everywhere Gecode would use an XXXArgs

argument, here, you should simply use a list (or tuple) of XXX. All gecode

constraints are available (except "extensional", which are not yet

implemented). All branchings are available except those with parameters that

require additional implementation in C++. Please refer to the Gecode

documentation.

Half-Reification

~~~~~~~~~~~~~~~~

Starting with version 4.0.0 Gecode also supports half-reification. Full

reification is C <-> B; half-reification is C -> B (resp. C <- B). Where

previously B, a BoolVar, was supplied, now a reification spec is also accepted:

Reify(B,RM_EQV) is for full reification (C <-> B)

Reify(B,RM_IMP) is for half reification (C -> B)

Reify(B,RM_PMI) is for half reification (C <- B)

DISJUNCTORS

~~~~~~~~~~~

Disjunctors are an experimental extension to Gecode implemented by the

gecode-python bindings. They provide support for disjunctions of clauses,

where each clause is a conjunction of constraints:

C1 or C2 or ... or Cn

Each clause is executed "speculatively": this means it does not affect the main

space. When a clause becomes failed, it is discarded. When only one clause

remains, it is committed: this means that it now affects the main space.

Example:

Consider the problem where either X=Y=0 or X=Y+(1 or 2) for variable X and Y

that take values in 0..3.

s = space()

x,y = s.intvars(2,0,3),

First, we must create a disjunctor as a manager for our 2 clauses:

d = s.disjunctor()

We can now create our first clause:

c1 = d.clause()

This clause wants to constrain x and y to 0. However, since it must be

executed "speculatively", it must operate on new variables x1 and y1 that

shadow x and y:

x1,y1 = c1.intvars(2,0,3)

c1.forward([x,y],[x1,y1])

The forward(...) stipulation indicates which global variable is shadowed by

which clause-local variable. Now we can post the speculative clause-local

constraints for X=Y=0:

c1.rel(x1,IRT_EQ,0),

c1.rel(y1,IRT_EQ,0),

We now create the second clause which uses x2 and y2 to shadow x and y:

c2 = d.clause()

x2,y2 = c2.intvars(2,0,3)

c2.forward([x,y],[x2,y2])

However, this clause also needs a clause-local variable z2 taking values 1 or

2 in order to post the clause-local constraint x2=y2+z2:

z2 = c2.intvar(1,2)

c2.linear([-1,1,1],[x2,y2,z2],IRT_EQ,0)

Finally, we can branch and search:

s.branch([x,y],INT_VAR_SIZE_MIN,INT_VAL_MIN)

for sol in s.search():

print sol.val([x,y])

gecode.fsa

~~~~~~~~~~

This module provides support for building finite state automata for use in the

extensional constraint. It exports the class FSA for creating arbitrary finite

state automata explicitly (see help(gecode.fsa)), and the object RE for

creating automata using regular expressions.

REGULAR EXPRESSIONS:

RE() empty regular expression

RE(x) regular expression matching integer x

RE(x,y) regular expression matching integers in [x,y]

r1>>r2 sequential composition

r1|r2 parallel composition (disjunction)

r.OPT matches an optional r

r.STAR matches r 0 or more times

r.PLUS matches r 1 or more times

r.REPEAT(n) matches r at least n times

r.REPEAT(n,m) matches r at least n times and at most m times

gecode.domain

~~~~~~~~~~~~~

This module provides support for coding finite domains of values using

integers. It exports the class Domain.

Domain([v0,...,vN])

create a domain for these values

see help(gecode.domain) for further documentation.

## Project details

## Release history Release notifications | RSS feed

## Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

### Source Distribution

gecode-python-0.27.tar.gz
(1.4 MB
view hashes)