augusti 23, 2008

Nästan 36 modeller med villkorsprogrammering (constraint programming) i MiniZinc

(Språklig not: Av någon anledning tycker jag inte riktigt om namnet "villkorsprogrammering" utan använder hellre det engelska "constraint programming", men det svenska namnet är vedertaget framförallt i vissa utbildningscentra så det måste nämnas emellanåt.)


Sedan sist har fler MiniZinc-modeller skapats. Det finns nu över 360 .mzn-filer - modeller och datafiler - på My MiniZinc page och det känns därför som rätt tillfälle att rensa lite från inkorgen, närmare bestämt nedanstående nästan 36 modeller. Grupperingen här nedan är inte riktigt samma som på MiniZinc-sidan.

Referenser till problemformulering/originalmodell/inspiration finns som vanligt i respektive modell.


Personliga favoriter


Några personliga favoriter av nedanstående är:
* Survo puzzle. Ett kul litet pyssel som är som en blanding av magiska fyrkanter och diskret tomografi. (Det finns även en JaCoP modell: SurvoPuzzle.java)
* Nadel's construction problem, där "soft constraints" används, dvs där det tillåts att vissa villkor inte uppfylls och man minimerar över antalet som inte uppfylls. Detta eftersom denna modell inte ger några resultat om man kräver att alla villkor ska vara uppfyllda (vilket naturligtvis kan innebära att modellen inte är helt korrekt). Tyvärr har jag inte hittat något facit...

Modeller

Kombinatorik/global constraints
* Dominating Set
* Graph Degree Sequence
* Stretch circuit
* Subsequence sum


Operations research
* Data Envelopment Analysis (DEA) model. (För tillfället är det endast ECLiPSe's eplex-solver som klarar detta.)


Enigma-pyssel
* Enigma eighteen
* Five fives
* Eight times
* Eight times 2, alternativ modell
* Planets


Dell Logic Puzzles
Logiska problem från brownbuffalo.sourceforge.net.
* Tunapalooza
* A round of golf
* Arch friends
* Four islands
* Breaking news
* Baby sitting
* Lecture series


100 dörrars-problemet
Problemformulering t.ex. hos Rosetta code.
* 100 doors problem, unoptimized (version 1)
* 100 doors problem, unoptimized (version 2)
* 100 doors problem, optimized, using set representation
* 100 doors problem, optimized, using array representation


Andra pyssel
* Clock triplets
* Franklin's 8x8 magic square
* Magic sequence, version 3 (en av flera varianter)
* Murder: Ett mord har begåtts ..(logiskt pysse)
* Number Generation, generalisering av Devil's Word (devils_word.mzn respektive Devil's word CGI-program).
* Self Referential Quiz
* Survo puzzle

Två exempel från Constraint Processing skriven av Rina Dechter
* Nadel's construction problem, sidan 5
* Scheduling speakers, sidan 72


Två exempel från theorem proving (automated reasoning)
* Jobs puzzle
* Who killed Agatha?


Övriga modeller
* Family, familjeträd, ett standard Prologprogram formulerat i MiniZinc
* ISBN: en etyd i konstruktion av ISBN-13 (med kontrollsiffra)

Posted by hakank at 08:35 FM Posted to | Comments (0)

augusti 19, 2008

Digital grusväg 1/2008 ute!

Via ett personligt epost-meddelande erhölls den glädjande nyheten att Digital Grusväg (Aperiodisk tidskrift) numro 1 anno 2008 är officiell. För att citera (delar av relevanta) delar av mailet:


I detta nummer...Vad är det i mjölken? Har sista bussen gått?

Samtidigt kan passas på att tipsas om Nerdlunchers (kreativitetens högborg på nätet, som lyckats lokalisera tillståndet av total förvirring, vilket dock måste sägas inte råder å nämnda nätplats), speciellt Wikin där Hr. Grusväg emellanåt och från tid till annan smular sitt oefterlikneliga grus.

Tidigare här på bloggen diskussioner diskuterar sådant som namnets ("Digital Grusväg"s) tillkommande (ehuru länkar är - som vanligt i denna av regn småningom fyllda spindelvävsvärld - inaktuella) .

Posted by hakank at 07:32 EM Posted to Diverse | Comments (0)

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.

På 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

På 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 10:00 FM Posted to Constraint Programming | Pyssel | Comments (0)

augusti 16, 2008

En vecka med Asus Eee Pc 900

För en vecka sedan (lördags lite i 12:00) inköptes en Asus Eee PC 900. Det gjordes efter att ha följt Tommy k Johansson och hans eminenta rapportering kring dessa modeller. (Jag hade sett lillebror 700 av en slump för en månad sedan och började därför kolla in dessa modeller.)

I och för sig skulle jag hellre vilja ha en 901:a - som framförallt har bättre batteritid än 900 - men de inköpsställen i Malmö som besöktes svarade följande på frågan när modellen skulle komma in och vad den skulle kosta:
* slutet på september och kommer att kosta 4000
* vi vet inte
* har ingen aning

Så, tillbaka till 900:an som med anledning av ovanstående således inköptes.

Det är en trevlig lite sak på knappt kilot inklusive batteri. Förvånansvärt mycket går in på den lilla skärmen så det är inga problem att kolla vad som händer i *sfären på Bloglines eller vilka TV-program som går nu, eller läsa mail. Det är ju så jobbigt att gå de drygt 10 metrarna till "stordatorn"

Men det egentliga skälet till inköpet är att jag länge önskat mig en liten "programmeringsdator" där jag kan fortsätta mina (programmerings)skov under reklamavbrott, på bussen eller annorstädes i naturen (där i naturen inberäknas sovrummet). 16 gigg (varav 12 är ledigt) är väldigt mycket eftersom jag inte planerar att dra ner kilovis med filmer eller musik på maskinen.

Efter att ha läst igenom manualen och samtidigt laddat batteriet (och samtidigt tittat på Sverige-matchen i damfotboll) gjordes första surfandet. Nätverket funkade helt enkelt genom att bara sätta i nätverkskabeln vilket överraskade posititvt.

Men efter några minuters surfande och lekande med filmkameran och patiensspelande (en alldeles utmärkt träning för att lära sig musplattan) och OpenOfficande var det: "OK, ge mig nu en prompt.. Det är i ju Linux vi pratar om." Skalet finns via Filhanteraren, /bin/bash (tyvärr finns inte zsh installerad default). ssh:ade in till huvuddator utan problem och packade ihop det som skulle kopieras.

Några spridda kommentarer kring detta:
- användarkontot är /home/users
- "|" (pipe-tecknet) finns via shift + Alt Gr + Z
- CTRL-ALT-t ger en terminal (det finns dock ingen fin ikon) med där får man inte skalet varmed man kan kopiera text med.

De flesta program som testades att kopiera rakt av från Mandriva-distributionen funkade rakt av, t.ex. Java, MiniZinc och lite annat. Men inte Haskells Hugs 98, där jag får "Aritmetiskt räknefel" vid start av hugs. Tyvärr finns ingen gcc installerad för att kompilera källkoden och jag vågar ännu inte att installera det eftersom det har antytts i forum etc att sådant kan bli problem (och Hugs-paketen vågar jag inte heller att installera av samma skäl). Fast det är naturligtvis Emacs som ska installeras först;; vim finns men det blir endast konstiga tecken när man i insert-läge trycker på piltangenterna (ja, det är så jag navigerar och det är möjligen en konsekvens av att vim körs i bash).

Det finns alltså en hel del att göra och lära sig. Och sådant är alltid roligt.

Några andra kommentarer:
- kul med musplattan: Man scrollar genom att föra två fingrar upp/ned, och man zoomar in/ut genom att placera två fingrar i mitten på plattan och sära dem (och vice versa).
- jag är alltså mycket nöjd med maskinen
- batteriet blir varmt så om man - tvärtemot varningen som finns i manualen - vill ha datorn i knät bör man ha en extra skiva som skydd för kläder (eller skinn nu på sommaren).
- ett kilo dator känns faktiskt mer än ett kilo socker i ryggsäcken.

Se även
Här är några sajter som har en viss myckethet av information om Asusarna:

Tommy j Johanssons skriverier
IDG Allt om Asus Eee PC
All about Asus EEE PC…
Eee User forum
Asus Eee News, Mods, and Hacks

Posted by hakank at 09:59 FM Posted to Diverse | Comments (5)

juli 20, 2008

Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life

Här är några fler MiniZinc modeller som skapats sedan sist. För en fullständig lista över samtliga publicerade modeller, se My MiniZinc page.

I samtliga modeller anges referenser, inspiration etc.

Personligen tycker jag följande modeller är lite kul:
* Minesweeper (som presenteras speciellt nedan)
* Game of Life
* Quasigroup completion problem (se nedan för ett antal testproblem)
* Födelsedagsproblemet


Minesweeper


Tänkte nämna något mer om Minesweeper.

Modellen till Minesweeper är - möjligen förvånansvärt - enkel. Notera att man s.a.s. "räknar baklänges": genom att summera minorna (mines) för att få de värden som ges i problemet (game). Sådant är typiskt i constraint programming.


% MiniZinc model for Minesweeper.
int: r; % rows
int: c; % column
int: X = -1; % the unknowns

% encoding: -1 for unknown, >= 0 for number of mines in the neighbourhood
array[1..r, 1..c] of -1..8: game;
array[1..r, 1..c] of var 0..1: mines;

constraint
forall(i in 1..r, j in 1..c) (
(
(game[i,j] >= 0 )
->
game[i,j] = sum(a,b in {-1,0,1} where
i+a > 0 /\ j+b > 0 /\
i+a <= r /\ j+b <= c
)
(mines[i+a,j+b])
)
/\
(game[i,j] > X -> mines[i,j] = 0)
/\
(game[i,j] = X <- mines[i,j] = 1)
)
;

Ett exempelproblem, där ett tal anger hur många bomber det finns som grannar och X att vi inte vet något om rutan (det kan vara en bomb men behöver inte vara det).

% Minesweeper example
r = 6;
c = 6;
game = array2d(1..r, 1..c, [
X,X,2,X,3,X,
2,X,X,X,X,X,
X,X,2,4,X,3,
1,X,3,4,X,X,
X,X,X,X,X,3,
X,3,X,3,X,X,
]);

Lösningen - som kommer blixsnabbt - är följande. Positionerna av bomberna markeras med 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

Minesweeper har visats vara ett s.k. NP-komplett problem, dvs ohyggligt svårt att lösa generellt för godtyckligt stora problem. De exempel som används i modellen är dock så (förhållandevis) små att lösningen kommer direkt.

Se vidare
Richard Kaye's Minesweeper Pages
Minesweeper (Wikipedia)
Ian Stewart on Minesweeper
The Authoritative Minesweeper: Articles and Announcements

Automatisk "lösning" av Minesweeper i Mozart/Oz där fler referenser ges.

Övriga modeller

Här är de övriga modellerna, grupperade enligt samma princip som på My MiniZinc page.

Puzzles, small and large

Global constraints

Operations research, linear programming, integer programming

  • Markov chains (fertlizer example from Taha "Operations Research")
  • Talent, exempel från ILOG OPL

Combinatorial problems

Other models


Posted by hakank at 08:23 EM Posted to Constraint Programming | Matematik | Pyssel | Comments (0)

juli 07, 2008

Fler MiniZinc modeller kring recreational mathematics

I Martin Chlond's Integer Programming Puzzles i MiniZinc förevisades MiniZinc-modeller för Martin Chlonds Integer Programming Puzzles.

Här är några fler i samma stil (recreational mathematics) som jag just har lagt upp på min Minizinc-sida . Det är MiniZinc-modeller baserade på Chlonds Puzzle artiklar (och de där ingående integer programming-modellerna) i INFORMS Transactions on Education (en öppen tidskrift om operational research).


Och så några andra recreational mathematics modeller som publicerades samtidigt:

Posted by hakank at 07:53 EM Posted to Constraint Programming | Matematik | Pyssel | Comments (0)

juli 04, 2008

Martin Chlond's Integer Programming Puzzles i MiniZinc

Som tidigare nämnts är Puzzles - Integer Programming in Recreational Mathematics en mycket trevlig samling pyssel skapad av Martin Chlond. De flesta problemen är klassiker inom området (recreational mathematics) och flera används som paradigmproblem i constraint programming eller integer programming.

I april skrevs MiniZinc-modeller för samtliga problem men jag har inte kommit loss att hyfsa till dem. Förrän nu. Samliga 48 problem har nu gåtts igenom så att de har en enhetlig struktur, kommentarer är på engelska etc.

Förutom MiniZinc-modellen nedan finns även en länk till Martin Chlonds lösning av problemet (oftast skrivet som en XPress Model, men de allra sista är i AMPL). MiniZinc-modellerna är i stort sett en konvertering av Chlonds modell. I några fall har flyttalsrepresentationer omvandlats till heltalsrepresentationer.

Nedanstående listning finns även på min MiniZinc-sida, men det blir en bättre bäring om de även listas här.

Martin Chlond's Integer Programming Puzzles

The collection is separated in four sections where the problems is presented:
* Integer Programming Puzzles section 1
* Integer Programming Puzzles section 2
* Integer Programming Puzzles section 3
* Integer Programming Puzzles section 4


Problems: Integer Programming Puzzles section 1
Solutions:
Twelve draughts puzzle (Chlond's solution)
Description : Twelve draughts puzzle Source : Boris Kordemsky - The Moscow Puzzles (P36)

Coin puzzle
(Chlond's solution)
Description : Coin puzzle
Source : Mathematical Puzzles of Sam Loyd (P111)

Egg basket puzzle
(Chlond's solution)
Description : Egg basket puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

Evens puzzle
(Chlond's solution)
Description : Evens puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P8)

Fifty puzzle
(Chlond's solution)
Description : Fifty puzzle
Source : The Puzzles of Sam Loyd (P 54)

Honey division puzzle
(Chlond's solution)
Description : Honey division puzzle
Source : H E Dudeney - Amusements in Mathematics

Wine cask puzzle
(Chlond's solution)
Description : Wine cask puzzle
Source : M Kraitchik - Mathematical Recreations (p 31)

Knight domination puzzle - all squares threatened
(Chlond's solution)
Description : Knight domination puzzle - all squares threatened
Source : M Kraitchik - Mathematical Recreations (P256)

Mango puzzle
(Chlond's solution)
Description : Mango puzzle
Source : M Kraitchik - Mathematical Recreations (P32)

Remainder puzzle
(Chlond's solution)
Description : Remainder puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

5 X 5 puzzle
(Chlond's solution)
Description : 5 X 5 puzzle
Source : Unknown

Lights on puzzle
(Chlond's solution)
Description : Lights on puzzle
Source : Unknown


Problems: Integer Programming Puzzles section 2

Solutions:
Clarke's tobacconist
(Chlond's solution)
Description : Clarke's tobacconist
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Tommy's Birthday Coins
(Chlond's solution)
Description : Tommy's Birthday Coins
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Lewis Carroll coin puzzle
(Chlond's solution)
Description : Lewis Carroll coin puzzle
Source : Wakeling, E., (1995), Rediscovered Lewis Carroll Puzzles, Dover.

Dudeney's tea mixing problem
(Chlond's solution)
Description : Dudeney's tea mixing problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Jive turkeys
(Chlond's solution)
Description : Jive turkeys
Source : rec.puzzles

Public School Problem
(Chlond's solution)
Description : Public School Problem
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Dudeney's bishop placement problem I
(Chlond's solution)
Description : Dudeney's bishop placement problem I
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Dudeney's bishop placement problem II
(Chlond's solution)
Description : Dudeney's bishop placement problem II
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Kraitchik's queen placement problem
(Chlond's solution)
Description : Kraitchik's queen placement problem
Source : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.

Schuh's queen placement problem
(Chlond's solution)
Description : Schuh's queen placement problem
Source : Schuh, F., (1943), Wonderlijke Problemen;
Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.

Dudeney's queen placement problem
(Chlond's solution)
Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Joshua and his rats
(Chlond's solution)
Description : Joshua and his rats
Source : Sole, T., (1988), The Ticket to Heaven, Penguin Books


Problems: Integer Programming Puzzles section 3

Solutions:
The Abbott's Puzzle
(Chlond's solution)
Description : The Abbott's Puzzle
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The Abbott's Window
(Chlond's solution)
Description : The Abbott's Window
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The First Trial
(Chlond's solution)
Description : The First Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Second Trial
(Chlond's solution)
Description : The Second Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Third Trial
(Chlond's solution)
Description : The Third Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fourth Trial
(Chlond's solution)
Description : The Fourth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fifth Trial
(Chlond's solution)
Description : The Fifth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Sixth Trial
(Chlond's solution)
Description : The Sixth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

Werewolves II
(Chlond's solution)
Description : Werewolves II
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Werewolves IV
(Chlond's solution)
Description : Werewolves IV
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Earthlings
(Chlond's solution)
Description : Earthlings
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling

Equal Vision
(Chlond's solution)
Description : Equal Vision
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling


Problems: Integer Programming Puzzles section 4

Solutions:
On the road
(Chlond's solution)
Description : On the road
Source : Poniachik, J. & L, (1998), Hard-to-solve Brainteasers, Sterling

The Riddle of the Pilgrims
(Chlond's solution)
Description : The Riddle of the Pilgrims
Source : Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.

The Logical Labyrinth
(Chlond's solution)
Description : The Logical Labyrinth
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The gentle art of stamp-licking
(Chlond's solution)
Description : The gentle art of stamp-licking
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The crowded board
(Chlond's solution)
Description : The crowded board
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Non-dominating queens problem
(Chlond's solution)
Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt

Enigma
(Chlond's solution)
Description : Enigma
Source : Herald Tribune circa November 1979 - courtesy of Dr Tito A. Ciriani

Price change puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations (p 33-35), Dover

Book buy puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Shopping puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Book discount problem
(Chlond's solution)
Source: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling

Seven 11 (Chlond's solution)
Source: alt.math.recreational

Posted by hakank at 07:09 FM Posted to Constraint Programming | Pyssel | Comments (0)

juli 03, 2008

Bloggträff i Malmö nu på lördag 5 juli (2008)

Henrik Sundström ordrar bloggträff i Malmö nu på lördag,(kl 1400. Läs mer och anmäl ert intresse hos honom.

Posted by hakank at 06:55 FM Posted to Bloggmiddagar | Comments (0)

juni 30, 2008

Gruppteoretisk lösning av M12 puzzle i GAP - take 2

I går skrev jag Gruppteoretisk lösning av M12 puzzle i GAP och publicerade ett GAP-program för att lösa M12 puzzle (för övriga länkar, se gårdagens skrift).

Efter lite mer funderande har jag nu kommit på en mer elegant lösning där man inte behöver göra inverse (^-1) på själva pusslet, och att man inte behöver arbeta baklänges. Den förra lösningen var inte felaktig, endast bökig.


Det som ändrades var helt enkelt hur man definierar merge-operatorn. Den är nu

merge:=PermList([1,3,5,7,9,11,12,10,8,6,4,2]);


Här är den nya GAP-koden och med ett nytt pyssel.


#
# GAP program for solving the M12 puzzle.
#

#
# The two operations M (Merge) and I (Reverse, Inverse)
#
merge:=PermList([1,3,5,7,9,11,12,10,8,6,4,2]);
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
g:=Group([reverse2, merge2]);

puzzle := [5,4,10,8,11,12,6,2,3,9,1,7];

#
# Solve the puzzle:
# x1 = I (inverse)
# x2 = M (merge)
#
# Notation: x2^-3 = x^(11-3) = x^8 = M8
#
Factorization(g, PermList(puzzle));

#
# End of GAP code
#

Notera att man inte behöver göra inverse på PermList(puzzle);

Lösningen på detta är

x1*x2*x1*x2^2*x1*x2*x1*x2^-5*x1

Denna lösning kan man alltså följa från början, och motsvarar följande operationer i M12-pusslet. Notera att x2^-5 är - som tidigare - samma som x^(11-5) = x^6 = M6.


I M I M2 I M I M6 I

Som jämförelse använder vi även den andra metoden som inte garanterar någon kort faktorisering:


#
# A variant
# R: = I
# M = M
#
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);
PreImagesRepresentative(hom,PermList(puzzle));

Lösningen är

M*R*M^-2*R*M^-4*R*M^-1*R*M*R*M^3*R^-1*M^-1*R^-1*M^-4*R^-1*M*R^-1*M^-1*R*M^-1

Vilket alltså motsvarar M12-operationerna:

M I M9 I M7 I M10 I M I M3 I M10 I M7 I M I M10 I M10

Denna lösningen är också betydligt längre.


Jaha, så kan det gå när man vill publicera något innan EM finalen i fotboll...

Posted by hakank at 07:22 EM Posted to | Comments (0)

juni 29, 2008

Gruppteoretisk lösning av M12 puzzle i GAP

I Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc) presenterades det gruppteoretiska pysslet M12, då med en lösning i MiniZinc (modellen M12.mzn).

När jag läste om M12 tänkte jag att det skulle vara skoj med även en gruppteoretisk lösning eftersom det är ett gruppteoretiskt problem. En sådan lösning har nu gjorts med hjälp av det abstrakta algebraiska systemet GAP. Numera finns GAP även med i distributionen av det öppna matematiska (och mycket trevliga) systemet Sage.

Uppdatering
Efter lite funderande kom jag på en bättre lösning. I stället för att ändra en massa i denna text skrev jag en ny: Gruppteoretisk lösning av M12 puzzle i GAP - take 2, vilken se.


Kort beskrivning av M12
Som tidigare beskrivits går M12-pysslet ut på att man har en sekvens av 12 siffror i en härlig oordning och man ska med hjälp av två operationer återställa sekvensen till 1,2,3,4,5,6,7,8,9,10,11,12. Operationerna är:
Merge: [1, 12, 2, 11,3, 10, 4, 9, 5, 8, 6, 7] blir [1,2,3,4,5,6,7,8,9,10,11,12].
Inverse: Vänder listan om, [1,2,3,4,5,6,7,8,9,10,11,12] blir [12,11,10,9,8,7,6,5,4,3,2,1]. Not, jag kallar operationen (av historiska skäl) för Reverse här nedan.


GAP-program
Här är GAP-programmet (M12_gap.txt). Resultat från ett kommando eller kommentar skrivs efter "#".


Först definierar vi operatorerna, dvs generatorerna i gruppen. Här används PermList som tar en lista och skapar en permutationscykel.

#
# Solving the M12 for a specific sequence
#

#
# Define the operators
#

# Reverse (Inverse)
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
# (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)

# Merge
merge := PermList([1,12,2,11,3,10,4,9,5,8,6,7]);
# (2,12,7,4,11,6,10,8,9,5,3)

Skapa gruppen g och gör några tester.


# Create the group
g:=Group([reverse, merge]);
# Group([ (1,12)(2,11)(3,10)(4,9)(5,8)(6,7), (2,3,5,9,8,10,6,11,4,7,12) ])

# Which group is it?
StructureDescription(g);
# "M12"

Size(g);
# 95040

Bra, det är alltså gruppen M12, dvs Mathieu-grupp av ordningen 12. Notera att det finns ett inbyggt kommando för att skapa en Mathieugrupp (MathieuGroup), men den har inte de generatorer som vil ska använda, alltså rullar vi vår egen.


Nu börjar det roliga. Låt oss som exempel ta följande sekvens som nyss skapats av M12-programmet.


#
# Create the puzzle to solve
#
puzzle:=[4, 5, 11, 1, 9, 6, 3, 10, 2, 7, 12, 8];;


För att få reda på lösningen görs en "faktorisering", med hjälp av funktionen Factorization.


Factorization(g, PermList(puzzle)^-1);
# x1*x2^2*x1*x2^-5*x1*x2^-5

Här har vi en lösning som ska tolkas som operationer i pysslet:

x1*x2^2*x1*x2^-5*x1*x2^-5

x1 betyder den första generatorn (dvs Reverse/Inverse) och x2 är Merge.

Det finns två saker att tänka på här:
- man ska läsa sekvensen baklänges
- alla operationer med negativ exponent måste konverteras till en positiv exponent. Det görs med en enkel subtraktion: x2^-5 innebär samma sak som x2^(11-5) = x2^6

Om vi översätter enligt ovanstående två regler blir det:

x2^6 x1 x2^6 x1 x2^2 x1

Så, uttolkat i samma form som M12-applikationen blir lösningen följande. Tänk på att vi arbetar med lösningen bakifrån och att x1 är I och x2 är M:

M6 I M6 I M2 I

Detta är en lösning med 6+1+6+1+2+1 = 17 steg.


En variant

Förutom Factorization finns det en annan metod, och det är den som generellt rekommenderas för att göra denna typ av "faktoriseringar". Tyvärr tenderar den att generera längre lösningar än med Factorization.


#
# This is the recommended function for factorizations, but it gives longer
# solutions (strings) than Factorization.
#

#
# Create names to identify the operations
#
M:=g.2; R:=g.1;
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);

#
# Now, solve the puzzle
#
PreImagesRepresentative(hom,PermList(puzzle)^-1);
# M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Lösningen är alltså:

M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Notera att R^-1 ska tolkas som en Inverse-operation.

Ovanstående motsvarar följande M12-operationer:

M2 I M10 I M8 I M3 I M I M4 I M8

Detta är en lösning på 2 + 1 + 10 + 1 + 8 + 1 + 3 + 1 + 1 + 1 + 4 + 1 + 8 = 42 steg, vilket är mycket längre än Factorization-approachen.


Man bör notera att dessa faktoriseringar är optimerade att få så små exponenter som möjligt oavsett om det är positiva eller negativa exponenter. Vi är dock endast intresserade av positiva exponenter och lider därför av denna optimering.

Om man adderar exponenterna utan tecken, ger Factorization i alla fall en enklare lösning.

Factorization: x1*x2^2*x1*x2^-5*x1*x2^-5 = 1 + 2 + 1+ 5 +1+ 5 = 15 steg.

PreImagesRepresentative: M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2 = 3 + 1 + 4 + 1 + 1+ 3+ 1 + 3+ 1+ 1 + 1 + 2 = 22 steg.


Båda dessa faktoriseringar går mycket snabbt, typ någon sekund eller så.


Jämförelse med MiniZinc-lösningen
Jag testade att köra pysslet med MiniZinc-modellen M12.mzn. Den tar väldigt lång tid (typ 10-tals minuter) och ger följande lösning på 18 steg, dvs något sämre än Factorization-varianten. Operatorn 1 motsvarar Merge och operatorn 2 motsvarar Inverse.


2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2

dvs operationerna: R M6 R M2 R M R M3 R M

Så här ser sekvensen ut för respektive operation. Siffran till vänster är operationen. Första raden är ursprungssekvensen och är endast med för presentationens skull.


0: 4 5 11 1 9 6 3 10 2 7 12 8
2: 8 12 7 2 10 3 6 9 1 11 5 4
1: 8 7 10 6 1 5 4 11 9 3 2 12
1: 8 10 1 4 9 2 12 3 11 5 6 7
1: 8 1 9 12 11 6 7 5 3 2 4 10
1: 8 9 11 7 3 4 10 2 5 6 12 1
1: 8 11 3 10 5 12 1 6 2 4 7 9
1: 8 3 5 1 2 7 9 4 6 12 10 11
2: 11 10 12 6 4 9 7 2 1 5 3 8
1: 11 12 4 7 1 3 8 5 2 9 6 10
1: 11 4 1 8 2 6 10 9 5 3 7 12
2: 12 7 3 5 9 10 6 2 8 1 4 11
1: 12 3 9 6 8 4 11 1 2 10 5 7
2: 7 5 10 2 1 11 4 8 6 9 3 12
1: 7 10 1 4 6 3 12 9 8 11 2 5
1: 7 1 6 12 8 2 5 11 9 3 4 10
1: 7 6 8 5 9 4 10 3 11 2 12 1
2: 1 12 2 11 3 10 4 9 5 8 6 7
1: 1 2 3 4 5 6 7 8 9 10 11 12 % Solution!

Posted by hakank at 08:25 EM Posted to Constraint Programming | Matematik | Pyssel | Comments (0)

juni 24, 2008

MiniZinc-nyheter

Här är några nyheter om constraint programming-systemet MiniZinc.

* Det har kommit en ny version av MiniZinc: version 0.8.1, som i princip endast är buggfix jämfört med version 0.8.

* ECLiPSe stödjer nu version 0.8-formatet. Ladda ner den senaste utvecklingsversionen här. I skrivande stund är det version 5.10_135 som gäller.

* Eftersom ECLiPSe ny stödjer version 0.8-formatet, har jag som utlovats ändrat alla mina modeller till detta format. Se My MiniZinc Page. Ett fåtal modeller krånglade och finns därför kvar i gamla formatet.

* Skaparna av MiniZinc har startat en tävling MiniZinc Challenge 2008. Fördelen med detta är att det kan generera lite buzz, samt göra så att fler solvers utvecklas.

* En ny solver har tillkommit:: fzntini som bygger på SAT solvern Tinisat. För närvarande finns det endast en Linux-exekutabel av solvern, dvs ingen källkod.

Posted by hakank at 09:23 FM Posted to Constraint Programming | Comments (0)

Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc)

Här är några matematiska / logiska pyssel med lösningar i MiniZinc.

n-puzzle (8-puzzle, 15-puzzle)

n-puzzle (8-puzzle, 15-puzzle) är ett synnerligen standardpyssel som ofta används för att testa algoritmer och liknande inom AI eller för att träna hjärnan. Det går ut på att flytta en blank bricka runt i en matris så att siffrorna återställs till en given ordning (oftast 1..15 eller 1..8) och den blanka ska vara i den nedersta högra rutan .

Min lösning på detta problem finns i n_puzzle.mzn och får väl anses vara ett pseudo-härke eftersom det använder en del trixerier såsom dummy-drag (kring rad 111).

Här är exempel på 8-puzzle, dvs en matris med 3x3. Talet 9 representerar den blanka rutan som flyttas runt.

Definiera först utgångspositionen:

puzzle =
[|2,3,6,
|1,4,9,
|7,5,8|];

Resultatet är (med num_sols = 8, dvs antal olika drag):


puzzle:
2 3 6
1 4 9
7 5 8
...
0: 2 3 6 1 4 9 7 5 8
0: 2 3 9 1 4 6 7 5 8
0: 2 9 3 1 4 6 7 5 8
0: 9 2 3 1 4 6 7 5 8
0: 1 2 3 9 4 6 7 5 8
0: 1 2 3 4 9 6 7 5 8
0: 1 2 3 4 5 6 7 9 8
1: 1 2 3 4 5 6 7 8 9
moves:
0 6
6 3
3 2
2 1
1 4
4 5
5 8
8 9

Lösningen finns i andra kolumnen i moves, dvs

6 3 2 1 4 5 8 9

Där 6 betyder att blank (9) och brickan som finns i position 6 ska byta plats, 3 att 9 och brickan i position 3 ska byta plats etc.

Raderna med matrisen visar hur draget påverkar matrisen (som en vektor). Talet framför raden (0 eller 1) visar om lösningen är gjort (1) eller inte (0).


M12


M12 är ett pyssel inspirerat av spel såsom ovanstående 15-pyssel och Rubiks kub (och dess släktingar). Skaparna av M12, gor Kriz and Paul Siegel, beskrev det Scientific American-artikeln Rubik's Cube Inspired Puzzles Demonstrate Math's "Simple Groups" för någon vecka sedan:

What we wanted for educational purposes was an entertaining way to develop people’s intuitions for groups entirely unlike the ones represented by the cube. And what we wanted as puzzle fans was a new set of puzzles whose solutions require a substantially different strategy from that of Rubik’s Cube and its relatives. So we made the natural connection: we were able to develop three new puzzles based on groups known as sporadic simple groups, whose properties are both remarkable and not well known except to specialists. Happily, the experiences of our colleagues show that anyone who can learn to solve Rubik’s Cube can gain an equally substantial understanding of these sporadic simple groups by doing our puzzles. But more, these puzzles are challenging in the sense that they do not yield to the methods that work with Rubik’s Cube—and we think they are a lot of fun. Readers who want to get their hands on them right away can download them.

Kortfattad beskrivning av M12
Talen 1 till och med 12 används, och de blandas slumpmässigt (fast inte hur som helst). Själva pysslet går ut på att man ska få tillbaka ursprungspositionen 1..12 med hjälp av endast två operationer:
- invert: placera talen i omvänd ordning, dvs 1..12 blir 12..1.
- merge: detta är en variant av "perfekt blandning". Den beskrivs som is a "card shuffle" best understood by trying it out, och kan väl enklast förklaras med följande: Om konfigurationen är

a) 1 12 2 11 3 10 4 9 5 8 6 7

och man gör en merge blir resultatet


b) 1 2 3 4 5 6 7 8 9 10 11 12

dvs man får då lösningspositionen.

Lösning i MiniZinc
I M12.mzn finns en modell för att lösa M12, dvs det enklaste av de tre problemen. För mer avancerade problemkonfigurationer, säg antal operationer > 24, tar det rätt lång tid.

Exempel:
Här är ett enkelt problem:

init = [7,1,8,9,12,5,3,10,4,11,6,2]

Lösning:

init: [7, 1, 8, 9, 12, 5, 3, 10, 4, 11, 6, 2]
check: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
check_ix: 10
operations: [0, 1, 1, 1, 2, 1, 1, 1, 1, 2, 0, 0]
0: 7 1 8 9 12 5 3 10 4 11 6 2
1: 7 8 12 3 4 6 2 11 10 5 9 1
1: 7 12 4 2 10 9 1 5 11 6 3 8
1: 7 4 10 1 11 3 8 6 5 9 2 12
2: 12 2 9 5 6 8 3 11 1 10 4 7
1: 12 9 6 3 1 4 7 10 11 8 5 2
1: 12 6 1 7 11 5 2 8 10 4 3 9
1: 12 1 11 2 10 3 9 4 8 5 7 6
1: 12 11 10 9 8 7 6 5 4 3 2 1
2: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12

Operationerna som används är kodade enligt:
0: gör inget (samma som föregående rad) . Not: Första raden är en dummy operation.
1: merge (M)
2: inverse (I)

Lösningen här är alltså: MMMIMMMMI .
Tyvärr klarar MiniZinc inte av att presentera strängar därav de numeriska värdena.

Tips: Antalet rader i lösningen (rows) påverkar väldigt mycket hur lång tid det tar. Börja därför med ett lägre värde (t.ex. 12) och öka detta försiktigt.

Not: Modellen är till strukturen rätt lik modellen för n-pysslet (se ovan) och det är ingen slump. (Jag skrev dock M12.mzn före n_puzzle.mzn)


Mer info om M12
* För att spela M12 (och dess storebröder) online kan man gå hit.
* Spelen finns även att tillgå som Windows-program från en av författarnas hemsida Igor Kriz. Se README för mer info.
* God Plays Dice skrev lite om detta i Rubik's deck of cards?.
* Wikipedia om den gruppteoretiska bakgrunden: Sporadic group.


SET puzzle


Tommy på Användbart skrev om dessa problem för några dagar sedan. Problemet påminner om vissa typer av IQ-test där man ska lista ut vilka saker som hör ihop med andra, och tycker man sådana problem är intressanta är SET värt att bita i.

När Tommy berättade om detta på senaste bloggträffen var en av mina första reaktioner att börja med att skapa en modell för problemet. Vilket sålunda har gjorts.

Läs mer om SET, med regler, tips etc:
* Wikipedia Set_(game), som väldigt korfattat beskriver problemet så här


Different "categories":
* They all have the same number , or they have three different numbers.
* They all have the same symbol , or they have three different symbols.
* They all have the same shading, or they have three different shadings.
* They all have the same color , or they have three different colors.

* New York Times har ett pyssel varje dag, och här förklaras lite mer.
* Ett lärt paper om SET: Benjamin Lent Davis and Diane Maclagan, The Card Game Set (PDF).


Huvuddelen av MiniZinc-modellen visas här med kommentarer. Den fullständiga modellen finns i set_puzzle.mzn.

include "globals.mzn";

int: n = 9; % number of items
% int: n = 12; % number of items
int: num_sets = 4; % number of Sets to find
% int: num_sets = 5; % number of Sets to find
int: m = 3; % number of items in a Set
int: num_flavours = 3; % number of flavours of the attributes
int: num_attributes = 4; % number of different attributes in each item
array[1..n, 1..num_attributes] of var 1..num_flavours: puzzle;

% decision variable: the sets to find
array[1..num_sets] of var set of 1..n: x;

% solve satisfy;
solve :: set_search(x, "input_order", "indomain_min", "complete") satisfy;

constraint

% exact three items in each set
forall(i in 1..num_sets) (
card(x[i]) = m
)
/\ % must be different sets
all_different(x)
/\
forall(i in 1..num_sets) (

% identify the items in this set
forall(a in 1..num_attributes) (
let {
array[1..m] of var 1..n: arr
}
in
% assign the set
forall(j in 1..m) (
arr[j] in x[i]
)
/\ % symmetry breaking: all different and sorted
forall(j in 1..m-1) (
arr[j] < arr[j+1]
)
/\
(
% EITHER all are same with regard to this attribute
forall(j in 1..m-1) (
puzzle[arr[j],a] = puzzle[arr[j+1],a]
)
\/
% OR all are different with regard to this attribute
forall(i, j in 1..m where i != j) (
puzzle[arr[i],a] != puzzle[arr[j],a]
)
)
) % end forall 1..num_attributes

) % end forall 1..num_sets

% /\ % Symmetry breaking: order the sets
% % Only works for flatzinc version >= 0.8
% increasing(x)
;

output [
show(x)
]

Idealet vore naturligtvis att man kunde förevisa bilden för programmet och sedan löstes problemet, men så långt har jag inte kommit. Istället används en enkel kodning från bilden med de ingående rutornas attribut till en matris av tal. Den kodning som används är följande, dvs det tal som visas inom parentes.


Symbols: Each card has ovals (1), squiggles (2), or diamonds (3) on it;
Color : The symbols are red (1), green (2), or purple (3);
Number : Each card has one (1), two (2), or three (3) symbols on it;
Shading: The symbols are solid (1), striped (2), or open (3).

Det problem som Tommy visar hos sig kodas så här:


puzzle =
array2d(1..n, 1..num_attributes,
[2,1,2,1,
3,3,2,1,
1,2,2,2,
1,2,2,1,
3,2,2,1,
3,1,2,1,
3,2,2,2,
2,3,2,2,
1,2,2,3,
]);

Det finns en unik lösning till detta problem (modulo symmetrier), nämligen dessa fyra mängder

{1, 2, 4}
{2, 5 6}
{3, 4, 9}
{6, 8, 9}

Posted by hakank at 09:07 FM Posted to Constraint Programming | Pyssel | Comments (0)

juni 11, 2008

"Ett handstickat nät" - Jorun Boklövs B-uppsats om svenska stickbloggare

Jorun Boklöv (Life de Luxe) har skrivit en B-uppsats i Medie- och kommunikationsvetenskap, Umeå Universitet, där hon speciellt studerat fyra svenska stickbloggare för att utröna hur kommunikationen på dessa förs.

Uppsatsen heter Ett handstickat nät - Verktyg och strategier för att skapa nätgemenskap, och hur de används av fyra svenska stickbloggare (PDF).

Begreppet stickbloggare förklaras på sid 5 (noten) som bloggar som helt eller delvis handlar om stickning..

Sammanfattningen är som följer


Bloggar beskrivs ofta med utgångspunkt i den publicerade texten: daterade inlägg (med eller utan länkar) i omvänd kronologisk ordning. Det finns många som upplever att den sociala sidan av bloggandet är en nog så viktig del av dess funktion för både bloggaren och läsarna. I den här uppsatsen har jag tittat närmare på nätgemenskap och hur en känsla av gemenskap skapas på bloggar. Jag har utgått från svenska stickbloggar, en liten sub-grupp i den svenska bloggosfären.

Frågorna jag utgått från är:
· Vad karaktäriserar en nätgemenskap?
· Vilka verktyg och strategier anses stärka banden i en bloggbaserad nätgemenskap?
· Hur används dessa verktyg och strategier bland svenska stickbloggare?

Nätgemenskaper kan sägas uppstå varhelst människor samlas online kring ett gemensamt intresse. Internet gör det enkelt att knyta många svaga band med andra.

De gemenskapsskapande verktyg som används flitigast i bloggar är kommentarsfunktionen och praxisen att samla rekommenderade länkar i en bloggroll. De gemenskapsskapande strategier jag funnit belägg för är att tala direkt till läsarna, att visa uppskattning och berömma samt att visa upp skicklighet. Strategin att skriva på ett inställsamt sätt är ännu tydligare i kommentarerna än i inläggen.

När man talar om dagboksliknande bloggar innebär det inte att bloggaren skulle vara omedveten om sin publik. I undersökningsmaterialet markeras tydligt att skribenten skriver med en publik i åtanke.

Ser man enbart till kommentarerna är bloggandet en angelägenhet för bloggare, det är i stor utsträckning de som kommenterar andra bloggares inlägg.


Uppsatsen kan vara intressant även för sådana som inte är intresserad av stickning eftersom diskussionen mestadels förs på ett generellt plan.

En fråga att ställa är om man direkt kan generalisera resultaten till andra typer av privatbloggar, t.ex.
- mer generellt om mode
- politik/debattbloggar
- dagboksnära bloggar
- teknik/vetenskapsbloggar
- reklambloggar
- etc.

Vilka likheter/skillnader finns i sättet att kommunicera inom respektive community? Jag förutsätter - åtminstone för diskussionens skull - att det faktiskt finns skillnader mellan dessa olika typer av communities.


Hoppas att Jorun sedan går vidare och gör en större social nätverksanalys av den svenska stickkommuniteten. (Jorun refererar till nämnda sida samt till det projekt som tyvärr aldrig blev av - Projektförslag:
Social nätverksanalys av den svenska bloggosfären - främst p.g.a. att det då - anno 2003 - var väldigt tungt att ta fram underlaget för vem som länkar till vem inom den svenska bloggosfären.)


Grattis till betyget, Jorun!

Posted by hakank at 07:14 EM Posted to Blogging | Social Network Analysis/Complex Networks | Comments (0)

juni 09, 2008

Sydsvenskan: Dagens hälsoprognos (med avseende på vädret)

På sin vädersida har Sydsvenskan en intressant länk "Dagens hälsoprognos" (kräver Flash). Programmet som poppar upp visar hur olika psykiska/fysiska tillstånd påverkas av hur vädret är just nu eller hur det har/kommer att förändras.

Följande "hälsoväder" rapporteras:
- Förkylning
- Huvudvärk
- Migrän
- Nedstämdhet
- Ledbesvär
- Sömnlöshet

T.ex. så kan man se att i södra Sverige finns det just nu följande väderrelaterade risker:
- liten risk för förkylning
- hög risk för huvudvärk
- hög risk för migrän
- ingen risk för nedstämdhet
- ingen risk för ledbesvär
- mycket hög risk för sömnlöshet.

Hur respektive tillstånd påverkas av vädret beskrivs kortfattat i programmet.


Källkritik
Eftersom jag inte sett denna typ av program förut och verkligen inte är något expert inom området (väder och hälsa) var jag tvungen att kolla lite mer om vem som står bakom.

Det är SMHI (som knappast tarvar någon presentation) och ett - för mig okänt - företag som heter Insun som tagit fram programmet i samarbete med Sydsvenskan.

Själva programmet Hälsoprognosen (presentation etc) har Insun tydligen tagit fram. De presenterar det så här på sin sajt:


Hälsoväder (bioväder) med väderprognos. En hälsoprognos som visar hur vädret påverkar din hälsa.

Denna produkt innehåller två delar: Hälsovädret samt en kompletterande Väderprognos (femdygns). Väderprognosen, som även innehåller meteorologens vädersammanfattning och en förklaring till vädersymbolerna, är tänkt som ett stöd till Hälsovädret. Detta för att lätt kunna jämföra relationen mellan de två. Hälsovädret ger en indikation på hur vissa hälsotillstånd (förkylning, huvudvärk, migrän, nedstämdhet, ledbesvär och sömnlöshet) kan påverkas av vädret de kommande dagarna. Förklaringar till detta redovisas även i textform. Hälsoprognosen kommer inom kort att kompletteras med en pollenprognos och UV.

Företaget presenterar sig så här:


Insun AB är ett produktionsbolag som, under eget varumärke, levererar informations- eller underhållningsrelaterade produkter till organisationer och företag. Produkterna, som i huvudsak är väderrelaterade, kombinerar information och rörlig grafik med inriktning på ny media.

Det låter i alla fall vettigt.


Noter
Jag vet inte hur pass väl detta stämmer, hur vetenskapligt det är eller om det endast är en "underhållningsrelaterad" produkt. Idealet vore naturligtvis att göra en vetenskaplig undersökning där man t.ex. varje morgon i ett par veckor känner efter hur man mår med avseende på de olika tillstånden och sedan kontrollerar hur bra prognosen stämde (eller med tillbörlig förskjutning i tiden). Det räcker inte att som jag gjort, att gå in och kolla endast då jag känner mig med huvudvärk eller sömnbesvär.

Intressant nog ger sökningen insun hälsoprognos på google exakt 2 träffar (eller 8 expanderade), samtliga till Insun-sajten.

Posted by hakank at 09:18 EM Posted to Sajter | Comments (0)

juni 06, 2008

Blogglunch söndagen den 15/6 kl 13.00 samt Markovgenererade bloggträffsammanställningar

Zyrenna-Åsa manar till Blogglunch söndagen den 15/6 kl 13.00, naturligtvis på restaurangen Kin Long. Meddelena Åsa om du tänker komma.


Med anledning av en semantisk förrvirrning angående tidens riktning i en första version av kallelesen skriver hon i kommentarsflödet:


Någon borde testa [att skriva refererat för framtiden]. Skriva referatet i förväg och sedan jämföra med utfallet.

Sammanställningar om redan hända bloggträffar har gjorts. Men att skapa sammanfattningarna innan? Detta kändes som en utmaning!

Eftersom jag är alldeles för lat för att fantisera fram diskussionerna på en hel bloggareträff gjordes det näst bästa: utgick från de redan skriva sammanfattningarna. Det blev det Markovgenerering - inte helt förvånande för den som följt med ett tag. Se t.ex. Generering av Nobelpris-motiveringar (Markov såklart) för mer om Markovgenerering av texter.

Det aktuella programmet som skapar bloggträffsammanfattningar är Markovgenererade bloggträffsammanfattningar.

Om texten inte upplevs vara helt korrekt svenska, föreställ då att författaren är smått förvirrad, berusad eller skriver aningen för snabbt . Eller helt enkelt är poetiskt kryptisk, en kryptopoet .

Posted by hakank at 08:43 EM Posted to Bloggmiddagar | Språk | Statistik/data-analys | Comments (1)

juni 05, 2008

Mats Anderssons tävling kring fotbolls-EM 2008 - ett MiniZinc-genererat tips

Mats Andersson har tidigare haft flera roliga tävlingar. Inför fotbolls-VM 2006 var det en tävling där man skulle gissa resultat i matcherna.

Eftersom mitt kunnande om fotboll var synnerligen begränsat valde jag en enkel metod genom att skapa ett beslutsträd för hur resultaten skulle bli. Och kom naturligtvis sist.

Inför fotbolls-EM (som alltså startar på lördag) har Mats en ny tävling, och den vill man ju inte missa.

Constraint programming-modell i MiniZinc

Eftersom kunnandet kring fotboll fortfarande är (ännu mer synnerligen) begränsat kan det inte vara frågan om att göra några bedömningar kring hur matchresultaten kommer att bli.

Denna gång tänkte jag istället parasitera på Mats fantastiska fotbollskunnande och utnyttja det tips han själv gjort. För detta har skapats en modell i constraint programming-systemet MiniZinc. Modellen finns här och visas även nedan.

Modellen bygger på Mats tips med följande villkor.

Möjligen är några av villkoren lite väl begränsande men har fördelen att det inte blir så många lösningar (om man t.ex. skulle göra någon form av okulärbedömning av dem, vilket inte gjorts här, så det spelar egentligen inte någon roll hur många lösningar som genereras)

1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips.
Kommentar: Om Mats anser att ett lag vinner så gör jag det också. Mats borde veta sådant.

2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
som för Mats tips.
Kommentar: Detta är för att få ner antalet möjliga lösningar.

3) Inga resultat får vara exakt samma som Mats.
Kommentar: Egentligen borde man tillåta att några resultat är samma som Mats, men det blir roligare så här.

4) Det får vara maximalt 5 mål per match.
Kommentar: Kanske det skulle vara maximalt 6 mål, eller 7?


Det finns 29 olika lösningar till detta problem. Redan innan jag tittade på resultaten beslöt jag mig för att ta den sista lösningen som solvern Gecode fz (version 1.2.1) genererade.

Mitt tips

Här är alltså mitt tips till fotbolls-EM 2008.

1. Schweiz - Tjeckien 2-2
2. Portugal - Turkiet 1-0
3. Österrike - Kroatien 0-1
4. Tyskland - Polen 1-2
5. Rumänien - Frankrike 1-3
6. Holland - Italien 1-2
7. Spanien - Ryssland 1-0
8. Grekland - Sverige 1-1
9. Tjeckien - Portugal 1-3
10. Schweiz - Turkiet 1-1
11. Kroatien - Tyskland 0-0
12. Österrike - Polen 1-3
13. Italien - Rumänien 2-0
14. Holland - Frankrike 0-1
15. Schweiz - Portugal 0-1
16. Turkiet - Tjeckien 1-1
17. Sverige - Spanien 1-3
18. Grekland - Ryssland 1-3
19. Österrike - Tyskland 0-3
20. Polen - Kroatien 0-1
21. Holland - Rumänien 1-0
22. Frankrike - Italien 1-3
23. Grekland - Spanien 1-4
24. Ryssland - Sverige 0-1


MiniZinc-modellen


Här nedan visas MiniZinc-modellen för problemet. (webb-versionen kan ha några små skillnader.)


%
% MiniZinc-modell för Mats Anderssons tävling om resultatet i fotbolls-EM 2008.
%
% För beskrivning av tävlingen se:
% http://www.mats-andersson.se/blogg/show.asp?svarsID=1956
%
%
% Min variant bygger på Mats tips med följande villkor:
%
% 1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips
% (om Mats anser att ett lag vinner så gör jag det också. Mats borde veta
% sådant).
% 2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
% som för Mats tips
% 3) Inga resultat får vara exakt samma som Mats.
% 4) Det får vara maximalt 5 mål per match.
%
% Med dessa begränsningar finns det 29 olika lösningar.
% Det beslöts innan lösningarna studerats att ta den sista lösningen
% som solvern Gecode fz (version 1.2.1) genererade.
%

%
% Model created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

int: n = 24; % antal fotbollsmatcher
array[1..n, 1..2] of 0..4: m; % Mats tips
array[1..n, 1..2] of var 0..4: h; % mitt tips

int: m_sum = sum(i in 1..n) (m[i,1] + m[i,2]); % totalt antal mål i Mats tips
var int: h_sum; % total antalet mål i mitt tips

solve satisfy;

constraint
forall(i in 1..n) (
% förhållandet i mål mellan lagen ska vara samma som Mats tips
m[i,1] - m[i,2] = h[i,1] - h[i,2]

/\ % max 5 mål per match
h[i,1] + h[i,2] <= 5
)
/\ % inga matcher får ha exakt samma resultat som Mats
sum(i in 1..n) (
bool2int(
m[i,1] = h[i,1] /\ m[i,2] = h[i,2]
)
) = 0

/\ % totalt antal mål i mitt tips
h_sum = sum(i in 1..n) (
h[i,1] + h[i,2]
)
/\ % totalt antal mål ska vara samma i Mats och mitt tips
h_sum = m_sum
;

output
[
if j = 1 then "\n" ++ show(i) ++ ": " else " " endif ++
show(h[i,j])
| i in 1..n, j in 1..2
];


%
% Mats tips
%
m = [
1,1, % 1. Schweiz - Tjeckien 1-1
2,1, % 2. Portugal - Turkiet 2-1
1,2, % 3. Österrike - Kroatien 1-2
0,1, % 4. Tyskland - Polen 0-1
0,2, % 5. Rumänien - Frankrike 0-2
0,1, % 6. Holland - Italien 0-1
2,1, % 7. Spanien - Ryssland 2-1
0,0, % 8. Grekland - Sverige 0-0
0,2, % 9. Tjeckien - Portugal 0-2
0,0, % 10. Schweiz - Turkiet 0-0
2,2, % 11. Kroatien - Tyskland 2-2
0,2, % 12. Österrike - Polen 0-2
3,1, % 13. Italien - Rumänien 3-1
1,2, % 14. Holland - Frankrike 1-2
1,2, % 15. Schweiz - Portugal 1-2
0,0, % 16. Turkiet - Tjeckien 0-0
0,2, % 17. Sverige - Spanien 0-2
0,2, % 18. Grekland - Ryssland 0-2
1,4, % 19. Österrike - Tyskland 1-4
2,3, % 20. Polen - Kroatien 2-3
2,1, % 21. Holland - Rumänien 2-1
0,2, % 22. Frankrike - Italien 0-2
0,3, % 23. Grekland - Spanien 0-3
1,2 % 24. Ryssland - Sverige 1-2
];

%
% End of MiniZinc model.
%


Notera att MiniZinc inte hanterar strängar speciellt bra så resultatet presenteras endast så här:


1: 2 2
2: 1 0
3: 0 1
4: 1 2
5: 1 3
6: 1 2
7: 1 0
8: 1 1
9: 1 3
10: 1 1
11: 0 0
12: 1 3
13: 2 0
14: 0 1
15: 0 1
16: 1 1
17: 1 3
18: 1 3
19: 0 3
20: 0 1
21: 1 0
22: 1 3
23: 1 4
24: 0 1


Slutord


Från början tänkte jag använda någon form av statistisk metod som analyserade Mats tips för att skapa mitt eget tips. Ovanstående angreppssätt ligger definitivt mer i linje med det jag håller på med nu.

Naturligtvis ska man se allt detta som en liten etyd i constraint programming.

Posted by hakank at 09:18 EM Posted to Constraint Programming | Pyssel | Comments (0)

juni 02, 2008

Nya MiniZinc-modeller, flera global constraints, däribland clique

Sedan anteckningen Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem i förra veckan har några fler modeller skapats. Samtliga modeller finns att ladda ner från My MiniZinc page.

Denna gång är det förvisso några pyssel men fokus har varit att implementera global constraints från den fantastiska samligen Global Constraints Catalogue.

Pyssel

Samtliga desa pyssel är från de kommenterade exemplen i det första kapitlet från boken Problem Solving Through Recreational Mathematics av Bonnie Averbach och Orin Chein (ISBN: 9780486409177).

Av enkelhet är filerna döpta efter exemplets namngivning. Den specifika problemformuleringen finns i mzn-filen.
- Exempel 1.2. Enkelt problem om tre damer som sitter vid ett bridgebord och byter kort. Det gäller att avgöra hur de sitter.
- Exempel 1.3. Här ska man avgöra namnet på hustrur och hästar till 5 olika män.
- Exempel 1.4. Svårare variant av 1.2. Fem män med olika yrken spelar poker. Här gäller det att avgöra yrke och position vid bordet.
- Exempel 1.5. Nim, ganska generell. Problemet är att avgöra vilken strategi som garanterar vinst, men här visas endast alla giltiga drag (man får alltså dra egna slutsatser om strategier).

Global constraints etc

Så har det skapats några global constraint som finns i Global Constraints Catalogue eller sådana som är lite mer generella. Samtliga modeller innehåller ett enkelt exempel, för det mesta är det exemplet som finns i katalogen.


clique
Jag börjar med clique eftersom det är en av mina favorit-constraints, och att det tog en stund att får det rätt.

Modell och exempel finns i clique.mzn. Se även Global constraint-entry.

clique är ett begrepp från grafteorin som innebär att samtliga noder inom denna klick är kopplade till varandra. (Det är ungefär det vi menar med det vardagliga "klick" för att beskriva en social struktur, ett gäng, ett kotteri, etc.)

Ibland är problemet att hitta den största klicken i en graf, men ibland räcker det bara med en klick, vilken som helst av en viss storlek.

Exempel på clique
Låt oss leka lite med exemplet från GC-katalogen. Det är 5 noder som har följande kopplingar:

1 är kopplad till 2,4
2 är kopplad till 1,3,5
3 är kopplad till 2,5
4 är kopplad till 1,5
5 är kopplad till 2,3,4

Modellen arbetar med en matrisrepresentation av grafen, och visas i koden nedan.

Här är hela modellen.


include "globals.mzn"
int: num_nodes;
array[1..num_nodes, 1..num_nodes] of 0..1: g; % the graph (as a matrix)

var set of 1..num_nodes: s; % the clique
var int: c = card(s); % size of the clique

%
% clique(clique size, the clique, the graph)
%
% Note: I have added the clique in the parameters list.
%
predicate clique(var int: c, var set of int: s, array[int, int] of int: g) =
let {
int: n = card(index_set_1of2(g)),
array[1..n] of var bool: s_bool
}
in
link_set_to_booleans(s, s_bool)
/\
forall(i,j in 1..n where i != j) (
(s_bool[i] /\ s_bool[j]) -> ( g[i,j] > 0)
)
/\
c = card(s)
;

solve maximize c;

constraint
% s = {1,2,3} /\ % Exempel 1
clique(c, s, g)

% /\ % Example 2
% c >= 2
;

%
% data
%
num_nodes = 5;
g = [
% 1 2 3 4 5
1,1,0,1,0, % 1
1,1,1,0,1, % 2
0,1,1,0,1, % 3
1,0,0,1,1, % 4
0,1,1,1,1, % 5
];

Exempel på några problem med clique

Med constrainten clique kan man nu lösa bl.a. följande problem:

1. Är {1,2,3} en klick i denna graf?

solve satisfy;

constraint
s = {1,2,3}
/\
clique(c, s, g)
;

Svaret är: "No solution". Det är alltså ingen clique.


2. Visa samtliga klickar som är större än 2.
Det görs med denna constraint-sektion:


clique(c, s, g)
/\
c >= 2

dvs här har vi inte fixerat s (själva klicken). En massa lösningar skrivs nu ut.


3. Vilken är den största klicken och hur stor är den?
Här används solve maximize eftersom vi är ute efter den största av något (nämligen klickens storlek, c). För att effektivisera sökningen kan man begränsa till att undersöka klickar av storlek 2 eller större.


solve maximize c;
% ...
constraint
clique(c, s, g)
/\
c >= 2
;

Svar: Den största klicken är {2,3,5} och den är över 3 noder.
Not: Med solve maximize får man endast en lösning. Det är möjligt att det finns andra cliques som är lika stora. Då måste man ändra modellen till:

solve satisfy;
% ...
constraint
clique(c, s, g)
/\
c >= 3
;

I denna graf finns dock ingen annan clique med tre eller flera noder än {2,3,5}.


Noteras kan att det i modellen även finns en slumpgenererad graf på 100 noder. I den grafen finns 3515 olika klickar >= 3 (dock inklusive "subklickar"). Det finns fyra klickar av storlek 6. Det sistnämnda problemet tar cirka 5 sekunder att lista ut.

Övriga global constraints

Här är listingen av några andra global constraints. Beskrivning och länk till global constraints-katalogen finns i modellen.

* all_differ_from_at_least_k_pos

* all_min_dist

* alldifferent_cst

* alldifferent_except_0

* alldifferent_modulo

* alldifferent_on_intersection

* alldifferent_partition

* alldifferent_same_value

* alldifferent_soft
Modellen implementerar två varianter:
- soft_all_different_ctr
- soft_alldifferent_var

* change

* circular_change

* common
Modellen implementerar:
- common
- used_by

* count_ctr
Notera att MiniZinc har en count constraint i globals.mzn, men den är inte så generell som katalogens. Min modell är mer generell.

* distance_between

* inflexions

* k_alldifferent

* longest_change

* nchange

* period

* sum_ctr

Och så några generella constraints som inte finns i GC-katalogen:

* runs: Antalet runs i en vektor. En run är ett segment av en vektor som består av samma värde.

* fix_points: Antalet fixpoints i en vektor, dvs antalet positioner där värdet är samma som dess position.

Matris-operationer

Modellen transpose innehåller några matrisoperationer: - transpose - scalar_add - scalar_mult

Det var dessa matrisoperationer som jag behövde för tillfället.

En trevlig sak med constraint-programming är - som vi sett ovan och som jag skrivit om tidigare - att man "vända på" ett problem. I transpose-modellen finns en 4x4-matris (x) som man gör en transpose på (roterar 90 grader), varpå man gör en skalär addition på dessa två matriser (originalmatrisen + den transponerade).

Låt x vara originalmatrisen, t vara den transposerade matrisen och slutligen p vara resultatet av p = x + t (skalär addition av x och p).

Då kan vi lösa några olika problem.

1. Givet x, räkna ut p
Detta är det normala problemet: Räkna ut p om vi har x (och därmed t).


int: n;
array[1..n, 1..n] of var 1..10: x;
array[1..n, 1..n] of var 1..10: t;
array[1..n, 1..n] of var int: p;

solve satisfy;

%
% definition av transpose och scalar_add
% ....

constraint
x = [1,1,1,1,
2,2,2,2,
3,3,3,3,
4,4,4,4]
/\
transpose(x,t)
/\
scalar_add(x,t,p)
;

Här räknas både t och p ut med ledning av de värden som vi givit x.


2. Givet p, räkna ut x och t
Det är nu det börjar bli skoj!

Vi låter nu x och t vara variabler (dvs deklarerar dem inte) och fixerar endast p (resultatet av x + t). Hur många olika lösningar x + t = p med en fix matrix p finns det?


% ....

constraint
transpose(x,t)
/\
scalar_add(x,t,p)
/\
p =
[2, 3, 4, 5,
3, 4, 5, 6,
4, 5, 6, 7,
5, 6, 7, 8]

Svar: Det finns 2880 lösningar.


Slutord (för dagens skörd)


Global Constraint Catalogue innehåller för närvarande över 300 global constraints och jag har bara implementerat en bråkdel av dem. Flera kommer med stor sannolikhet att modelleras, i alla fall sådana som verkar nyttiga/skoj och går att göra i MiniZinc. Det finns några mer avancerade grafteoretiska constraints som är svåra att implementera i MiniZinc, som saknar rekursioner och dynamiskt växande listor.


Posted by hakank at 08:02 EM Posted to Constraint Programming | Comments (0)

MiniZinc/FlatZinc version 0.8 släppt

Häromdagen släpptes en ny version av MiniZinc (se även My MiniZinc page), det constraint programming-system som jag håller på med just nu.

Den nya versionen finns här.

Förändringar
I NEWS beskrivs alla de förändringar som gjorts sedan version 0.71.

Notera att detta endast gäller MiniZinc/FlatZinc. Ändringarna är ännu (2008-06-02) inte införda för de andra solvers, dvs Gecode fz respektive ECLiPSe's ic, fd eller eplex. Jag väntar med spänning på detta.


De praktiskt viktigaste ändringarna är:

* ny deklaration av vektorer
vektorer (arrays) i högre dimensioner konverteras inte längre automatiskt till en "multi-array". Man måste deklarera dimensionen explicit.

Exempel: För att deklarera en 2-dimensionell vektor (dvs en matris) gjorde man tidigare så här:

int: n;
array[1..n, 1..n] of int: x;
% en massa andra saker
% ...
n = 3;
% deklarationen (gamla sättet)
x =
[1,2,3,
4,5,6,
7,8,9];
% ....

Nu måste man istället skriva deklarationen så här:

% ...
x =
[|1,2,3,
|4,5,6,
|7,8,9|]

Dvs man måste omsluta varje rad med ett "|"-tecken. Notera att "parenteserna" inte får delas upp utan man måste skriva "[|" respektive "|]". Gör man inte så blir det ett kryptiskt fel.


* FlatZinc har flera solvers
För FlatZinc (den solver som kommer med MiniZinc-distributionen) är default solver fd, en finite domain-solver och det var den endast som fanns tillgänglig i version 0.7.1.

Följande solvers finns nu att tillgå i FlatZinc. Från kommandot flatzinc --help:

Solver Selection Options:
-s , --solver , --solver-backend
Select the solver(s) and evaluation algorithm that should be used.
Valid solver backends are: `fd', `sat', `mip', `fdmip', `colgen',
`skp' and `ttt'. (The default is `fd'.)

--mip-solver
Use the specified solver as the default MIP solver.
Supported MIP solvers are: osi-cbc.

--sat-solver
Use the specified solver as the default SAT solver.
Supported SAT solvers are: minisat.

--colgen-mip-solver
Use the specified solver as the default MIP solver for the column
generation backend. (Note that this choice will be overridden by
a `colgen_master_solver' annotation in the model.)
Supported column generation MIP solvers are: osi-cbc.

--colgen-approx-solver
Use the specified approximate linear solver with the column
generation backend. (Note that this choice will be overridden by
a different choice inside a `colgen_master_solver' annotation in
the model.)
Supported approximate linear solvers are: osi-volume.

Speciellt intressanta är fd, mip (mixed integer programming, använder Coin:s osi-cbc) och fdmip (en hybrid mellan dessa).

Det antyds att allt utom fd och möjligen mip/fdmip bör anses som odokumenterade features.

Tyvärr generar flatzinc-programmet endast en lösning. Hoppas att man ändrar detta i en senare version så att alla lösningar visas (som Gecode fz och ECLiPSe's ic/fd gör).


* show_cond
När man skriver ut resultaten, med show(variabel) inom output, har man endast kunnat för if-satser på fixa variabler (dvs par-deklarerade variabler), vilket har begränsat uttryckfullheten ordentligt.

I version 0.8 finns det möjlighet att med show_cond göra en dynamisk kontroll av icke-fixa variabler. Exempel: Här skriver vi endast ut de värden som tillsammans blir 14, dvs de som har värdet 1 i x-vektorn. MiniZinc/FlatZinc skriver ut 2 3 4 5.

int: n = 10;
array[1..n] of var 0..1: x;

solve satisfy;
constraint sum(i in 1..n) (x[i]*i) = 14;

output [
show_cond(x[i] > 0, i, "") ++ " "
| i in 1..n
];


* vektorer är 1-baserade
I äldre versionen var alla vektorer 0-baserade (dvs första element räknades från 0). Nu börjar man på 1 istället. Normalt behöver man inte bry sig om, detta förutom då man arbetar med "slices" som skickas till ett predikat.


Mina exempel
Mina MiniZinc-modeller på My MiniZinc page är fortfarande i gamla 0.7.1-formatet, och jag kommer att vänta med att konvertera dem till version 0.8 tills åtminstone en av de två andra solvers (Gecode fz respektive ECLiPSe's varianter) stöder denna version. Då är det förmodligen endast vektor-deklarationerna som kommer att ändras (men kanske en och annan show_cond läggs till).


Wrapper
För övrigt har jag skapat en flexibel Perl-wrapper kring de olika solvers. Det har stöd för både 0.7.1 och den nya 0.8. Och man kan från kommandoraden t.ex. ändra parametrar, lägga till constraints, ändra antal lösningar som ska visas etc.

Jag har ännu inte några planer att lägga upp detta program publikt, men maila mig gärna om du är intresserad av det. Som en teaser visas två exempel som faktiskt inte är helt ovanliga:

mzx.pl model.mzn --solver minizinc --new --option "--solver fdmip" --param "n=10;k=3"

mzx.pl model.mzn --solver ic --param "n=100;k=12" --num_solutions 10

Det första exemplet kör den nya versionen av MiniZinc (oftast SVN-versionen) med solvern fdmip, och ändrar parametern n till 10 samt parametern k till 3. Det andra exemplet kör ECLiPSe's ic-solver med andra parametrar samt visar endast de 10 första lösningarna.


Posted by hakank at 06:10 EM Posted to Constraint Programming | Comments (0)