« Ubiquity 0.1 - kommandoradsfunktionalitet i Firefox | Main | Constraint programming: Fler MiniZinc-modeller, t.ex. Martin Gardner och nonogram »

september 14, 2008

Constraint programming i Java: Choco version 2 släppt - samt jämförelse med JaCoP

I JaCoP - Java Constraint Programming solver gjordes en jämförelse mellan två olika constraint programming system (villkorsprogrammering) i Java:
- JaCoP (se även My JaCoP page)
- Choco (My Choco page)

Då avvaktade jag med framförallt modeller i och mer information om Choco tills det var mer stabilt (beta-versionen har ändrats mycket den senaste tiden) Det är det nu: I onsdags (10 september 2008) släpptes version 2.0 (lagom till internationella constraint programming-kongressen som börjar idag, se nedan under Relaterat). Denna version har en ny hemsida (cf. sidan för Choco version 1).

Choco version 2

Choco presenteras så här:
The CHOCO development team is eager to announce the release of the new version of its open-source constraint solver: CHOCO.

Choco is Java library that can be used for:
* teaching (a user-oriented constraint solver with open-source code)
* research (state-of-the-art algorithms and techniques, user-defined constraints, domains and variables)
* real-life applications (many application now embed choco)

Choco is final-user oriented. It has been under heavy refactoring from V1 to V2. New constraints, new features have been offered.

Choco is available online with a complete documentation, tutorials, various materials, forums, etc.


Dokumentation


Till skillnad från JaCoP finns det mycket dokumentation om Choco, t.ex. en bra och inträngande genomgång hur man skapar modeller, tweakar lösningar och mer avancerade användningar.

Sajten innehåller följande huvuddelar:


Ett exempel: Minesweeper


I JaCoP - Java Constraint Programming solver presenterades JaCoP-modellen för Minesweeper. Här är motsvarande modell i Choco. Input till programmet är en problemfil, t.ex. minesweeper0.txt.

Jag har tagit bort en del saker för att göra listningen kortare. Den fullständiga modellen finns i MineSweeper.java.

Den observante kan notera att det är i stort sett samma modell, med endast några få skillnader:
- namn på variablerna: IntegerVariable i Choco, FDV i JaCoP
- metod att skapa variabler: makeIntVar(...) respektive new FDV(store,...). Notera att Choco har en metod för att initiera en array: makeIntVarArray.
- metod för att ange villkoren: model.addConstraint respektive store.impose
- själva villkoren (constraints), i choco behöver man inte new:a dessa villkor. Se mer om villkoren nedan.

public class MineSweeper {
    int r;        // number of rows
    int c;        // number of cols
    int X = -1;  // represents the unknown value in the problem matrix
    int[][] problem; // The problem matrix
    IntegerVariable[][] game;    // The IntegerVariable version of the problem matrix.
    IntegerVariable[][] mines;   // solution matrix: 0..1 where 1 means mine.
    Model model;
    CPSolver s;
    public void model() {
        model = new CPModel();
        if (problem == null) {
            r = 8;
            c = 8;
            int problemX[][] = {{X,2,X,2,1,1,X,X},
                                {X,X,4,X,2,X,X,2},
                                {2,X,X,2,X,X,3,X},
                                {2,X,2,2,X,3,X,3},
                                {X,X,1,X,X,X,4,X},
                                {1,X,X,X,2,X,X,3},
                                {X,2,X,2,2,X,3,X},
                                {1,X,1,X,X,1,X,1}};
            problem = problemX;
        }
        /*
         * Initialize the constraint variables.
         */
        mines = new IntegerVariable[r][c];
        game  = new IntegerVariable[r][c];
        for(int i = 0; i < r; i++) {
            mines[i] = makeIntVarArray("m_" + i, c, 0,1);
            game[i] = makeIntVarArray("g_" + i, c, -1,8);
        }
        // Add the constraints
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // This is a known value of neighbours
                if (problem[i][j] > X) {
                    // mirroring the problem matrix.
                    model.addConstraint(eq(game[i][j], problem[i][j]));
                    // This could not be a mine.
                    model.addConstraint(eq(mines[i][j], 0));
                    // Sum the number of neighbours: same as game[i][j].
                    ArrayList lst = new ArrayList();
                    for(int a = -1; a <= 1; a++) {
                        for(int b = -1; b <= 1; b++) {
                            if (i+a >= 0 && j+b >=  0 &&
                                i+a < r && j+b < c) {
                                lst.add(mines[i+a][j+b]);
                            }
                        }                        
                    }
                    model.addConstraint(eq(sum(lst.toArray(new IntegerVariable[1])), game[i][j]));
                } // end if problem[i][j] > X
            } // end for j
        } // end for i
    } // end model
   //
   // Search
   //
    public void search() {
        s = new CPSolver();
        s.read(model);
        s.solve();        
        if (s.isFeasible()) {
            int sol = 1;
            do {
                System.out.println("\nSolution # " + sol);
                for(int i = 0; i < r; i++) {
                    for(int j = 0; j < c; j++) {
                        System.out.print(s.getVar(mines[i][j]).getVal() + " ");
                    }
                    System.out.println();
                }
                sol++;
            } while (s.nextSolution() == Boolean.TRUE);
        } else {
            System.out.println("No solutions.");
        } // end if result
    } // end search
   //
   // Main
   //
    public static void main(String args[]) {
        MineSweeper minesweeper = new MineSweeper();
        String file = "";
        if (args.length > 0) {
            file = args[0];
            minesweeper.readFile(file);
        }
        minesweeper.model();
        minesweeper.search();
    } // end main
} // end class


Resultatet:

readFile(minesweeper0.txt)
6
6
..2.3.
2.....
..24.3
1.34..
.....3
.3.3..
22[+0] millis.
16[+0] nodes
20[+0] backtracks
20[+0] fails

Solution # 1
1 0 0 0 0 1
0 1 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 1 1 1 0 0
1 0 0 0 1 1


Fördelar/nackdelar

* Exempel. Till skillnad från JaCoP så finns det inte så många fullständiga exempel i distributionen. Några av exemplen är kvar från version 1 och är inte portade till version 2 (koden är helt enkelt bortkommenterad). Det är lite synd. I gengäld finns många test cases för i stort sett samtliga metoder i systemet, vilket är informativt.

* Dokumentation. Som ovan sagt är dokumentationen (på sajten) mycket bra och förklarar i stort sett allting. Man bör dock notera att eftersom den slutliga version 2 är så pass ny finns det några ställen där man inte uppdaterat till denna version. Några constraints är inte heller dokumenterade. Jag antar att allt sådant kommer att fixas till snart.

* Domäner. Choco styrka är finita domäner (heltal eller sådant som kan representeras av heltal), men kan - till skillnad från JaCoP - hantera mängder (sets) samt flyttal. Stödet för de två sistnämda är dock inte lika stort eller stablilt som för finita domäner.

* Global constraints. På sidan Constraints presenteras de (global) constraints som finns i systemet. De flesta förväntade finns med såsom allDifferent, boolChanneling, distance etc. Jag blev dock lite förvånad att count (villkor för att ange att ett visst värde ska ha ett visst antal förekomster) saknades. I YoungTableaux behövdes nämligen ett sådant villkor, men det implementerades i stället genom att trixa med globalCardinality (en generalisering av count).

Speciellt intressant är de relativt nya geost för att hantera geometriska villkor, och tree för "tree partitioning".

Man kan också notera att det finns en viss skillnad i inställning av "convenient constraints" mellan Choco och JaCoP. Efter en fråga till JaCoPs utvecklare om varför villkoret XminusYeqZ saknades kom svaret att man följer en minimalistisk princip att endast implementera de nödvändiga villkoren (man kan använda XplusYeqZ i stället). I Choco verkar man inte ha denna princip: där finns såväl plus som minus; man kan initiera en hel vektor på ett bräde med makeVarIntArray och behöver inte loopa över elementens makeVarInt etc.

* XCSP. XCSP är ett XML-format för constraint satisfaction/programming-problem som används bl.a. i Third International CSP Solver Competition (se även nedan under Relaterat). Choco kan läsa i detta format. Efter de tester jag gjort tycker jag att Chocos stöd är något bättre än JaCoPs. Choco kan dock inte skriva XCSP (det kan JaCoP), men det är på gång.

* Prestanda. Jag har inte gjort några formella tester men min känsla är att Choco nästan alltid är snabbare och kan hantera större problem än JaCoP. Men det är alltså en subjektiv åsikt.

* Open source. Choco är open source till skillnad från JaCoP vilket naturligtvis är en stor fördel. JaCoP kommer enligt uppgift att släppas öppet inom kort, men än så länge finns det inte fritt tillgängligt.

Det finns ett Subversion-repositorium på https://choco.svn.sourceforge.net/svnroot/choco . Jag använder fortfarande version 2.0.0 men kommer väl snart att gå över till 2.0.1 (som skapades i förrgår, dvs strax efter den officiella releasen).


Slutkommentar
I och för sig tycker jag om JaCoP eftersom det har en slim och "naturlig" klassmodell, har många exempel. Trots det kommer jag nog mestadels att använda Choco för villkorsprogrammering i Java eftersom det är (än så länge) ett mer fullständigt system, har bättre dokumentation och drivs av fler utvecklare (vad jag förstår är det åtminstone en heltidstjänst enkom för att utveckla Choco).

Mina Choco-modeller

På My Choco page finns ett antal Choco-modeller. Det är (i skrivande stund) en portning av de modeller som finns (i skrivande stund) på My JaCoP page (förutom DeBruijnIterate som var en specialmodell för att generera lösningar batch-vis).

Modellerna är (direkt från sidan):


Relaterat


Choco: Constraint Programming i Java om Choco version 1, som skrev i april 2006.


Intressant nog börjar stora villkorsprogrammeringskonferensen International Conference on Principles and Practice of Constraint Programming idag och håller på till 18 september. Jag väntar speciellt med spänning på resultatet av två olika tävlingar:
- Third International CSP Solver Competition
- MiniZinc Challenge 2008 (Rules). En av utvecklarna av MiniZinc har antytt att några av mina MiniZinc-modeller med på ett hörn i denna tävling.

Posted by hakank at september 14, 2008 10:56 FM Posted to Constraint Programming | Pyssel