« Mailen strular förhoppningsvis inte längre | Main | Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller »

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

Drinking game
ETT + ETT+ ETT+ ETT+ ETT = FEM
enkelt korsord (standardexempel inom constraint programming)
Devil's word (en MiniZinciifiering av programmet Devil's Word)
Defending a castle
ett underligt tal
"Column Sum Puzzle"
3 jugs problem
SEND MOST MONEY

exempel från Operations Research / integer programming-litteraturen

crew allocation
Giapetti (exempel från artikeln The GNU Linear Programming Kit)
cutting stock
critical path
maximum flow
organize a day
PERT
bin packing
xkcd's knapsack-problem (se http://xkcd.com/287/)
diet
subset sum

icke-linjär programmering

Cyclohexane
dynamisk optimering
circle intersection

andra exempel på modellering i MiniZinc

Hammingavstånd
Latin Squares
Färglägga en karta
Fibonacci numbers (använder array eftersom MiniZinc inte stödjer rekursioner)
global constraint cycle
minsta antal mynt för att betala exakt 1..99 cent
power set
partitions
enkel talteori, och sieve
rot13
de Bruijn-sekvenser


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 april 14, 2008 06:58 EM Posted to Constraint Programming

Comments

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?

Posted by: Andreas Larsson at april 21, 2008 10:48 FM

Andreas: Efter lite (ja, inte så lite) skrivande på ett svar inser jag att det blir för långt för en kommentar så det blir en egen blogganteckning. Kommer förhoppningsvis senare ikväll.

Titelns arbetsnamn är för närvarande "Några kommersiella applikationer med constraint programming-tekniken samt lite om operations research", men jag förbehåller mig rätten att ändra denna titel.

Senare: det blev nästan den titeln: Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller.

Posted by: hakank [TypeKey Profile Page] at april 21, 2008 06:43 EM