hakank.blogg

(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

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

• Coins grid problem: Tony Hürlimann: "A coin puzzle - SVOR-contest 2007".
  
• de Bruijn sequences: both "normal" and "arbitrary" de Bruijn sequences.
  Usage: java DeBruijn base n (m)
  where base is the base to work with, n is the "bit length" and m the optional length of the sequence (default length is base^n).
• Diet: Simple diet problem.
• Furniture moving: Simple task optimization using cumulative.
• HakankUtil.java: some utilities. Is needed for some of these models
• Least diff problem: alphametic puzzle, minimize the difference ABCDE-FGHIJ where A..J is integers 0..9 (all different)
• Minesweeper: Minesweeper problem.
  Problem files for the Minesweeper program.
  Usage: java Minesweeper problem file
  
  • Problem 0 from Gecode minesweeper.cc
  • Problem 1 from Gecode minesweeper.cc
  • Problem 2 from Gecode minesweeper.cc
  • Problem 3 from Gecode minesweeper.cc
  • Problem 4 from Gecode minesweeper.cc
  • Problem 5 from Gecode minesweeper.cc
  • Problem 6 from Gecode minesweeper.cc
  • Problem 7 from Gecode minesweeper.cc
  • Problem 8 from Gecode minesweeper.cc
  • Problem 9 from Gecode minesweeper.cc
  • From "Some Minesweeper Configurations",page 2
  • From "Some Minesweeper Configurations",page 3
  • From Richard Kaye: How Complicated is Minesweeper?, splitter (131072 solutions)
  • From Richard Kaye: How Complicated is Minesweeper?, wire
• QuasigroupCompletion.java: Quasigroup completion problem.
  Problem files:
  
  • quasigroup1.txt
  • quasigroup2.txt
  • quasigroup3.txt
  • quasigroup4.txt
  • quasigroup5.txt
  • quasigroup6.txt
  • quasigroup7.txt
  • quasigroup8.txt
  • quasigroup9.txt
• Seseman convent problem: a simple recreational mathematics puzzle.
• Young Tableuax: Young tableaux and partitions

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

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

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

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

Puzzles, small and large

• Enigma birthday magic puzzle (#1448)
  
• Enigma planets puzzle (#1396)
  
• Enigma portuguese squares puzzle (#1476)
  
• Digits of the square problem
  
• A dinner problem
  
• Futoshiki puzzle
  
• Enigma ENIGMA / M = TIMES puzzle (#1000)
  
• Enigma What the hex? puzzle (#1001)
  
• Enigma Reverse Fahrenheitpuzzle (#1293)
  
• Enigma circular chain puzzle (#985)
  
• Word golf (word chain)
  
• 3 letter words for Word golf
  
• 4 letter words for Word golf
  

Global constraints

• cond_lex_cost
  
• cond_lex_less, även cond_lex_lesseq, cond_lex_greater, cond_lex_greatereq
  
• in_relation
  
• in_same_partition
  
• strictly_decreasing, även strictly_increasing and decreasing
  
• subsequence
  
• sum_set
  
• symmetric
  
• symmetric_alldifferent
  

Operations research, linear programming, integer programming

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

Combinatorial problems

• K4 P2 Graceful Graph
  
• K4 P2 GracefulGraph, version 2 (en mer generell modell)
  
• Minesweeper
  
• Quasigroup existence problem 3, Idempotent (CSPLib)
  
• Quasigroup existence problem 3, NonIdempotent (CSPLib)
  
• Quasigroup existence problem 4, Idempotent (CSPLib)
  
• Quasigroup existence problem 4, NonIdempotent (CSPLib)
  
• Quasigroup existence problem 5, Idempotent (CSPLib)
  
• Quasigroup existence problem 5, NonIdempotent (CSPLib)
  
• Quasigroup existence problem 6 (CSPLib)
  
• Quasigroup existence problem 7 (CSPLib)
  
• Quasigroup completion problem
  
• Quasigroup completion problem.mzn , med följande instanser
  
  • Gomes Shmoys, sid 3
    
  • Gomes Shmoys, sid 7
    
  • Martin Lynce
    
  • from Global Constraint Catalogue
    
  • Gomes demo 1
    
  • Gomes demo 2
    
  • Gomes demo 3
    
  • Gomes demo4
    
  • Gomes demo 5
    
  
  
• Young tableaux
  

Other models

• Birthday paradox
  
• Catalan numbers
  
• Factorial (utan att använda prod-predikatet, som f.n. inte funkar)
  
• Game of Life
  

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

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).

• Alien tiles (from An Alien IP)
• Elevator puzzle model (from A Tokyo Elevator Puzzle)
• Elevator 6 3 puzzle (from A Tokyo Elevator Puzzle)
• Elevator 8 4 puzzle (from A Tokyo Elevator Puzzle)
• Fairies problem (from Puzzle—O.R. with the Fairies)
• Gunport problem 1 (from The Gunport Problem)
• Gunport problem 2 (from The Gunport Problem)
• Nimatron problem (from A Nimatron)
• Sangraal (from Fantasy OR)
• Tank Attack Puzzle (from A Tank Attack Puzzle)
• Touching numbers puzzle (from The Traveling Space Telescope Problem)
• Tripuzzle 1 (from Tri-Puzzle: A Three-Cornered Conundrum)
• Tripuzzle 2 (from Tri-Puzzle: A Three-Cornered Conundrum)

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

• Narcissistic numbers
  
• Clock Triplets
  
• Dividing the spoils
  
• Hundred Fowls puzzle
  

Posted by hakank at 07:53 EM Posted to Constraint Programming | Matematik | Pyssel

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

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

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
#

# 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) ])

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.
#

#
# 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

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

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)

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

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

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.

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

include "globals.mzn";

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

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

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

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


%
% 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
%

%
% 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

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

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

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

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)

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

* 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

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;

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?


% ....

Svar: Det finns 2880 lösningar.

Slutord (för dagens skörd)

Posted by hakank at 08:02 EM Posted to Constraint Programming

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'.)

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;

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

maj 26, 2008

Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem

Här är några MiniZinc-modeller som skapats sedan förra anteckningen om sådana modeller.

Samtliga modeller att tilnå finns via My MiniZinc page.

Digital Tomography samt några varianter
Det problem som skrevs om i Ett litet april-pyssel löste jag själv med en digital tomografi-teknik. Se modellen tomography.mzn.

En viss förklaring av digital tomografi finns på sidan Open problems in discrete tomography. Sidan innehåller några Java-applets som man själv kan leka med.

I ovanstående modell var det bara en färg ("svart") man arbetade med, men problem kan generaliseras till flera färger. En sådan generalisering görs i tomography_n_colors.mzn, och som exempel modelleras bl.a. "The two atom problem".

Solitaire Battleship (wikipedia) är en variant av "Sänka skepp" som har liknande förutsättningar som digital tomografi. MiniZinmodell: solitaire_battleships.mzn.

SONET problem
SONET-problemet är ett standardproblem inom constraint programming som jag inte hittat någon MiniZinc-modell av så därför rullade jag en egen: sonet_problem.mzn.

För mer om problemet se t.ex. Simplified SONET Problem (Postscript-fil).

A Coin Puzzle
Detta problem på en rätt stor "grid" beskrivs utförligt av Tony Hürlimann i A coin puzzle - SVOR-contest 2007 (PDF).

Min MiniZinc-implementation av problemet finns i coins_grid.mzn. Ett tips är att låta en linear programming-solver lösa problmet, dvs ECLiPSe:s eplex eller MiniZincs nya option "--solver mip". Då löses det blixsnabbt.

Några Operations Research-problem
I John Hooker:s föreläsning A framework for integrating optimization and constraint programming finns några OR-problem som imlementerats:

- freight_transfer.mzn

- product_configuration.mzn

Ett skoj fotbollspussel
I Yahoo!-gruppen lp_solve kom ett skoj problem. Tyvärr krävs inloggning till gruppen, så MiniZinc-modellen innehåller hela meddelandet.

Problemet (som är en knapsack-variant) går ut på att optimera köp av brittiska fotbollsspelare med vissa krav:
- budgeten är på 30 miljoner (pund)
- man måste köpa ett visst antal spelare (målvakt, försvarsspelare etc) för en given kostnad per spelare
- man ska maximera den totala kostnaden men inte komma över budgeten.

Problemet uttrycks i flyttal men jag har valt att arbeta med heltal av två skäl:
- för tillfället är det fler MiniZinc-solvers som klarar av helttal än flyttal

- när det gäller spelarkostnader är inte orimligt att anta hela pund.

MiniZinc-modellen finns i football.mzn och är ganska generell.

Några andra modeller
- Funktionspartitionering, dvs partionera ett gäng heltal med avseende på en funktion t.ex. modulo-funktionen: modulo_partition.mzn. Det är enkelt att ändra funktion i modellen.

- Beslutsträd. Här modelleras ett fullständigt binärt beslutsträd: decision_tree_binary.mzn.

- Markovkedjor: markov_chains.mzn: Här räknar man ut "stable state" av marknadsandelnarna för tre företagsmärken.

- Yet another recreational schackproblem: peacableArmyOfQueens.mzn.

Raymond Smullyans logiska pyssel
Så till det jag satt med i helgen.

I den underbara boken What is the name of this book? beskriver Raymond Smullyan ett stort antal logiska pyssel, de allra flesta är skapade av Smullyan själv.

Några av de mest kända pysslen från denna bok är "Knights and Knaves"-problemen från kapitel 3 (som heter just "Knights and Knaves"): Alla "knights" talar alltid sanning och alla "knaves" ljuger alltid. Senare i kapitlet kommer även "Normals" med, sådan ljuger ibland och talar sanning ibland, och så tillkommer speciella giftasregler mellan de olika typerna. Problemet är att försöka lista ut vem som är vad med ledtråd av några få ledtrådar.

De allra flesta problemen från kapitel 3 finns modellerade i respektive modell:
- smullyan_knight_knaves.mzn: bara knights och knaves
. Problem 26 till och med 35. (Problem 36, 37 och 38 har av olika skäl inte modellerats.)

- smullyan_knight_knaves_normals.mzn: här finns även normals
. Problem 39 till och med 42 (modellen för 43 är inte korrekt).

- smullyan_knight_knaves_normals_bahava.mzn, med speciella giftoregler mellan knights, knaves och normals. Problem 44, 45 och 46.

Wikipedia har mer info om Knights and Knaves.

Uppdatering något senare
Några fler problem från samma bok:

- De första problemen om Lion och Unicorn från kapitel 4 "Alice in the Forest of Forgetfulness": smullyan_lion_and_unicorn.mzn. Lejon och enhörningar ljuger vissa dagar och talar sanning andra dagar. Här gäller det att lista ut vilken dag de säger olika saker.

- De första problemen från kapitel 5 "The mystery of Portias Caskets" smullyan_portia.mzn.

Posted by hakank at 06:54 EM Posted to Constraint Programming | Pyssel

april 27, 2008

Mitt OpenOffice Calc-/Excel-skov

Som tidigare antytts har jag tidigare kollat in OpenOffice Calc och Excel. IRL har detta till mina vänner beskrivits som mitt OpenOffice/Excel-skov och det har i vissa fall även utlovats en rapport om detta.

Här är en reseskildring över förloppet, kompletterad med några exempel som gjordes då. Samtliga exempel utnyttjar Solver/Problemlösaren eftersom det är den finessen som jag uppskattade mest.

Excel/OpenOffice Calc

Dataanalys har istället gjorts i främst R eller rena standardprogramspråk (C, C++, Java, Perl, Python, Ruby etc) med eller utan numeriska tillägg, eller med matematiska system såsom Maple/Matlab (eller dess kloner såsom MuPAD, Octave) etc etc.

I och för sig har (eller snarare hade eftersom Windowsmaskinen är trött numera) jag tillgång till Excel 2003, men eftersom jag främst är en Linux-människa kollade jag mest in OpenOffice Calc som är valdigt kompatibel med Excel 2003.

Som av en slump sträcklästes först Bill Jelens praktverk Special Edition Using Microsoft Office Excel 2007 (>1000 sidor). Trots att boken är för Excel 2007 är det väldigt mycket som är applicerbart för Calc, framförallt formler och sätt att tänka. (Jag läste dock kursivt de första 300-400 sidorna som pratar om det nya GUI-t för Excel 2007).

Sedan införskaffades Microsoft Office Excel 2007 - Data Analysis and Business Modeling skriven av Wayne Winston. Denna bok innehåller många fler fullständiga och kommenterade exempel (än Jelens bok). De mest intressanta var avsnitten kring planering, simulering etc, framförallt modellerna med linjära-/heltals-modeller.

En asidekommentar i ett av dessa avsnitt hänvisade till Winstons egen bok Operations Research - Applications and Algorithms, och den införskaffades därför (ibland är bokbeställningsbenägenhetströskeln väldigt låg). Det är en alldeles förträfflig introduktion inom området Operations Research (OR, operationsanalys på svenska). För böcker som därefter lästes inom OR, se litteraturlistan i Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller.

Ungefär i samband med testningen av OR-exemplen började jag fundera på hur man implementerade problem såsom SEND + MORE = MONEY och liknande småpyssel i Excel/Calc. En del andra problem implementerades också, vara några presenteras nedan.

Det gemensamma med dessa problem är att de använder Solver/Problemlösaren, en av de mest avancerade funktionerna i systemen. Se vidare nedan under Solver/Problemlösaren.

Ett tag var allting smör och solsken (eller vad det nu heter), men efter ett tag blev begränsningarna i systemet mer och mer tydliga: Excels Solver kan inte hantera fler an 200 beslutsvariabler; den Solver som användes i OpenOffice Calc kan vara långsam och hanterar inte icke-linjära problem (ibland kan man modellera runt denna begränsning men det är ofta rätt trixigt). Det var då jag gick över till att modellera i andra modellspråk, något som beskrivs i Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller.

Solver/Problemlösaren

Kortfattat kan säga att Solver möjliggör lösningar av vissa typ av problem genom att optimera vissa värden på ett smart sätt. Man kan säga att Solver testar en massa olika lösningar och väljer den (eller en av flera) som är bäst givet det kriterium man angivit.

OpenOffice har ingen inbyggd solver, men det ska komma en sådan i version 3. Tills vidare kan rekommenderas det Solver-paket (.oxt-paket) som Kohei Yoshida skapat: Calc Optimization Solver. Tyvärr hanterar det endast linjära problem.

Istället för att förklara detaljerna hur man gör för att använda Solver, länkas här till några bra introduktioner. Jag rekommenderar även att någon av ovan nämnda Excel-böcker studeras (där står mycket annat matnyttigt om Excel). Samtliga beskriver Excels Solver, men det funkar i princip på samma sätt i OpenOffice Calc.

* Teaching Linear Programming using Microsoft Excel Solver. Introduktion i linjär programmering, med instruktion hur man använder Solver.

* Microsofts egen dokumentation: Introduction to optimization with the Excel Solver tool

* Learn to Use the Excel Solver to Make Money-Saving Decisions: Build Models to Allocate Scarce Resources

* (Bok) Paul Cornell: Beginning Excel What-if Data Analysis Tools - Getting Stated with Goal Seek, Data Tables, Scenarios, and Solver.

Några exempel med Solver/Problemlösaren

I dokumenten beskrivs vilka celler/områden som är relevanta för Solver.

För jämförelsens skull länkas även till motsvarande MiniZinc-modell. (Om någon skulle vara intresserad av motsvarande modeller i AMPL är det bara att hojta.)

Not: Inga macros har använts.

Slutord

Posted by hakank at 07:45 EM Posted to Constraint Programming | OpenOffice Calc/Excel | Operations research | Comments (3)

april 26, 2008

Ett litet april-pyssel

För tre år sedan (2005) publicerades ett Aprilpyssel. Det är dags att åter ta upp denna tradition.

Naturligtvis är nedanstående pyssel - på något sätt - kopplat till det jag kollar in just nu, dvs constraint programming/integer programming/MiniZinc.

Denna typ av pyssel har ett specifikt namn - som jag inte avslöjar just nu - och tillhör en grupp mer generella problem (som vad jag vet inte har något speciellt namn, dock med åtminstone ett undantag).

Problem

Betänk följande binära matris (dvs endast 0 och 1 förekommer) där summorna för respektive rader och kolumner visas i fetstil.


1 010
1 010
0 000
  020


Vi sammanfattar respektive summor i två vektorer:

- radsummor: [1,1,0]

- kolumnsummor: [0,2,0].

Dagens pyssel går nu ut på, att givet en radsummavektor och en kolumnsummavektor, lista ut vilken matris som ligger som grund för dessa summor.

Delproblem

Det är två stycken delproblem som vardera på något vis kan ge ledtråd till lösningen av det andra delproblemet.

Delproblem a

radsummor= [0,2,2,2,2,2,8,8,4,4,4,4,4,0]
kolumnsummor = [0,0,0,12,12,2,2,2,2,7,7,0,0,0]


Delproblem b

radsummor = [0,0,8,2,6,4,5,3,7,0,0]
kolumnsummor = [0,0,7,1,6,3,4,5,2,7,0,0]


Ett av dessa problem har jag snott ("kopierat" är en mer korrekt term för detta förfarande) från någonstans, det andra har jag hittat på själv. Ordningen mellan delproblemen, liksom presentationen av dess härlednad i föregående mening, är faktiskt slumpad med ett slumptalsprogram, nämligen R.

Vinnerier etc

Vinnaren i detta pyssel anses den vara som först till pysselledningen:

- p) ger korrekt svar på båda delproblem

- q) samt redogör för hur problemet löstes.

"Till pysselledningen" definieras här som antingen en kommentar i denna blogganteckning, eller ett mail till hakank@bonetmail.com.

Vinnaren erhåller i kommentarerna till denna blogganteckning eller i en separat blogganteckning ett "Bra gjort, X!", där X ersätts av vinnarens namn/handle/smeknamn etc. Möjligen kommer "Bra gjort" att ersättas av synonymiserade uttryck och/eller kompletteras med kraftfullare attribut (såsom "Mycket") då i kombination med erforderliga ändringar av resten av uttrycket för att det ska bli så korrekt svenska som möjligt (byte av stor till liten bokstav etc).

Pysselledningen förbehåller sig att dela ut noll (0) eller flera stilprogram till förslag som ej är korrekt lösta, inkompletta men på något sätt (subjektivt bedömt) förtjänar ett stilpoäng, men även till korrekta lösningar som förtjänar sådan stilpoäng. Negativa stilpoäng kommer inte att delas inte, åtminstone inte officiellt. Eventuella felaktigheter som eventuellt påpekas för eventualla lösningsförslag definieras inte som negativa stilpoäng i detta sammanhang.

Till allt detta kommer vinnaren även att erhålla en av följande vid nästa eller någon (dock endast en) efterföljande IRL-träff (den virtuella glassen är än så länge alldeles för blaskig för att bjuda på):

- glass
- öl
- kaffe
- te
- eller annan motsvarande dryck

Not: Glass/öl/etc kan delas ut av den person som råkar utgöra pysselledningen i helt andra sammanhang och av helt andra skäl. Detta ska då ses som något som är hetl frikopplat från denna pysseltävling.

Lösningens presenterande etc

Slutord

Slutligen: Förutom "Lycka till!" kan noteras (vilket säkert redan gjorts av den observante läsaren) att ovanstående pysselformulering kunde - om omständigheterna vore annorlunda - göras mycket kortare. Men det är de inte så det gjordes inte.

Posted by hakank at 10:25 FM Posted to Constraint Programming | Pyssel | Comments (8)

april 21, 2008

Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller

CP nedan är förkortning för Constraint Programming.

Andreas Larsson frågade följande i kommentaren till MiniZinc-sida samt fler MiniZinc-exempel:

Har du några fina exempel på när sådan här typ av programmering används i näringslivet, dvs. utanför institutionerna och skolsalarna?

Det tänktes först skrivas en rätt kort kommentar som sedan växte till en alldeles egen blogganteckning. Hoppas att du fått svar på din fråga, Andreas.

Kommersiella tillämpningar

Sedan: Jag tillåter mig att utöka svaret lite grand med länkar till saker inom både constraint programming och operations research.

Här är en lista på några kommersiella applikationer av CP:

Applications Of Constraint Programming

Sedan kan man kika på kunderna till några av constraint programming-systemtillverkarna.

Koalog: Clients.

SICStus: Customers. SICStus är en (svensk!) Prolog-implementation (en av de mest kraftfulla) med CP-stöd. Några kunder använder CP-teknologin.

ILOG: ILOG CP med en lång lista på ILOGs kunder. ILOG har dock andra produkter, t.ex. CPLEX som är en av de mest kraftfulla solver för linjär/integer/mixed programmering. ILOGs modelleringsspråk OPL är för övrigt en av inspirationskällorna till MiniZinc.

Mer allmänt kan sägas att många av de problem som studeras inom constraint programming kan mycket väl tillämpas inom näringslivet och har även gjorts även om jag inte kan ge några bättre länkar just nu.

På My MiniZinc page finns ett flertal exempel under rubriken "Operations Research" (se även nedan). Det är några enkla skolexempel på problem där constraint programming-metoden används: schemaläggning, rutt-planering, lagerhantering etc. Flera av dessa exempel har jag tagit från läroböcker i just operations research (länkar till dessa böcker finns nedan). På MiniZincs exempelsida finns flera sådana exempel, och benchmark-katalogen finns en hel del större problem.

(Ja visst ja - och detta har inget med näringslivsimplementationer att göra - jag har ju glömt bort att länka till den obligatoriska Sudoku-lösningen: modellen, data, resultatet. Notera att modellen är för arbiträr dimension, exemplet är för det vanliga 3 x 3-problemet.)

Operations Research

OR använder traditionellt (bl.a.) matematisk programmering, såsom linjär programmering, heltalsprogrammering (integer programming), och mixed integer programming (blandat flyttal och heltal). Det som numera komplicerar en strikt uppdelning av constraint programming å ena sidan och OR å andra är:

* Metoderna i CP och OR har sedan ett antal år börjat att närma sig/befrukta varandra.
* För t.ex. MiniZinc-systemet kan nämnas att en av de solvers som det redan nu finns stöd (ECLiPSe's eplex) använder just linear/integer programming. Det gör att det blir än mer flytande gränser. (Och i vissa av mina CP-modeller används standard-trick specifikt från integer programmering-modellering, se t.ex. knapsack_investment.mzn).

Här är några system som använder sådan matematisk programmering:

* AMPL. Det finns en demo (finns för Linux/Unix, Windows) att ladda ner och leka med. Demoversionen har dock endast stöd för cirka 300 variabler. AMPL är mitt favoritsystem inom denna genre; de solvers som används är rasande snabba, speciellt CPLEX som även finns att ladda ner som demoversion.

Kan passa på att här nämna att flera av mina MiniZinc-modeller först skrevs i AMPL under mitt AMPL-skov i höstas/vintras (se nedan). Det har funderats på att skapa en motsvarande "My AMPL page".

* GLPK är ett open source-system som har ett modelleringsspråk som är mycket likt AMPL (bygger på en tidigare version av AMPL), men är inte lika snabbt eller kraftfullt som AMPL (+ dess olika solvers). Tyvärr klarar GLPK inte icke-linjär programmering speciellt bra.

* Dash Optimization XPress Mosel. Här finns några exempel.
Man kan notera att de allra flesta problemen i Martin Chlonds underbara samling Integer Programming in Recreational Mathematics är skrivna i XPress-MP (och som antyddes i slutet av Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc finns de översatta till både AMPL och MiniZinc men inte tillräckligt hyfsade för att publicera.)

Några andra system nämns nedan.

Några böcker om Constraint Programming

Kim Marriott, Peter J. Stuckey Programming with Constraints - An Introduction. Min första CP-bok. Mycket trevlig med många exempel och detaljer. Exemplen är Prologvarianterna (Constraint Logic Programming). Både Marriott och Stuckey tillhör hjärnorna bakom MiniZinc.

Pascal van Hentenryck: Constraint Satisfaction in Logic Programming (finns inte just nu på Bokus). En av de första böckerna om Constraint Logic Programming. Flera av standardexemplen populariserades här.

Krzysztof Apt, Mark Wallace Constraint Logic Programming using Eclipse. Beskriver det Prolog-inspirerade systemet The ECLiPSe Constraint Programming System både vad gäller Prolog-delen och constraint-delen.

Pascal van Hentenryck, Laurent Michel Constraint-Based Local Search. Denna bok presenterar systemet COMET som löser optimeringsproblem med s.k. local search, vilket är en annan metod än den som beskrivs i ovanstående böcker.

Boken är mycket intressant just eftersom den beskriver moderna och mycket snabba tekniker samt dokumenterar ett specifikt system. Tyvärr är den version som finns nedladdningsbar inte riktigt kompatibel med boken så man måste mixtra en hel del.

Krzysztof Apt Principles of Constraint Programming. Detta är en ganska teoretisk bok som går igenom tekniken bakom constraint programming. Används vad jag förstår mycket på universiteten.

Thom Frühwirth, Slim Abdennadher Essentials Of Constraint Programming. Systematisk översikt över constraint programming. Det speciella är att man nästan genomgående använder Constraint Handling Rules (där Frühwirth är en av de stora).

En bok som funderas på att införskaffas är samlingsvolymen Handbook of Constraint Programming. Den innehåller många essäer om state-of-the art inom forskningsområdet. Den är tyvärr lite dyr.

Några böcker om Operations Research

Microsoft Office Excel 2007 - Data Analysis and Business Modeling. Det var faktiskt denna bok som fick mig börja med OR och sedan constraint programming. Några av kapitlen innehåller exempel från OR. En liten fotnot hänvisade till Winstons OR-bok (se nedan) och sedan var det kört.

(Jag har länge tänkt skriva om mitt Excel-skov som föregick OR- och CP-skoven. Det kommer förhoppningsvis någon gång framgent.)

Wayne Winston Operations Research - Applications and Algorithms. Många exempel, modellerna skrivna i Excel eller Lindo/Lingo.

Hamdy A. Taha Operations Research - An introduction. Också det en introduktionsbok.

Både Winston och Taha är alltså introduktionsböcker. Fastän Taha har exempel i AMPL (och Excel) så tycker jag nog att Winstons bok är något bättre, vilket kan beror på att det var den jag läste först. Båda har många exempel och mycket förklaringar.

En tanke: en annan förklaring till att jag tycker mer om Winstons bok kan vara att jag tyckte det var roligare och mer givande att översätta modeller från Lindo/Lingo än att se färdig kod som i Tahas bok.

Robert Fourer, David M. Gay, Brian W. Kernighan: AMPL: A Modeling Language for Mathematical Programming. AMPL-bibeln. Går minutiöst igenom de olika AMPL-konstruktionerna. Tyvärr inte så mycket om principer för modellering som jag hade hoppats. (Jullklappsbok 2007.)

H. P. Williams Model Building In Mathematical Programming, en översikt över tekniker inom matematisk modellering. En klassiker. Tyvärr gav den mig inte så väldigt mycket men jag är glad att ha läst den.

Lundgren, Rönnqvist, Värbrand: Optimeringslära. En mycket trevlig svensk bok om matematisk programmering.

Tony Hürlimann Mathematical Modelling of Puzzles and Games. En trevlig, ny och rätt okänd bok om matematisk modellering. Vad jag vet går den inte att få tag i på annat sätt än via Lulu.com, antingen att ladda ner som PDF eller beställa en träd-bok (ingendera är speciellt dyr). Exemplen är kodade i systemet LPL. En rolig feature är att koden finns som URL-ar, t.ex. chess4. Många av problemen är från Martin Chlonds Integer Programming in Recreational Mathematics (se ovan).

Så kommer några fria-att-ladda-ner-böcker:

Applications of Optimization with XPress-MP. Introduktion i modellering. Går igenom många modeller med:
- pratversion
- matematisk (generell) modell
- implementation i XPress-MP

Optimization Models For Decision Making: Volume 1, speciellt kapitel 7 "Modeling Integer Programs" var intressant.

Linus Schrage Optimization Modeling with LINGO som till viss del är som "Applications of Optimization with XPress-MP" men är inte riktigt lika systematisk vad gäller modellerna.

Det är alltså detta jag har hållt på med sedan höstas och som orsakade bloggtystnaden.

Några nya MiniZinc-modeller

* knapsack_investment.mzn, ett exempel på optimering av investeringar från ovan nämnda bok Optimeringslära.

* perfect_shuffle.mzn, en modell som visar utvecklingen av en perfekt blandning (en riffelblandning där man blandar exakt varannat kort från de två korthalvorna, en inte helt lätt bedrift att utföra). Se vidare out-shuffle. Med modellen kan man bl.a. se att det endast behövs 8 perfekta blaningar för att återställa ordningen i kortleken (vilket man redan visste och det var därför som man intresserade sig för matematiska modeller av perfekta blandningar:-).

* några varianter på set covering-problemet, samtliga exempel från boken "Optimeringslära":
- set_covering4.mzn
- en variant av samma problem men där mängder används istället: set_covering4b.mzn
- samt set_covering5.mzn som är en form av schemaläggning med lite olika typer av begränsningar.

* två nya global constraints: nvalue.mzn och den mer generella nvalues

* partial_latin_square, som är en variant av latin square.

* en ny variant av set partition, set_partition.mzn

Posted by hakank at 08:43 EM Posted to Constraint Programming | Operations research | Comments (6)

april 14, 2008

MiniZinc-sida samt fler MiniZinc-exempel

För en vecka sedan skrevs Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc, där bland annat några MiniZinc-exempel förevisades.

Sedan dess har jag renskrivit några andra av mina MiniZinc-modeller, dvs översatt kommentarer till engelska, tagit bort fåniga utrop samt givit någon form av problemreferens. Dessa finns nu på en egen MiniZinc-sida: My MiniZinc page tillsammans med andra relevanta länkar. Det finns för tillfället drygt 100 modeller (program) inom olika områden, där några listas nedan (det finns alltså fler på sidan).

Rubrikerna är (som alla indelningar) arbiträra och ofullständiga (men trots det bra att ha). Jag har inte - förutom i något enstaka fall - tagit med problem/modeller som finns på MiniZinc-exempelsidan (vilken se).

små och stora pyssel

exempel från Operations Research / integer programming-litteraturen

icke-linjär programmering

andra exempel på modellering i MiniZinc

Som grädde på moset finns även en modell som uppstod i samband med läsandet av Ravens Internationell på kontoret. Nämligen (den naturligtvis Vennska) funderingen: givet fördelning av språken, hur är då fördelningen per person. Det finns en massa lösningar. Problemet undersöks i Raven puzzle.

Posted by hakank at 06:58 EM Posted to Constraint Programming | Comments (2)

april 05, 2008

Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc

Minizinc är ett relativt nytt constraint programming-system (startade 2005). Det tillhör G12-projektet som är menat att bli ett öppet (som i open source) state-of-the-art-system.

Samtidigt som det mer kompletta systemet Zink håller på att utvecklas, utvecklas Minizinc en mindre variant som även föreslås att användas som ett gemensamt språk för benchmarks av olika constraint solvers (dvs de system som faktiskt löser problemen, se nedan).

Zinc (storebrodern) finns inte tillgängligt för närvarande. Det finns däremot Minizinc, dels i en officiell version 0.7.1, dels en utvecklingsversion (jag använder utvecklingsversionen). Se vidare Download för nedladdningar.

Specifikationen för både Zinc och MiniZinc är Zinc spec (PDF). Detta dokument och andra nyttigheter finns via MiniZinc and FlatZinc. Uppdaterade versioner av dokumenten finns i utvecklingsversionen.

Många Minizinc-exempel finns här. Fler exempel finns i distributionens kataloger examples respektive benchmark samt till viss del i katalogen test/minizinc.

Jag tycker att Minizinc är ett mycket trevligt och lättarbetat system. Språket har syntaktiskt socker på en bra nivå och är numera min favorit bland constraint programming-systemen.

Det kommer att bli mycket intressant när Zinc släpps eftersom det har en massa skoj finesser som jag saknar i Minizinc, men jag lämnar det för nu. Här nedan kommer jag alltså i stort sett endast att prata om Minizinc.

Lite om Minizinc

Prolog är ett av de mest kända exemplen på denna typ av programspråk. [Några mindre kända sådana språk är inom stable models/answer set programming-paradigmet såsom smodels/lparse, som nog kan uppfattas som än mer magiska än Prolog.]

Minizinc är dock inget "komplett programspråk" såsom Prolog, t.ex. saknas stöd för rekursion (detta av design för att göra det enkelt att arbeta med för olika solvers), det finns ingen filläsning förutom inkluderande av andra Minizinc-modeller eller data, hantering av strängar är synnerligen begränsat etc.

Trots dessa begränsningar är kan väldigt många problem modelleras i Minizinc. Se den officiella exempelsamlingen som innehåller olika typer av standardproblem från constraint programming, operations research och matematisk programmering. Nedan finns något av det som jag själv knåpat ihop.

Några speciellt trevliga saker i Minizinc

- definition av predicate

Man kan definiera predikat som sedan kan återanvändas via include-direktivet. Det finns en samling sådana i lib/zinc/globals.mzn som är väl värt att studera.

(I Zinc kommer det att finnas möjlighet att definiera funktioner som returnerar värden, men i Minizinc använder man samma teknik som i Prolog för att "returnera" värden, dvs att ange returvärdet i parameterlistan.)

- "bidirectional" predikat

Liksom Prolog har Minizinc den trevliga egenskapen att predikat kan vara "bidirect", dvs att flödet mellan parametrarna kan verka åt båda hållen, kan vara ut- eller in-data. Ett enkelt exempel på detta är konvertering mellan tal och en vektor (givet en bas). Jag har definierat toNum på följande sätt.

predicate toNum(array[int] of var int: vec, var int: n, float: base) =
let {
int: len = length(vec)
}
in
% summera ihop elementen i vec för den givna basen
n = sum(i in 1..len) (
ceil(pow(base, int2float(len-i))) * vec[i] % se nedan för varför denna används
)
% samtliga element i vec måste vara 0
/\ forall(i in 1..len) (vec[i] >= 0)
;


Poängen är att man kan använda detta predikat för att konvertera från ett decimaltal (n) till en vektor (vec) av heltal i den givna basen base, eller konvertera från vektorn av heltal till ett tal (givet en bas). toNum används t.ex. i debruijn_binary.mzn, vilken se. (I teorin skulle man också kunna räkna ut vilken bas som används givet vec och n, men det går inte i Minizinc eftersom pow() inte kan användas på en var-deklarerad variablen utan måste definieras som en fix parameter.)

Här blir n = 7

% ...
constraint
% ....
toNum([1,1,1], n, 2.0)
;


och här blir vec = [1,1,1]:

% ...
constraint
% ...
toNum(vec, 7, 2.0)
;


Det är mycket denna bidirektionella egenskap gör att programmering i Minizinc (och liknande deklarativa språk) känns riktigt magiskt. Och det är synnerligen skoj.

Tyvärr är Minizinc hårt typat så man måste själv konvertera flyttal till heltal, vilket frustrerar mig. [I Zinc/Minizinc-specen står att sådan konvertering kommer att göras automatiskt i storebroderna Zinc, men inte i Minizinc. Jag hoppas att specifikatörerna besinnar sig.] Och eftersom pow()-funktionen för heltal inte funkar i den aktuella versionen är man tvungen att använda float-varianten vilket innebär att man måste använda göra ceil(...)-hacket. Det är ju en hel del sådant i betaversioner som det tar tid att komma på och runt.

Ett något mer avancerad exempel på bidirection är mortgage.mzn (beräkning av lån), som är ett (annat) standardexempel i constraint logic programming (där ofta just Prolog användas som grund eller inspiration för implementationerna). På samma sätt som i toNum kan samma kodbas - med olika initialvärden - användas för att räkna ut de andra parametrarna. Se kommentarerna i programmet för vidare info. Not: för närvarande är det endast ECLiPSe-solvern som klarar detta problem.

Exempel på mer användande av toNum finns i programmen debruijn_binary och gray_code.mzn som beskrivs mer nedan.

* global constraints

I filen lib/zinc/globals.mzn finns ett flertal "global constraints" implementerade (och det antyds att det kommer att fyllas på med fler). Global constraints kan ses som standardrutiner ("standardmönster") att lösa vissa typer av (del)problem, t.ex. all_different(x) som kräver att samtliga element i en vektor ska vara olika, global_cardinality_constraint som räknar hur antal förekomster av olika element det finns i en vektor (och med bidirect-principen kan man ställa krav på antalet förekomster), etc.

Det finns en stor samling definitioner/beskrivningar av sådana global constraints (men tyvärr inga implementationer) i Global Constraint Catalog.

Min personliga fascination för sådana globala constraints är på modelleringsnivå eftersom de kan ses som byggstenar (tankehjälp) för modellering. Som övning har några av dessa implementerats såsom circuit.mzn (som i min implementation bygger på några observationer kring s.k. orbits i permutationer), cycle etc.

En stora vinst med sådana global constraints är att underliggande solvers kan göra specialoptimimeringar, vilket naturligtvis snabbar upp systemen. Studiet av sådana global constraints är en viktig del i forskningen kring constraint programming.

* stöd för flera olika solvers

Språket Minizinc är egentligen bara en del av systemet och det löser inga problem. I stället konverteras till ett annat språk (Flatzinc) som olika solvers kan arbeta med för att faktiskt lösa problemet. (Man skulle kunna översätta "solver" med "problemlösare", men eftersom det ryser varje gång jag använder den svenska versionen av Excels Solver så gör jag inte det :-). I distributionen finns det en solver med: flatzinc.

Redan nu finns det redan tre solvers: flatzinc, Gecode/flatzinc samt ECLiPSe-modulen minizinc. De gås igenom nedan.

Exempel

Så här ser min rättframma implementation ut:

% globals.mzn innehåller den globala constrainten all_different
include "globals.mzn";

Sedan kör man programmet lite olika beroende på vilken solver man använder. Jag brukar testa med samtliga tre för att se vilken som är snabbast etc.

Minizinc (anropar flatzinc automatiskt)

minizinc send_more_money.mzn


eller programmet flatzinc direkt via konvertering till .fzn-format.


mzn2fzn send_more_money.mzn
flatzinc send_more_money.fzn


Gecode/flatzinc:

mzn2fzn send_more_money.mzn
fz send_more_money.fzn


ECLiPSe:

eclipse -e "minizinc:mzn_run('send_more_money.mzn',zn_options{solver:fzn_ic})"


Resultatet blir samma för alla

S:9 E:5 N:6 D:7 M:1 O:0 R:8 Y:2

Fler exempel

I Choco: Constraint Programming i Java gavs några exempel på problem som löstes i constraint programming-systemet Choco. Dessa har nu skrivits om i Minizinc. Som jämförelse länkas även till Choco-varianten.

* Planering av möbelflyttande, använder "global constraint" cumulative

furniture_moving.mzn (FurnitureMoving.java)

* Ett enkelt knapsack-problem (minimering)

knapsack.mzn (Knapsack.java)

* Least diff (minsta differensproblemet som beskrivs i ovanstående blogganteckning)

least_diff.mzn (LeastDiff2.java)

* Sesemans klosterproblem

seseman.mzn (Seseman.java). Se Sesemans matematiska klosterproblem samt lite Constraint Logic Programming för en förklaring av detta problem.

* set_covering_deployment.mzn

Implementation av exemplet på Set Covering Deployment för att optimera antal arméer i gamla romarriket. Problemet beskrivs i detalj i R.R. Rubalcaba Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs (PDF).

de Bruijn-sekvener och "arbiträra de Bruijn-sekvenser"

- de Bruijn sequence, samma som Java Applet

- de Bruijn arbitrary sequences, där man använder "de Bruijn-egenskapen" men tillåter sekvenslängden bestäms av användaren.

Se respektive de Bruijn-sekvenser (portkodsproblemet) och de Bruijn-sekvenser av godtycklig längd för förklaringar av programmen.

Naturligtvis var detta en sak som skulle kodas i Minizinc. Första versionen av programmet byggde liksom webbversionen av "de Bruijn arbitrary sequences" på en speciell typ av graf som traverserades på ett visst sätt. Denna implementation var dock lite trixig att genereralisera till andra baser än n=2. Därefter skrevs en variant där man programmerar de Bruijn-egenskapen direkt i stället för att gå via en graf, vilket gjorde det hela mycket mer generellt och (oftast) snabbare.

Denna senare variant finns att beskåda i debruijn_binary.mzn. (Anledningen till att programmet heter "_binary" är bl.a. för att jag fick idén till implementationen några minuter efter jag kodat klart Gray-koder).

Exempelkörning
Problemet som jag kallar för 2/4/16 är base = 2, n = 4 (antal bitar att använda), m = 16 (längden på sekvensen). Programmet spottar ur sig lite olika typer av information:

- bin_code / binary_code: själva de Bruijn-sekvensen
- x är decimalrepresentationen av vektorerna som utgör sekvensen
- gcc (förkorting av global cardinality constraint) kontrollerar hur många olika siffror (0..base-1) som används. Det finns en begränsning att det måste vara exakt lika många förekomster av de olika siffrorna om det är matematiskt möjligt. Och det är just denna begränsning som gör problemet både intressant och tungt. I exemplet ser vi alltså att det finns 8 stycken 0:or och 8 stycken 1:or.
- sedan kommer listningen av "bit-representation" av vektorerna


n: 4 m: 16 base: 2
bin_code: [0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1]
gcc: [8, 8]
binary code: 0000100110101111
x (decimal representation):
[0, 1, 2, 4, 9, 3, 6, 13, 10, 5, 11, 7, 15, 14, 12, 8]
0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 1
0 0 1 1
0 1 1 0
1 1 0 1
1 0 1 0
0 1 0 1
1 0 1 1
0 1 1 1
1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0


Ett problem som är betydligt tyngre att lösa är 4/3/52, dvs bas=4 (dvs siffrorna 0, 1, 2 och 3 används), 3 "bitar" i varje tals vektor, samt en sekvenslängd på 52. Detta är så tungt så man inte kan använde solve satisfy utan måste använda sökheuristiker för att inte vänta förgäves på en lösning.

Genom experiment (föregånget av luskande i källkod och dokumentation hittades följande

solve :: int_search(x, "first_fail", "indomain_split", "credit(5,bbs(1))") satisfy


(Zinc-specen förklarar ingående vara parametrarna innebär, men det är helt enkelt lite olika metoder att traversera problemträdet.)

Den praktiska innebörden är att Eclipse-solvern hittar 1 lösning mycket snabbt, 65 lösningar på 5 sekunder (jag vet inte hur många olika lösningar som det total finns men det är väldigt många i alla fall). Med credit(4,bbs(2)) blir det 108 lösningar på 8 sekunder, credit(4,bbs(4)) hittar 1104 lösningar på 1:07 minuter etc.

En av dessa lösningar är följande

n: 3 m: 52 base: 4
bin_code: [0,0,2,0,0,3,0,1,0,1,1,0,2,1,0,3,1,1,1,2,0,1,2,1,1,3,0,2,2,0,2,3,0,3,2,0,3,3,1,2,2,1,2,3,1,3,3,2,2,3,3,3]
gcc: [13,13,13,13]
binary code: 0020030101102103111201211302202303203312212313322333
x (decimal representation):
[2,8,32,3,12,49,4,17,5,20,18,9,36,19,13,53,21,22,24,33,6,25,37,23,28,50,10,40,34,11,44,51,14,56,35,15,61,54,26,41,38,27,45,55,31,62,58,43,47,63,60,48]Total time 0.320s cpu (0.040 setup + 0.280 search)


Tyvärr har varken Flatzinc eller fz givit någon lösning alls på detta problem (jag har låtit båda programmen stå minst en timme varderna men sedan tröttnade jag). Om man däremot tar bort kravet att det ska exakt samma antal förekomster av siffror i sekvensen löser även fz problemet snabbt (men minizinc gör det inte).

Olika solvers

* flatzinc
Det är denna solver som följer med i Minizinc-distributionen.

Fördelar:
- det största fördelen är att den finns med i distributionen och kan alltså användas direkt.

Brister:
- ger endast en lösning oavsett hur många lösningar som problemet har. Detta är för mig en mycket stor brist.
- klen vad gäller beräkning av stora tal. T.ex. klarar den inte av grocery.mzn eftersom det är för stora tal inblandade.
- verkar inte vara känslig för de olika heuristikerna

* Gecode/flatzinc (fz)
Gecode/Flatzinc.

Kräver att Gecode finns installerad. Gecode är ett snabbt open source constraint programming-system (skrivet i C++) och har flera intressanta exempel. Det finns även en Java-implementation ovanpå Gecode Gecode/J. Båda dessa är väl värda att bekanta sig med helt oavsett Minizinc.

Fördelar:
- ofta mycket snabb, ibland snabbare än Eclipse-solvern (även fast man har heuristiker som hjälper Eclipse-solvern)
- ger flera lösningar (alla!) om det finns (såvida man inte "heuristicerar" bort dem)
- summerande statistik som indikerar hur svårt problemet är att lösa

Nackdelar:
- min uppfattning är att fz inte är lika känslig för sök-heuristikerna som Eclipse-solvern vilket gör att den kan vara långsammare än Eclipse-solvern för vissa problem
- klarar inte av vissa typer av flyttalsberäkningar, t.ex. mortgage exemplet ovan.
- kan reagera konstigt på sök-heuristikerna
- man måste installera gecode

* ECLiPSe
Kräver ECLiPSe Constraint Programming System. Det är en variant av Prolog (min favoritvariant och som användes i Sesemans matematiska klosterproblem samt lite Constraint Logic Programming).

För tillfället krävs en utvecklingsversion eftersom Minizinc-stödet ännu inte är officiellt släppt. Eftersom sajten crosscoreop.com kan bete sig konstigt vid hämtande av stora filer är att rekommendera att man hämta filerna från en av speglarna t.ex. http://sunsite.informatik.rwth-aachen.de/ftp/pub/mirror/ECLiPSe-CLP/.

Dokumentation hur man använder Minizinc-modulen finns i library(minizinc).

Ett tips är även att studera ECLiPSe-predikatet search/6 som är inspirationskällan för sök-heuristiken i Minizinc.

Fördelar:
- liksom fz mycket snabbt och ger alla lösningar
- klarar av flyttalsberäkningar (såsom mortgage)

Nackdelar:
- vissa saker är inte implementerade, såsom vissa set_operationer.
- man måste installera ECLiPSe-systemet.

Buggar eller brister

* Utskrifen är inte fullständigt i den existerande beta-versionen. Det är trixigt att skriva ut mer komplicerade strukturer (se exemplen). Det finns för närvarande inget sätt att villkora så att man bara ska skriva ut vissa element i en var-deklarerad array (såsom endast de element som är större än 0). Till viss del är det ett desginbeslut, möjligen kommer fix() att lösa några av dessa problem.

* Typningen. Personligen tycker jag inte om den strikta typningen av float och int (det är enligt design) som gör att man explicit måste sköta sådant. T.ex. görs '/' (division) endast på flyttal och det gör att vissa problem blir mycket svårare att lösa (såsom några av Integer Programming-pysslen). Det är inte alltid det går att använda div-operatorn (som f.ö. är buggig i fz) eller att (på ett enkelt sätt) skriva om problemet så det inte använder division.

* Det saknas en solver som använder metoder från linjär programmering/heltalsprogramming (såsom simplex-metoden). Det antyds att det finns sådana men de är ännu ej släppta. I och för sig har ECLiPSe-systemet någon form av stöd för eplex i sin Zincinterface-katalog, men det har jag inte fått att fungera ännu. Uppdatering ett halvt dygn senare:: Jodå, eplex funkar för vissa typer av problem såsom några av exempeln i examples-kataloge; queens_ip.mzn, min_cost.mzn, product_lp och multidimknapsack_simple. Får alltså kolla in det mer...

Länkar
Annat som kan vara intressant.

* Integer Programming Puzzles (programmering av lösningarna av Martin Chlond). Detta är en härlig samling "heltalspyssel" (dvs där lösningarna är heltal, eller kan ses som heltal). Send More Money, Least Diff är några andra exempel på sådana problem.

När jag satt med AMPL i höstas konverterade jag i stort sett samtliga dessa problem från XPress till AMPL, och har nu kodat om dessa till Minizinc. Tyvärr är det inte alla Minizinc-implementationer som ger resultat inom rimlig tid. Ett projekt i vardande är att hyfsa till dem och sedan lägga ut dem på sajten.

Jag tänkte här egentligen länka till en del annat som jag hållt på med sedan oktober förra året, såsom Excel, Open Office Calc, Linear Programming, AMPL, GLPK, matematisk programming, Operations Research, andra constraint programming-system etc, men det blir i så fall i separata postningar.

Posted by hakank at 09:33 EM Posted to Constraint Programming | Comments (6)

april 18, 2006

Choco: Constraint Programming i Java

Bakgrund
Mitt intresse för Constraint Programming (CP) (som tidigare kallades Constraint Logic Programming, CLP) väcktes för ett antal år sedan strax efter en företagskamp (som kort beskrevs i Uppdaterat program: AnaCheck), där ett av uppdragen var följande matematiska pyssel:

Vilken är den minsta differensen man kan få mellan två tal om man måste använda samtliga siffror (0..9) exakt en gång?

Lösningen presenteras nedan.

Ungefär samtidigt stötte jag på Constraint (Logic) Programming och med detta och liknande pyssel i bakhuvudet, och blev väldigt fascinerad av programmeringsparadigmet. Kanske inte så förvånande eftersom många standardexempel är just matematiska pyssel.

Tanken är att man endast behöver skriva de problemspecifika villkoren (constraints), sedan får systemet lista ut bästa sättet att lösa problemet. Det finns många olika metoder och heuristiker för att lösa problemen, och ibland måste hjälpa till så att lösningen kommer denna sidan regnbågen eftersom vissa problem är mycket tunga.

Ett citat som ofta nämns i sammanhanget är Eugene C. Freuder (CONSTRAINTS, April 1997)

Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it..

Prologbaserade system
I början arbetade jag mestadels med logikprogramspråket Prolog som "moderspråk", Sicstus Prolog samt ECLiPSe Constraint Programming System (det senare inte att förväxlas med utvecklingsmiljön med ungefär samma stavning).

Imperativa språk
Som komplement till de Prologbaserade systemen har jag letat efter mer imperativa - samt icke-kommersiella - moderspråk såsom Java, C, C++, Perl, Python, eftersom vissa saker är lättare att programmera med sådana språk (men ibland svårare) En av dessa implementationer Python-constraint och nämns i kommentarerna till Sesemans matematiska klosterproblem samt lite Constraint Logic Programming.

Choco
Så till det system jag har kollat i nyligen: det Java-baserade Choco. I slutet av anteckningen finns fler referenser.

Choco är snabbt och det har en stor mängd funktioner. Exemplen nedan är endast för "finita domäner" (löses med hjälp av heltal), men det finns även domäner med reella tal samt mängder.

Det är dock inte lika elegant att skriva constraints som i Sicstus/ECLiPSe, vilket vi nu kommer att titta på.

Minsta differensproblemet - en jämförelse av kodskrivning
För att tydliggöra skillnader och likheter mellan Choco och de Prologbaserade systemen visas hur minsta differensproblemet kan lösas i respektive system.

I ECLiPSe skriver man själva constraint-delen av problemet på följande sätt; i Sicstus Prolog skriver man snarlikt. Obs: koden är inte riktigt komplett att bara köra.

:-lib(fd), lib(fd_search), lib(fd_global),lib(fd_domain).

Elegant och lite magiskt, eller hur?

Motsvarande Choco-program är lite längre, främst eftersom det saknas syntaktiskt socker. Det går att pressa antalet rader (sådant har gjorts) men här görs en mer expressiv form för att jämförelsen ska bli tydligare. Programmet finns att ladda ner här nedan.


// Choco program

} // end class


Lösningen som ges av dessa båda program är samma, nämligen

50123 - 49876 = 247


Några körbara (kompilerbara) Choco-program
Här är källkoden till några andra mindre Choco-program, varav några är standardproblem inom constraint programming. Choco-distributionen innehåller några andra.

LeastDiff2.java: Ovanstående exempel
FurnitureMoving.java: Planering av möbelflyttande, använder cumulative.
Knapsack.java: ett enkelt knapsack-problem (minimize)
Zebra.java: ett standardpyssel
Seseman.java: Choco-versionen av Sesemans matematiska klosterproblem

Se även
om Choco:
Choco: projektsidan på Sourceforge
Wiki
User guide
Choco API
Forum

om constraint programming
Roman Barták: On-line Guide to Constraint Programming
Roman Barták: Constraint Programming: In Pursuit of the Holy Grail (PDF)

tidigare skrivet om C(L)P
Sesemans matematiska klosterproblem samt lite Constraint Logic Programming
Automatisk "lösning" av Minesweeper i Mozart/Oz

JaCoP är ett annat Javabaserat system, utvecklat vid Lunds Universitet som man kan få tillgång till om man frågor någon av dess skapare. Har inte kollat in det så mycket ännu, men det verkar också trevligt.

Posted by hakank at 09:59 EM Posted to Constraint Programming | Matematik | Pyssel

november 04, 2005

Sesemans matematiska klosterproblem samt lite Constraint Logic Programming

Bengt O. Karlsson ställde igår en matematisk gåta: Ett aritmetiskt problem av Hans Jacob Seseman. Se även den omslutande anteckningen Sesemania (som avslutas med en personlig anmaning). [Uppdatering: Titeln på den nyss angivna anteckningen är felaktig och ska vara Sesemana, men felskrivningen upplevdes av Bengt som en nära-Freud-upplevelse. Och hur kan man underlåta att ge Bengt en sådan njutning? Därför står felstavningen kvar i sin ursprungliga - men alltså felaktiga - prakt. Se något mer i kommentarerna till Bengts Sesemana -artikel. I sanningens namn korrigerades först felet, men sedan korrigerades rättet och denna uppdatering skrev som ett förtydligande.]

Det var ett kul litet problem, och inte speciellt svårt att lösa. En av utmaningarna var att korrekt tolka gammelsvenskan för att förstå vad problemet egentligen bestod av. Försök gärna lösa problemet själv innan ni läser vidare eller läser kommentarerna till problemet.

Uppdatering 2
På begäran har programmet Seseman's Convent Problem (se nedan) nu även möjlighet att visa unika lösningar, eller - mer korrekt - samla lösningar som är lika vad gäller rotation, spegling etc. Denna unicifiering har gjorts i CGI-programmet, ursprungligen som ett analysstöd för att eventuellt senare göra sådant i CLP-programmet.

Problemet
Problemet består av 4 liknande delproblem där det gäller att givet ett visst antal personer i ett kloster (nunnor samt eventuellt "tillkomne Karlar") ska man placera ut dessa personer i rum så att vissa villkor uppfylls.

A, B, C, D, E, F, G, H betecknar klostrets olika rum. Rummet "_" används inte, forutom att presentera en fin kvadrat.

A B C
D _ E
F G H


Ett krav är att vissa rader/kolumner ska ha summan 9:

A + B + C = 9
A + D + F = 9
C + E + H = 9
F + G + H = 9


Ett annat krav är att totalantalet personer ska vara en av de fyra summorna (24, 28,20, 32), som man själv fick lista ut med lite enkelt aritmetik. Villkoret är alltså:


A + B+ C + D + E + F + G + H = Totalsumma


Notera att det inte står någonting om huruvida rum kan vara tomma eller ej (se nedan om detta).

I kommentarerna till problemet visades ett antal olika lösningar, och det visar sig att problemet inte är entydigt eftersom några delproblem har flera lösningar, varav några presenteras av Fredriik och Hakke (också en Håkan K) samt undertecknad (Håkan K).

Constraint Logic Programming
Men det finns fler lösningar än så.

Problemet löstes ursprungligen med penna och baksidan av ett papper, men efteråt skapades ett litet CLP-program (Constraint Logic Programming) för att generera de olika lösningarna, närmare bestämt i det Prolog-baserade programspråket ECLiPSe (Gratis att ladda ner, men man måste anhålla om en licens.)

ECLiPSe-programmet finns här. Den centrala funktionen i programmet innehåller i stort sett endast de matemaitksa uttrycken ovan.

seseman(Rowsum, Total, FirstNum, LD) :-
LD = [A,B,C,D,E,F,G,H], % deklarera variablerna

labeling(LD).


Den magiska genereringen av giltiga lösningar enligt restriktionerna (constraints) hanteras av labeling.

För att köra programmet från kommandoraden anger man följande:

eclipse -b seseman.ecl 9 24 1 -e 'go.'


där 9 är radsumman, 24 totalsumman. Talet 1 är ett hack för att ange att inget rum får vara tomt (0 om rum får vara tomma). -e 'go' är anropet till funktionen go och -b anger filnamnet.

Lösningar och ett webb-program
Det skrevs även ett webb-program som kommunicerar med ECLiPSe-programmet: Seseman's Convent Problem (monastary är munkkloster, convent är nunnekloster). Detta program gör det också möjligt att ändra på parametrarna skulle man så önska leka lite.

T.ex. finns det 7 lösningar för totalsumma 20 om man inte tillåter tomma rum och hela 73 lösningar om tomma rum tillåts.

Notera att programmet inte tar hänsyn att två lösningar kan vara samma fast de är roterade, spegelvända etc. Uppdatering Jodå, det gör det nu.

För de fyra olika totalsummorna som angav i problemet förevisas här antalet lösningar och om rum får vara tomma eller ej:
24 personer, tomma rum tillåts ej: 85 lösningar
24 personer, tomma rum tillåts: 231 lösningar

Som problemet är formulerat finns det dock bara en korrekt lösning för första delproblemet (24 nunnor): samtliga rum innehåller vardera 3 nunnor.

28 personer, tomma rum tillåts ej: 35 lösningar
28 personer, tomma rum tillåts: 165 lösningar
20 personer, tomma rum tillåts ej: 7 lösningar
20 personer, tomma rum tillåts: 73 lösningar
32 personer, tomma rum tillåts ej: 1 lösning
32 personer, tomma rum tillåts: 35 lösningar

Programmet har dock kvar begränsningen att maximalt antal personer som får finnas i ett rum är 9. Vi kan väl säga att det beror på att jag vill vara snäll mot webbservern. Om man vill leka med större värden kan man ändra 9 till något annat (t.ex. Total) på denna rad:

LD :: [FirstNum..9],


Kommentarer
Jag har inte hittat någon ren matematisk lösning på problemet, men en sådan kanske kommer (av någon). Ovanstående program gör det i alla fall möjligt att empiriskt studera problemet. Uppdatering: Det finns en bok Sesemans problem som kanske innehålla slika lösningar.

Man kan möjligen misstänka att Fredrik nu kommer att skriva ett mycket elegantare Python-program för detta problem.

För den som vill läsa mer om Constraint Logic Programming kan rekommenderas Programming with Constraints av Kim Marriott och Peter Stuckey. Boken innehåller många exempel som finns att ladda ner.

Posted by hakank at 11:48 EM Posted to Constraint Programming | Matematik | Program | Comments (12)