« oktober 2008 | Main | januari 2009 »

december 29, 2008

My Constraint Programming Blog

Som antyddes i slutkommentaren till Constraint programming-nyheter samt nya MiniZinc-modeller funderades det på att skapa en engelskspråklig specialblogg om constraint programming (och relaterade paradigm).

Sagt och gjort: My Constraint Programming Blog vars första inlägg Welcome to my My Constraint Programming Blog innehåller - förutom indroducerande information - länkar till fyra nyskrivna MiniZinc-modeller.

Nya MiniZinc-modeller
Först tre modeller med uppgifter från Rosetta code.
* 99_bottles_of_beer.mzn : 99 bottles of beer
* knapsack_problem.mznKnapsack problem
* pyramid_of_numbers.mzn: Pyramid of numbers

Samt en operations research-modell
* sportsScheduling.mzn: Sports scheduling.


Noter
* Vi får helt enkelt se hur frekvent My Constraint Programming Blog uppdateras och i vilket håll den kommer att utvecklas. "Relaterade paradigm" är en vidlyftig ballong.
* Jag kommer inte här att upprepa allting som skrivs på My Constraint Programming Blog, däremot kommer uppsamlingsanteckningar skrivas med oregelbunden regelbundenhet.
* My Constraint Programming Blog kommer inte att pinga intressant.se, twingly eller andra svenska ping-portaler.
* Orsaken till den frekventa länkningen till My Constraint Programming Blog ovan (och här) är naturligtvis sökmotorrelaterad. Sorry about that.

Posted by hakank at 09:29 FM Posted to Constraint Programming

december 27, 2008

Constraint programming-nyheter samt nya MiniZinc-modeller

Här är några nyheter kring constraint programming sedan cirka oktober 2008 och inkluderar naturligtvis även en del MiniZinc-modeller.

My Constraint Programming page

För att samla ihop mina constraint programming-modeller/-referenser har skapats Constraint Programming som i stort sett endast är länkar till respektive "My XXXXXX page" (där "XXXXX" in {MiniZinc, Choco, JaCoP}).

MiniZinc

För vidare info, se My MiniZinc page.

JaCoP

För vidare info, se My JaCoP page.


Choco


För vidare info, se My Choco page.


Minion/Tailor


Tailor är ett trevligt modelleringsspråk som översätter en Essence'-modell (en nedstrippad variant av modelleringsspråket Essence) till Minion. Tailor är implementerat i Java.

Jag har skrivit några Tailor-modeller men de är ännu inte publikt publicerade, bland annat eftersom specifikationen av Tailor/Essence' inte har varit stabil. Återkommer om detta. Kan också notera att några av mina MiniZinc-modeller är portade från just Tailor/Essence'.


Global Constraint Catalog


Global constraint catalogue uppdaterades 2008-11-15. Det var några nya constraints, framförallt geost och andra packnings-constraints.

Det gjordes då också en strukturell förändring av sajten med ett nytt URL-schema. I stället för URL-ar såsom http://www.emn.fr/x-info/sdemasse/gccat/sec4.5.html (för alldifferent_cst), så är URL-en numera http://www.emn.fr/x-info/sdemasse/gccat/Calldifferent_cst.html, dvs .../C följt av constraint-namnet. Jag har dock inte ändrat referenserna i mina MiniZinc-modeller på My MiniZinc page; däremot har nya modeller den nya URL-en.


Gecode


Gecode har inte kommit ut med någon ny officiell release sedan augusti 2008. Däremot har Gecode/flatzinc uppdaterats (SVN-versionen) några gånger för att stödja nya versioner av MiniZinc. Som tidigare sagt är Gecode/flatzinc min favorit-MiniZinc-solver.


Gecode/R


Gecode/R är ett Ruby-gränssnitt till Gecode:

Gecode/R provides access to many, but not all, of the features in Gecode 2.2.0. Gecode/R is only a modelling interface, it does not provide support for e.g. creating new propagators.

Version 1.0 kom i september. Har inte kollat in Gecode/R så mycket, vilket emellanåt förvånar mig...

Comet

Comet är ett constraint programming-system som bygger på "local search". Det har kommersialierats och en tidsbegränsad version av 1.02 finns nu att ladda ner på Dynadec.

Denna version är mer kompetent och komplett än förra, men det är nu ännu fler skillnader mot det som beskrivs i boken Constrant-based local search av Pascal Van Hentenryck, Laurent Michel.


Nya MiniZinc modeller


Sedan sist har det skrivit ett flertal nya MiniZinc-modeller (och några har uppdaterats men det - med ett undantag - noteras inte här nedan). Som vanligt finns de alla samlade på My MiniZinc page.

Referenser och oftast en kort förklaring finns att läsa i respektive modell.

Pyssel och andra matematiska förströelse



GLPK


GLPK (GNU:s Linear Programming Kit) är en open source-projekt för linjär/heltals-programmering. GLPK har bl.a. ett AMPL-liknande språk kallat MathProg varpå följande MathProg-exempel har konverterats till MiniZinc. Några av de allra största exemplen har - ännu - inte konverterats.


Global constraints


En handfull global constraints från Global constraint catalogue har skapats:

Operations research, linear programming, integer programming

Kommentaren "Williams" refererar till den mycket trevliga boken om modellering inom operations research och matematisk programmering: Model Building in Mathematical Programming (4th edition), skriven av H. Paul Williams.

Combinatorial


Övrigt



Slutord


Det har sedan länge insetts att målgruppen för ovanstående saker i svensk språkdräkt inte är så väldigt stor, varför det har tänkts att starta en separat blogg på engelska som endast handlar om constraint programming och relaterade paradigm såsom nyheter samt nyskrivna modeller. Mer om detta senare.

Posted by hakank at 10:51 EM Posted to Constraint Programming | Comments (4)