« En vecka med Asus Eee Pc 900 | Main | Digital grusväg 1/2008 ute! »

augusti 17, 2008

JaCoP - Java Constraint Programming solver

Fast det jag egentligen hållit på med den senaste veckan är att kolla in JaCoP, ett (annat) constraint programming-system i Java.

Det som beskrivs här nedan är JaCoP version 2. Information om version 1.3 finns på ett annat ställe (LTH, Lunds Universitet), men det är alltså 2:an som gäller.


JaCoP


JaCoP presenteras på följande sätt:

Java Constraint Programming solver, JaCoP in short, is a Java library, which provides Java user with Constraint Programming technology. JaCoP is actively developed since year 2001. Krzysztof Kuchcinski and Radoslaw Szymanek are the authors of this Java library. They are working in their free time to improve this library. They both have worked countless hours to create software which is frequently used not only in their research work.

...

JaCoP is available for free as Java library for research and educational purposes. JaCoP is not free for commercial applications. However, our intention is to charge minimum fees in order to have some additional help in creating better documentation and better product.

I JaCoP google group berättas att man har planer att skapa en "dual license" (dvs både en fri och en komersiell licens).

För att få tillgång till JaCoP-distributionen måste man - än så länge - maila Radoslaw Szymanek (radoslaw.szymanek@gmail.com ) med en förfrågan, helst på engelska. Berätta gärna att du läste om JaCoP här.


Dokumentation


JaCoP Web är stället där man hittar information om systemet. Tyvärr finns ännu inte så mycket dokumenterat för version 2, vilket är en stor nackdel. I distributionen finns ett stort (>= 57) antal exempel som gör att man får bra tips hur JaCoP används (eventuellt finns någon av nedanstående modeller med). Man lär sig även mycket genom att studera den övriga källkoden.

SudukoACSP förklaras detaljerat och pedagogiskt om de viktigaste JaCoP-metoderna via lösning av Sudoku-spelet. Rekommenderad läsning.

Man kan ställda frågor på JaCoPFAQ (kräver registrering).

En PDF-presentation Introduction to JaCoP för version 1 finns på kurssidan EDA340: Constraint Programming (LTH, Lunds Universitet).


Ett exempel: Minesweeper


Här nedan visas ett exempel av ett JaCoP-program. Jag har valt Minesweeper ("MS Röj") för enkel jämförelse med MiniZinc modellen på Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life.

En stor skillnad mellan MiniZinc-modellen och JaCoP-modellen är - förutom att JaCop-modellen är mer pratig - att det finns stöd för att läsa in externa problem-filer (MiniZinc har ett annat sätt att lösa detta).

Input till programmet är en problemfil, t.ex. minesweeper0.txt:

# Minesweeper problem.
# This problem file is used by
# http://www.hakank.org/JaCoP/MineSweeper.java
#
# Problem from Gecode/examples/minesweeper.cc problem 0
6
6
..2.3.
2.....
..24.3
1.34..
.....3
.3.3..


Här nedan visas de mest relevanta delarna av programmet. Det är alltså inte ett komplett program.

import JaCoP.constraints.*;
import JaCoP.core.*;
import JaCoP.search.*;
public class MineSweeper {
    // declare the variables
    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
    FDV[][] game;    // The FDV version of the problem matrix.
    FDV[][] mines;   // solution matrix: 0..1 where 1 means mine.
    Store store;
    public void model() {
        store = new FDstore();
        // Initialize the constraint variables.
        mines = new FDV[r][c];
        game  = new FDV[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // 0: no mine, 1: mine
                mines[i][j] = new FDV(store, "m_" + i + "_" + j, 0, 1);
                // mirrors the problem matrix
                game[i][j] = new FDV(store, "g_" + i + "_" + j, -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.
                    store.impose(new XeqC(game[i][j], problem[i][j]));
                    // This could not be a mine.
                    store.impose(new XeqC(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]);
                            }
                        }                        
                    }
                    store.impose(new Sum(lst, game[i][j]));
                } // end if problem[i][j] > X
            } // end for j
        } // end for i
    } // end model

Till skillnad från MiniZinc (men i likhet med Choco, Gecode etc) måste man uttryckligen ange vilken sökmetod som ska användas. Här används metoden SimpleMatrixSelect över variabelmatrisen mines. Här skrivs endast den sista lösningen ut.

(Jag har önskat en möjlighet att skriva ut samtliga lösningar via en iterator istället för att alla lösningar räknas ut innan presentationen, och det kanske kommer.)

    public void search() {
        SelectChoicePoint select = 
            new SimpleMatrixSelect (mines,
                              new SmallestDomain(),
                              new IndomainMin ()
                              );
        Search label = new DepthFirstSearch ();
        label.getSolutionListener().searchAll(true);
        label.getSolutionListener().recordSolutions(true);
        boolean result = label.labeling(store, select);
        int numSolutions = label.getSolutionListener().solutionsNo();
        if (result) {
            System.out.println("\nThe last solution:");
            for(int i = 0; i < r; i++) {
                for(int j = 0; j < c; j++) {
                    System.out.print(mines[i][j].value() + " ");
                }
                System.out.println();
            }
            System.out.println("numSolutions: " + numSolutions);
        } else {
            System.out.println("No solutions.");
        } // end if result
    } // end search


Fördelar/nackdelar


Här är några kommentarer om JaCoP.

Intrycket efter en vecka är att det är ett trevligt system, och för det mesta är det naturligt hur man programmerar modellerna. De lite mer avancerade modellerna nedan, Minesweeper och de Bruijn sekvenser, portades från MiniZinc-modellerna ganska rakt av och utan några större problem. Det är naturligtvis en fördel att ha modellerat en hel del constraint programming-problem innan.

* Bra exempel. Det finns många exempel som visar hur man använder JaCoP. Många är standardexempelmen det finns några nya saker.

* Dokumentation. En av de stora nackdelarna är avsaknaden av dokumentation, men eftersom det är en enkel klassstruktur är det rätt enkelt att hitta constraints (de finns i katalogen JaCoP/constraints och sökmetoderna (JaCoP/search.

* Finita domäner. JaCoP hanterar endast finita domäner, dvs stöd för mängder (sets) saknas, liksom flyttal. Det senare gör inte så mycket för min egen del, däremot saknar jag sets för modellering av en del problem. En kommentar om detta från utvecklaren av JaCoP finns här.

* Global constraints. JaCoP har ett antal global constraints, vilket förenklar både syntaktiskt och prestandamässigt.

* XCSP. XCSP är ett XML-format för constraint satisfaction/programming problem som används bl.a. i Third International CSP Solver Competition. JaCoP kan både läsa och skriva i detta format. Trevligt! (Tänk på att skapa XML-filen innan sökningen börjar, annars hårdkodas lösningen.)

* Prestanda. Jag har inte gjort några formella tester av hastighet eller minnesanvändning, men de flesta av mina modeller (se nedan) har lösts snabbt, åtminstone lika snabbt som den snabbaste av de solvers som finns för MiniZinc (vilket oftast är Gecode/fz).

* Java. Naturligtvis är det mestadels en fördel att använda ett "riktigt" programspråk och baka in stöd för constraint programming där. Ett exempel på detta är Minesweeper (och Quasigroup completion problem) där man kan läsa in problemfiler av godtyckligt format. Problemet är att det blir emellanåt väldigt pratigt, t.ex. just vid filinläsning, och det är något som jag inte tycker om (och är en stor orsak till min förtjusning över agila programspråk). Ett framtida projekt är att skriva om några modeller till Groovy.

* Jämförelse med Choco 2.0. När jag började med JaCoP så var ett av målen att jämföra med Choco version 2, ett annat constraint programming system i Java. Choco 2.0 är dock för närvarande i beta-status så jag avvaktar med detta till det blivit lite mer stabilt. (Det har tidigare skrivits om Choco version 1 här.)

Choco är mer kompetent än (existerande distribution av) JaCoP: mer dokumentation (både pedagogiska texter och JavaDoc), stöd för mängder och flyttal, och det finns mängder av test-program. Dock finns det betydligt färre "riktiga" exempel än för JaCoP.

Som sagt. Det är ett framtida projekt att jämföra JaCoP och Choco.

Mina JaCoP-modeller

My JaCoP page har jag lagt ett antal modeller för version 2. Några av dem kräver utilitetsklassen HakankUtil.java. Samtliga program (i alla fall i nedanstående lista) finns även som MiniZinc-modell (MiniZinc är ett alldeles utmärkt verktyg för att prototypa constraint programming-problem).


Se även

* Sidan för JaCoP version 1. Där finns referenser som fortfarande är relevanta.

* Choco: Constraint Programming i Java där JaCoP nämns en passant som ett system att kolla in.

Posted by hakank at augusti 17, 2008 10:00 FM Posted to Constraint Programming | Pyssel