gecol

Gecol aims at providing CFFI bindings to allow for constraint programming in Lisp using Gecode.
The intended API will be quite low-level, on which other layers can be built.

Currently, we are targeting Gecode 1.3.1.

News

• 10.01.2008: Mauricio Toro is going to work on a port for Gecode 2.0.
  Until we can eventually merge, a new branch has been created.

• 08.01.2007: The big update is done! :)

• 28.12.2006: A big update is in preparation that will allow to work with finite sets and also clean up the API.

• 07.12.2006: A very preliminary version of the codebase has been uploaded.
  Suggestions are very welcome.
  For the time being, you can only work with finite domain integers -
  although limited, this should already allow to solve a range of problems.
  Be careful however, the API might still change....

Mailing Lists

• gecol-devel
  for discussions, questions, etc.
• gecol-announce
  for announcements

Download

This project has not released any files.

Darcs

Source code is held in a Darcs repository at: http://common-lisp.net/project/gecol/darcs/gecol.
You can find more information on how to use darcs at the DarcsWiki.

You can browse the code through its DarcsWeb interface.

Examples

For most up-to-date and further examples see examples.lisp

First, we load it:

? (oos 'load-op :gecol)
[...]

Please note: The following examples are currently out-of-date, but they should give a general idea.

Let's start with the cartesian product of three integer variables that each have a domain of (1 2 3):

? (defun cartesian-product ()
  ;; create a search space of 3 integer variables
  ;; in the range [1,3] and 0 boolean variables
  (let ((s (gecol:create-space 3 1 3 0 0)))    
    ;; determines the order, how values are chosen,
    ;; when distributing a variable
    (gecol:gec-branch-vars-min s)
    ;; create a search-engine that can be queried
    ;; for the next solution
    (let ((e (gecol:create-search-engine s)))
      (loop
         for sol = (gecol:search-next e)
         ;; a null-pointer means there is no more solution
         until (cffi:null-pointer-p sol)
         ;; access the current solution
         do (format t "~a, ~a, ~a~%"
                    (gecol:space-read-int sol 0)
                    (gecol:space-read-int sol 1)
                    (gecol:space-read-int sol 2))
         do (gecol:dispose-space sol))
      (gecol:dispose-search-engine e)
      (gecol:dispose-space s))))
CARTESIAN-PRODUCT
? (cartesian-product)
1, 1, 1
1, 1, 2
1, 1, 3
1, 2, 1
1, 2, 2
1, 2, 3
1, 3, 1
1, 3, 2
1, 3, 3
2, 1, 1
2, 1, 2
2, 1, 3
2, 2, 1
2, 2, 2
2, 2, 3
2, 3, 1
2, 3, 2
2, 3, 3
3, 1, 1
3, 1, 2
3, 1, 3
3, 2, 1
3, 2, 2
3, 2, 3
3, 3, 1
3, 3, 2
3, 3, 3
NIL

Same as above, but with an additional distinct constraint:

? (defun distinct ()
  (let ((s (gecol:create-space 3 1 3 0 0)))
    ;; distinct - we pass the indices of the integer variables
    (gecol:gec-distinct s (list 0 1 2) :icl-def)
    (gecol:gec-branch-vars-min s)
    (let ((e (gecol:create-search-engine s)))
      (loop
         for sol = (gecol:search-next e)
         until (cffi:null-pointer-p sol)
         do (format t "~a, ~a, ~a~%"
                    (gecol:space-read-int sol 0)
                    (gecol:space-read-int sol 1)
                    (gecol:space-read-int sol 2))
         do (gecol:dispose-space sol))
      (gecol:dispose-search-engine e)
      (gecol:dispose-space s))))
DISTINCT
? (distinct)
1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
NIL
? 

Force the three variables to be sorted:

? (defun sorted ()
  (let ((s (gecol:create-space 3 1 3 0 0)))
    ;; v0 < v1
    (gecol:gec-rel-var s 0 :irt-< 1 :icl-def)
    ;; v1 < v2
    (gecol:gec-rel-var s 1 :irt-< 2 :icl-def)
    (gecol:gec-branch-vars-min s)
    (let ((e (gecol:create-search-engine s)))
      (loop
         for sol = (gecol:search-next e)
         until (cffi:null-pointer-p sol)
         do (format t "~a, ~a, ~a~%"
                    (gecol:space-read-int sol 0)
                    (gecol:space-read-int sol 1)
                    (gecol:space-read-int sol 2))
         do (gecol:dispose-space sol))
      (gecol:dispose-search-engine e)
      (gecol:dispose-space s))))
SORTED
? 
(sorted)
1, 2, 3
NIL

Again unconstrained cartesian product, but with another value ordering:

? (defun cartesian-product-distr-max ()
  (let ((s (gecol:create-space 3 1 3 0 0)))    
    ;; !!
    (gecol:gec-branch-vars-max s)
    (let ((e (gecol:create-search-engine s)))
      (loop
         for sol = (gecol:search-next e)
         until (cffi:null-pointer-p sol)
         do (format t "~a, ~a, ~a~%"
                    (gecol:space-read-int sol 0)
                    (gecol:space-read-int sol 1)
                    (gecol:space-read-int sol 2))
         do (gecol:dispose-space sol))
      (gecol:dispose-search-engine e)
      (gecol:dispose-space s))))

CARTESIAN-PRODUCT-DISTR-MAX
? (cartesian-product-distr-max)
3, 3, 3
3, 3, 2
3, 3, 1
3, 2, 3
3, 2, 2
3, 2, 1
3, 1, 3
3, 1, 2
3, 1, 1
2, 3, 3
2, 3, 2
2, 3, 1
2, 2, 3
2, 2, 2
2, 2, 1
2, 1, 3
2, 1, 2
2, 1, 1
1, 3, 3
1, 3, 2
1, 3, 1
1, 2, 3
1, 2, 2
1, 2, 1
1, 1, 3
1, 1, 2
1, 1, 1
NIL

Back to Common-lisp.net.