« maj 2008 | Main | juli 2008 »

juni 30, 2008

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

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

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


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

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


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


#
# GAP program for solving the M12 puzzle.
#

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

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

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

#
# End of GAP code
#

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

Lösningen på detta är

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

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


I M I M2 I M I M6 I

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


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

Lösningen är

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

Vilket alltså motsvarar M12-operationerna:

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

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


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

Posted by hakank at 07:22 EM Posted to

juni 29, 2008

Gruppteoretisk lösning av M12 puzzle i GAP

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

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

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


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


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


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

#
# Solving the M12 for a specific sequence
#

#
# Define the operators
#

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

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

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


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

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

Size(g);
# 95040

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


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


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


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


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

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

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

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

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

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

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

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

M6 I M6 I M2 I

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


En variant

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


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

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

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

Lösningen är alltså:

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

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

Ovanstående motsvarar följande M12-operationer:

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

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


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

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

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

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


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


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


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

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

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


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

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

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)

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

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

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

Definiera först utgångspositionen:

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

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


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

Lösningen finns i andra kolumnen i moves, dvs

6 3 2 1 4 5 8 9

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

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


M12


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

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

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

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

och man gör en merge blir resultatet


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

dvs man får då lösningspositionen.

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

Exempel:
Här är ett enkelt problem:

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

Lösning:

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

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

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

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

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


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


SET puzzle


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

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

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


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

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


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

include "globals.mzn";

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

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

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

constraint

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

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

) % end forall 1..num_sets

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

output [
show(x)
]

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


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

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


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

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

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

Posted by hakank at 09:07 FM Posted to Constraint Programming | Pyssel

juni 11, 2008

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

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

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

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

Sammanfattningen är som följer


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

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

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

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

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

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


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

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

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


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


Grattis till betyget, Jorun!

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

juni 09, 2008

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

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

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

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

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


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

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

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


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

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

Företaget presenterar sig så här:


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

Det låter i alla fall vettigt.


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

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

Posted by hakank at 09:18 EM Posted to Sajter

juni 06, 2008

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

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


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


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

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

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

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

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

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

juni 05, 2008

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

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

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

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

Constraint programming-modell i MiniZinc

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

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

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

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

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

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

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

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


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

Mitt tips

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

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


MiniZinc-modellen


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


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

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

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

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

solve satisfy;

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

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

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

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


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

%
% End of MiniZinc model.
%


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


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


Slutord


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

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

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

juni 02, 2008

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

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

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

Pyssel

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

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

Global constraints etc

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


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

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

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

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

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

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

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

Här är hela modellen.


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

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

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

solve maximize c;

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

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

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

Exempel på några problem med clique

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

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

solve satisfy;

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

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


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


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

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


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


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

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

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

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


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

Övriga global constraints

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

* all_differ_from_at_least_k_pos

* all_min_dist

* alldifferent_cst

* alldifferent_except_0

* alldifferent_modulo

* alldifferent_on_intersection

* alldifferent_partition

* alldifferent_same_value

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

* change

* circular_change

* common
Modellen implementerar:
- common
- used_by

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

* distance_between

* inflexions

* k_alldifferent

* longest_change

* nchange

* period

* sum_ctr

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

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

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

Matris-operationer

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

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

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

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

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

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


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

solve satisfy;

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

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

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


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

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


% ....

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

Svar: Det finns 2880 lösningar.


Slutord (för dagens skörd)


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


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

MiniZinc/FlatZinc version 0.8 släppt

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

Den nya versionen finns här.

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

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


De praktiskt viktigaste ändringarna är:

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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


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


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

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

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

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

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


Posted by hakank at 06:10 EM Posted to Constraint Programming