« Digital grusväg 1/2008 ute! | Main | Ubiquity 0.1 - kommandoradsfunktionalitet i Firefox »

augusti 23, 2008

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

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


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

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


Personliga favoriter


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

Modeller

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


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


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


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


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


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

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


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


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

Posted by hakank at augusti 23, 2008 08:35 FM Posted to