« Bloggträff söndag 1 mars kl 17.00 på Kin Long i Malmö | Main | Mitt föredrag på SweConsNet Workshop 2009: "Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned" »

mars 16, 2009

Lite om vad som händer på andra bloggen: My Constraint Programming Blog

Som tidigare nämnts är det inte här utan på My Constraint Programming Blog ("Min villkorsprogrammeringsblogg") jag numera mest håller till.

Här är en liten sammanfattning om vad som hänt där och i samband med detta.

* En stor drös med Comet modeller på My Comet page. Några exempel:


* En mycket mindre drös med MiniZinc-modeller på My MiniZinc page.

Men de modeller som tagit mest tid är följande

Nonogram
Här är de blogganteckningarna som presenterar de olika varianterna, i normal sorterad tidordning:
1) More Comet models, e.g. Nonogram, Steiner triplets, and different set covering problems som presenterade den första Nonogram-modellen. Långsam var den.
2) Comet: regular constraint, a much faster Nonogram with the regular constraint, some OPL models, and more presenterade en mycket snabbare Nonogram-modell som använder principen bakom reguljära uttryck (villkoret regular).
3) samt slutligen Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about 1 second där jag hittade lite mer saker att förbättra, bl.a. med hjälp av en av mina husgudar Pascal Van Hentenryck och som är en av skaparna av just Comet.

Ungefär samtidigt kom jag i kontakt med gänget bakom Gecode (C++ baserat), det snabbate constraint programming-systemet som jag känner till. Roligt nog har de nu lagt in samma förbätring i sitt Nonogramprogram.


Pi Day Sudoku
I lördags var det Pi-dagen (3.14 som vissa skriver den 14 mars) och som hyllning skapade Brainfree Puzzles några dagar tidigare en tävling: Pi Day Sudoku 2009. Det är som vanliga Sudoku fast med knorr: förutom att det ska vara 1..9 på samtliga rader och kolumner ska det finnas exakt tre stycken Pi. Till detta kommer att man inte har de vanliga kvadratiska regionerna som kräver samma fördelning av siffror utan det är även olika former på regionerna (kolla sajten så förstår ni bättre). Jag har slutat med att lösa Sudokuproblem för hand, däremot var de speciella kriterierna ett intressant problem att modellera med villkorsprogrammering (constraint programming).

Första modellen, som var rätt långsam, skrevs om i Pi Day Sudoku 2009. Efter lite funderande, och framförallt diskuterande med Mikael Zayenz Lagerkvist (från sagda Gecode team), snabbades modellen upp avsevärt. Detta beskrevs i Solving Pi Day Sudoku 2009 with the global cardinality constraint.

Till förfång för alla de som som söker på Pi Day Sudoku har varken lösningen på problemet eller modellerna presenterats på bloggen (det blir inte förrän tävlingen är över).


Gecode 3.0.0
Vi får ju inte heller glömma att version 3.0.0 av Gecode släpptes för några dagar sedan. Jag rekommenderar varmt den mycket trevliga introduktion till modellering i Gecode: Modeling with Gecode (PDF).

I och med att version 3 har släppts kommer det inom kort även stöd för det grafiska verktyget Gist till MiniZinc, dvs när man har Gecode/FlatZinc som lösare (och det har man alltid som förstaval). Det ser jag mycket fram emot.


Till sist: MiniZinc Challenge 2008
Resultat av constraint programming-tävlingen MiniZinc Challenge 2008 kom förra vecka. Inte förvånande vann Gecode. Mer om detta skrevs i MiniZinc Challenge 2008 Results.

Posted by hakank at mars 16, 2009 08:34 EM Posted to Constraint Programming | Reguljära uttryck etc