« augusti 2008 | Main | oktober 2008 »

september 28, 2008

Constraint programming: Fler MiniZinc-modeller, t.ex. Martin Gardner och nonogram

Förutom att ha lekt med de Javabaserade villkorsprogrammeringssystemet Choco version 2 har även några MiniZinc-modeller skapats sen sist.

Förra gången räknades till cirka 360 modeller (stora eller små). Nu är det cirka 440 stycken (stora och små), vilket innebär cirka 80 nya modeller. Som vanligt finns de på My MiniZinc page. De läggs upp där så fort som de är klara, så om du är intresserad av nya modeller är det bara att - mer eller mindre - regelbundet kolla den sidan.

Denna gång har det blivit en del problem från husguden Martin Gardner, mest beroende på att jag håller på att beta av samlingen med Martin Gardners pyssel i The Colossal Book of Short Puzzles and Problems, (ISBN: 9780393061147, sammanställd av Dana Richards).

Personliga favoriter
* nonogram.mzn, även känd som "painting by numbers". Utifrån rad- och kolumnsummor ska man skapa bilder. Jämför med "discrete tomography" som nämndes i Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem samt med "Survo puzzle" som nämndes i Nästan 36 modeller med villkorsprogrammering (constraint programming) i MiniZinc.
* two_cube_calendar.mzn: Two cube calendar. Till synes enkelt problem, men det var trixigt att modellera eftersom en siffra kan användas på två olika sätt.
* diffn.mzn. Placering av boxar utan att de överlappar varandra. Stödjer tre olika representationer (vilket tyvärr gör modellen lite svåröverskådlig).
* calculs_d_enfer.mzn: Calculs d'enfer. Yet another alfametiskt problem med några twistar: här används även negativa värden och man ska minimera det största absolutvärdet. En viktig sak är att använda korrekt heuristik annars går det långsamt att lösa problemet: den snabbaste jag hittade var "occurrence" respektive "indomain_max".


Martin Gardner
Detta är några problem från de första kapiteln av (den ovan nämnda) The Colossal Book of Short Puzzles and Problems. En bok att rekommendera. Man noterar redan på de första sidorna (om man inte läst Gardner tidigare för då vet man troligen detta redan) att en del standardexempel - t.ex. SEND + MORE = MONEY, Langfords heltalssekvens - beskrevs eller populariserades av Martin Gardner.

Nedanstående har det gemensamma kännetecknet att de - mig veterligen - inte modellerats i MiniZinc. I vissa fall har jag inte sett någon diskussion alls på nätet (i alla fall inte under dessa namn).

curious_set_of_integers.mzn: Curious set of integers
divisible_by_7.mzn: Divisible by 7
gardner_prime_puzzle.mzn: Prime puzzle
magic_squares_and_cards.mzn: Magic squares and cards
nine_digit_arrangement.mzn: Nine digit arrangements
nine_to_one_equals_100.mzn: Nine to one equals 100
nonogram.mzn
pool_ball_triangles.mzn: Pool ball triangles
two_cube_calendar.mzn: Two cube calendar


Andra pyssel och matematiska gåtor
bank_card
calculs_d_enfer.mzn: Calculs d'enfer puzzle (from the NCL manual), se kommentar ovan
coins_problem.mzn: Minimize the number of coins...
family_riddle.mzn: Family riddle
magic_hexagon.mzn: Magic hexagon
message_sending: Message sending


Operations research, linear programming, integer programming
lectures: ett scheduleringsproblem
scheduling_chip: ännu ett scheduleringsproblem


Non linear problems
spreadsheet.mzn, exempel på problem som ofta löses i spreadsheets


Combinatorics
maximum_subarray.mzn: Maximum subarray
set_packing.mzn, set packing
set_covering_skiena.mzn, set covering (ännu ett exempel)
all_paths_graph.mzn, skapa vägar med utgångspunkt från en grafrepresentation


Global constraints
Som vanligt har även några global constraints modellerats. Förutom att många av dem är nyttiga i sig, är modelleringen av dem en nyttig övning. (Nu finns det cirka 100 global constraints modellerade, endast en tredjedel av den fulla listan. I och för sig är cirka 40-50 global constraints redan definierade i MiniZinc, antingen inbyggda eller i global.mzn, men det är i alla fall en massa kvar...)

contains_array
cumulative_test
diffn
discrepancy
disjunctive
domain
domain_constraint
imply
in_interval
in_set
indexed_sum
inverse_within_range
ith_pos_different_from_0
k_same
k_same_modulo
lex2
lex_between
lex_chain_less
lex_different
lex_greater
max_index
min_index
nclass
open_alldifferent
product_test
roots_test
same_interval
same_modulo
shift
sliding_sum
sliding_time_window
sliding_time_window_from_start
smooth
soft_same_var
sort_permutation
weighted_sum (not in the catalogue)


Prolog/constraint logic programming benchmarks
Här är några benchmarks för Prolog eller constraint programming som inte tidigare modellerats i MiniZinc.

crossbar.mzn
crypta.mzn
eq10.mzn
fractions.mzn
grocery2.mzn
magic3.mzn
magic4.mzn
multipl.mzn
olympic.mzn
parallel_resistors.mzn
sudoku_25x25_250.mzn
voltage_divider.mzn


Övrigt
fizz_buzz Liten programmeringsövning
huey_dewey_louie, litet logiskt problem
power, variant av power-funktionen (som ännu inte funkar i MiniZinc)

Posted by hakank at 08:17 EM Posted to Constraint Programming | Matematik | Pyssel

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

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 10:56 FM Posted to Constraint Programming | Pyssel