« december 2007 | Main | maj 2008 »

april 27, 2008

Mitt OpenOffice Calc-/Excel-skov

Som tidigare antytts har jag tidigare kollat in OpenOffice Calc och Excel. IRL har detta till mina vänner beskrivits som mitt OpenOffice/Excel-skov och det har i vissa fall även utlovats en rapport om detta.

Här är en reseskildring över förloppet, kompletterad med några exempel som gjordes då. Samtliga exempel utnyttjar Solver/Problemlösaren eftersom det är den finessen som jag uppskattade mest.


Excel/OpenOffice Calc


Av lite olika anledningar började jag ordentligt kolla in Excel/OpenOffice Calc under hösten 2007 och blev riktigt överraskad hur kompetent det är. Jag hade kollat in det för många år sedan men blev då inte speciellt road, troligen för att själva spreadsheet-metaforen inte passade mig då.

Dataanalys har istället gjorts i främst R eller rena standardprogramspråk (C, C++, Java, Perl, Python, Ruby etc) med eller utan numeriska tillägg, eller med matematiska system såsom Maple/Matlab (eller dess kloner såsom MuPAD, Octave) etc etc.

I och för sig har (eller snarare hade eftersom Windowsmaskinen är trött numera) jag tillgång till Excel 2003, men eftersom jag främst är en Linux-människa kollade jag mest in OpenOffice Calc som är valdigt kompatibel med Excel 2003.

Som av en slump sträcklästes först Bill Jelens praktverk Special Edition Using Microsoft Office Excel 2007 (>1000 sidor). Trots att boken är för Excel 2007 är det väldigt mycket som är applicerbart för Calc, framförallt formler och sätt att tänka. (Jag läste dock kursivt de första 300-400 sidorna som pratar om det nya GUI-t för Excel 2007).

Sedan införskaffades Microsoft Office Excel 2007 - Data Analysis and Business Modeling skriven av Wayne Winston. Denna bok innehåller många fler fullständiga och kommenterade exempel (än Jelens bok). De mest intressanta var avsnitten kring planering, simulering etc, framförallt modellerna med linjära-/heltals-modeller.

En asidekommentar i ett av dessa avsnitt hänvisade till Winstons egen bok Operations Research - Applications and Algorithms, och den införskaffades därför (ibland är bokbeställningsbenägenhetströskeln väldigt låg). Det är en alldeles förträfflig introduktion inom området Operations Research (OR, operationsanalys på svenska). För böcker som därefter lästes inom OR, se litteraturlistan i Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller.

Ungefär i samband med testningen av OR-exemplen började jag fundera på hur man implementerade problem såsom SEND + MORE = MONEY och liknande småpyssel i Excel/Calc. En del andra problem implementerades också, vara några presenteras nedan.

Det gemensamma med dessa problem är att de använder Solver/Problemlösaren, en av de mest avancerade funktionerna i systemen. Se vidare nedan under Solver/Problemlösaren.


Ett tag var allting smör och solsken (eller vad det nu heter), men efter ett tag blev begränsningarna i systemet mer och mer tydliga: Excels Solver kan inte hantera fler an 200 beslutsvariabler; den Solver som användes i OpenOffice Calc kan vara långsam och hanterar inte icke-linjära problem (ibland kan man modellera runt denna begränsning men det är ofta rätt trixigt). Det var då jag gick över till att modellera i andra modellspråk, något som beskrivs i Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller.


Solver/Problemlösaren


Som ovan nämndes är OpenOffice Calc/Excel väldigt kompetenta och kan göra en massa saker. Det enda jag tänker att beröra här är en av de mest kraftfulla funktionerna: Solver (OpenOffice Calc, eller engelskspråkiga Excel)/Problemlösaren (svenskspråkig Excel).

Kortfattat kan säga att Solver möjliggör lösningar av vissa typ av problem genom att optimera vissa värden på ett smart sätt. Man kan säga att Solver testar en massa olika lösningar och väljer den (eller en av flera) som är bäst givet det kriterium man angivit.

OpenOffice har ingen inbyggd solver, men det ska komma en sådan i version 3. Tills vidare kan rekommenderas det Solver-paket (.oxt-paket) som Kohei Yoshida skapat: Calc Optimization Solver. Tyvärr hanterar det endast linjära problem.

Istället för att förklara detaljerna hur man gör för att använda Solver, länkas här till några bra introduktioner. Jag rekommenderar även att någon av ovan nämnda Excel-böcker studeras (där står mycket annat matnyttigt om Excel). Samtliga beskriver Excels Solver, men det funkar i princip på samma sätt i OpenOffice Calc.

* Teaching Linear Programming using Microsoft Excel Solver. Introduktion i linjär programmering, med instruktion hur man använder Solver.

* Microsofts egen dokumentation: Introduction to optimization with the Excel Solver tool

* Learn to Use the Excel Solver to Make Money-Saving Decisions: Build Models to Allocate Scarce Resources

* (Bok) Paul Cornell: Beginning Excel What-if Data Analysis Tools - Getting Stated with Goal Seek, Data Tables, Scenarios, and Solver.

Några exempel med Solver/Problemlösaren

Här är några exempel på hur man använder Solver/Problemlösaren. Samtliga är skrivna i OpenOffice Calc version 2.4, och de borde fungera även i Excel 2003 eller senare. Tyvärr är min Excel 2003 inte tillgänglig för tillfället så de kan inte testas där, men vid modelleringen i höstas funkade samtliga exempel i båda systemen.

I dokumenten beskrivs vilka celler/områden som är relevanta för Solver.

För jämförelsens skull länkas även till motsvarande MiniZinc-modell. (Om någon skulle vara intresserad av motsvarande modeller i AMPL är det bara att hojta.)

Not: Inga macros har använts.

Exempel Calc/Excel MiniZinc
Schemaläggning (från Winstons OR-bok) Scheduling_Winston.xls post_office_problem.mzn, mer generell modell: post_office_problem2.mzn
Produktplanering (chess set) chess_sets.xls chessset.mzn
Diet-problemet diet.xls diet1.mzn
Knapsack knapsack.xls knapsack2.mzn
Set covering (Winstons brandstationsexempel) set_covering_winston.xls set_covering.mzn
SEND + MORE = MONEY send_more_money.xls send_more_money.mzn
Växling av pengar (knapsack-variant) money_changing.xls money_change.mzn
Seseman-problemet seseman.xls seseman.mzn, mer generell modell: seseman2.mzn

Slutord

Jag har även kollat in Gnumeric som är en annan Excel-kompatibel öppenkod-produkt. Där finns en solver men den blev jag aldrig vän med.

Posted by hakank at 07:45 EM Posted to Constraint Programming | OpenOffice Calc/Excel | Operations research | Comments (3)

april 26, 2008

Ett litet april-pyssel

För tre år sedan (2005) publicerades ett Aprilpyssel. Det är dags att åter ta upp denna tradition.

Naturligtvis är nedanstående pyssel - på något sätt - kopplat till det jag kollar in just nu, dvs constraint programming/integer programming/MiniZinc.


Denna typ av pyssel har ett specifikt namn - som jag inte avslöjar just nu - och tillhör en grupp mer generella problem (som vad jag vet inte har något speciellt namn, dock med åtminstone ett undantag).


Problem


Inledning

Betänk följande binära matris (dvs endast 0 och 1 förekommer) där summorna för respektive rader och kolumner visas i fetstil.


1 010
1 010
0 000
  020

Vi sammanfattar respektive summor i två vektorer:

- radsummor: [1,1,0]

- kolumnsummor: [0,2,0].


Dagens pyssel går nu ut på, att givet en radsummavektor och en kolumnsummavektor, lista ut vilken matris som ligger som grund för dessa summor.


Delproblem

Det är två stycken delproblem som vardera på något vis kan ge ledtråd till lösningen av det andra delproblemet.

Delproblem a

radsummor= [0,2,2,2,2,2,8,8,4,4,4,4,4,0]
kolumnsummor = [0,0,0,12,12,2,2,2,2,7,7,0,0,0]

Delproblem b

radsummor = [0,0,8,2,6,4,5,3,7,0,0]
kolumnsummor = [0,0,7,1,6,3,4,5,2,7,0,0]


Ett av dessa problem har jag snott ("kopierat" är en mer korrekt term för detta förfarande) från någonstans, det andra har jag hittat på själv. Ordningen mellan delproblemen, liksom presentationen av dess härlednad i föregående mening, är faktiskt slumpad med ett slumptalsprogram, nämligen R.


Vinnerier etc

Vinnaren i detta pyssel anses den vara som först till pysselledningen:

- p) ger korrekt svar på båda delproblem

- q) samt redogör för hur problemet löstes.

"Till pysselledningen" definieras här som antingen en kommentar i denna blogganteckning, eller ett mail till hakank@bonetmail.com.

Vinnaren erhåller i kommentarerna till denna blogganteckning eller i en separat blogganteckning ett "Bra gjort, X!", där X ersätts av vinnarens namn/handle/smeknamn etc. Möjligen kommer "Bra gjort" att ersättas av synonymiserade uttryck och/eller kompletteras med kraftfullare attribut (såsom "Mycket") då i kombination med erforderliga ändringar av resten av uttrycket för att det ska bli så korrekt svenska som möjligt (byte av stor till liten bokstav etc).

Pysselledningen förbehåller sig att dela ut noll (0) eller flera stilprogram till förslag som ej är korrekt lösta, inkompletta men på något sätt (subjektivt bedömt) förtjänar ett stilpoäng, men även till korrekta lösningar som förtjänar sådan stilpoäng. Negativa stilpoäng kommer inte att delas inte, åtminstone inte officiellt. Eventuella felaktigheter som eventuellt påpekas för eventualla lösningsförslag definieras inte som negativa stilpoäng i detta sammanhang.

Till allt detta kommer vinnaren även att erhålla en av följande vid nästa eller någon (dock endast en) efterföljande IRL-träff (den virtuella glassen är än så länge alldeles för blaskig för att bjuda på):

- glass
- öl
- kaffe
- te
- eller annan motsvarande dryck

Not: Glass/öl/etc kan delas ut av den person som råkar utgöra pysselledningen i helt andra sammanhang och av helt andra skäl. Detta ska då ses som något som är hetl frikopplat från denna pysseltävling.


Lösningens presenterande etc


Det är planerat att presentera den av pysselledningen ansedda korrekta lösningen (inklusive några kommentarer samt åtminstone en vidarelänk) efter en viss tid har s.a.s. runnit, inklusive en MiniZinc-modell. Exakt när detta sker beror på.

Slutord

En av de saker som intresserar mig är hur man går till väga för att lösa slika problem. Därför är punkt q) viktig i lösningen. Det behöver inte vara (men kan vara) speciellt långt svar, men ange gärna metod, systemstöd samt - vilket är lika intressant - eventuella felskär.

Slutligen: Förutom "Lycka till!" kan noteras (vilket säkert redan gjorts av den observante läsaren) att ovanstående pysselformulering kunde - om omständigheterna vore annorlunda - göras mycket kortare. Men det är de inte så det gjordes inte.

Posted by hakank at 10:25 FM Posted to Constraint Programming | Pyssel | Comments (8)

april 23, 2008

Bloggareträff uti Malmö, söndagen 4 maj (2008), klockan 13:00 på Kin Long

Berätta helst om du tänker komma genom en kommentar här eller via epost till mig: hakank@bonetmail.com.

Ja, det är väl inte så mycket mer att säga.

Mer än länka till information om tidigare bloggareträffar där det står vad vi tenderat att prata om och inte prata om (indirekt genom avsaknad av beskrivning av sådana ämnen), vem som har tenderat att komma och vem som inte ha tenderat att komma (även det indirekt genom att dessa personer - och det är väldigt många bara i Sverige som inte kommer på dessa bloggmiddagar - som inte står upptagna i listan över deltagare).

Välkommna du/ni som har bloggartendenser och befinner dig/er i Malmö vid den rubriken angivna tid-/platspunkten!

OK, en sak till då. Här är en karta till restaurang Kin Long, det är precis till väster om stora hotellet vid Malmös mittpunkt: Triangeln.

Posted by hakank at 09:51 EM Posted to Bloggmiddagar | Comments (10)

april 21, 2008

Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller

CP nedan är förkortning för Constraint Programming.


Andreas Larsson frågade följande i kommentaren till MiniZinc-sida samt fler MiniZinc-exempel:


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?

Det tänktes först skrivas en rätt kort kommentar som sedan växte till en alldeles egen blogganteckning. Hoppas att du fått svar på din fråga, Andreas.


Kommersiella tillämpningar


Först: jag känner inte till några näringslivsimplementationer specifikt i MiniZinc.

Sedan: Jag tillåter mig att utöka svaret lite grand med länkar till saker inom både constraint programming och operations research.

Här är en lista på några kommersiella applikationer av CP:

Applications Of Constraint Programming

Sedan kan man kika på kunderna till några av constraint programming-systemtillverkarna.

Koalog: Clients.

SICStus: Customers. SICStus är en (svensk!) Prolog-implementation (en av de mest kraftfulla) med CP-stöd. Några kunder använder CP-teknologin.

ILOG: ILOG CP med en lång lista på ILOGs kunder. ILOG har dock andra produkter, t.ex. CPLEX som är en av de mest kraftfulla solver för linjär/integer/mixed programmering. ILOGs modelleringsspråk OPL är för övrigt en av inspirationskällorna till MiniZinc.

Mer allmänt kan sägas att många av de problem som studeras inom constraint programming kan mycket väl tillämpas inom näringslivet och har även gjorts även om jag inte kan ge några bättre länkar just nu.

My MiniZinc page finns ett flertal exempel under rubriken "Operations Research" (se även nedan). Det är några enkla skolexempel på problem där constraint programming-metoden används: schemaläggning, rutt-planering, lagerhantering etc. Flera av dessa exempel har jag tagit från läroböcker i just operations research (länkar till dessa böcker finns nedan). På MiniZincs exempelsida finns flera sådana exempel, och benchmark-katalogen finns en hel del större problem.

(Ja visst ja - och detta har inget med näringslivsimplementationer att göra - jag har ju glömt bort att länka till den obligatoriska Sudoku-lösningen: modellen, data, resultatet. Notera att modellen är för arbiträr dimension, exemplet är för det vanliga 3 x 3-problemet.)

Operations Research

För en introduktion i operations research se wikipedia operations research.

OR använder traditionellt (bl.a.) matematisk programmering, såsom linjär programmering, heltalsprogrammering (integer programming), och mixed integer programming (blandat flyttal och heltal). Det som numera komplicerar en strikt uppdelning av constraint programming å ena sidan och OR å andra är:

* Metoderna i CP och OR har sedan ett antal år börjat att närma sig/befrukta varandra.
* För t.ex. MiniZinc-systemet kan nämnas att en av de solvers som det redan nu finns stöd (ECLiPSe's eplex) använder just linear/integer programming. Det gör att det blir än mer flytande gränser. (Och i vissa av mina CP-modeller används standard-trick specifikt från integer programmering-modellering, se t.ex. knapsack_investment.mzn).


Här är några system som använder sådan matematisk programmering:

* AMPL. Det finns en demo (finns för Linux/Unix, Windows) att ladda ner och leka med. Demoversionen har dock endast stöd för cirka 300 variabler. AMPL är mitt favoritsystem inom denna genre; de solvers som används är rasande snabba, speciellt CPLEX som även finns att ladda ner som demoversion.

Kan passa på att här nämna att flera av mina MiniZinc-modeller först skrevs i AMPL under mitt AMPL-skov i höstas/vintras (se nedan). Det har funderats på att skapa en motsvarande "My AMPL page".

* GLPK är ett open source-system som har ett modelleringsspråk som är mycket likt AMPL (bygger på en tidigare version av AMPL), men är inte lika snabbt eller kraftfullt som AMPL (+ dess olika solvers). Tyvärr klarar GLPK inte icke-linjär programmering speciellt bra.

* Dash Optimization XPress Mosel. Här finns några exempel.
Man kan notera att de allra flesta problemen i Martin Chlonds underbara samling Integer Programming in Recreational Mathematics är skrivna i XPress-MP (och som antyddes i slutet av Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc finns de översatta till både AMPL och MiniZinc men inte tillräckligt hyfsade för att publicera.)

Några andra system nämns nedan.


Några böcker om Constraint Programming


Böckerna listas i princip i läsordning.

Kim Marriott, Peter J. Stuckey Programming with Constraints - An Introduction. Min första CP-bok. Mycket trevlig med många exempel och detaljer. Exemplen är Prologvarianterna (Constraint Logic Programming). Både Marriott och Stuckey tillhör hjärnorna bakom MiniZinc.

Pascal van Hentenryck: Constraint Satisfaction in Logic Programming (finns inte just nu på Bokus). En av de första böckerna om Constraint Logic Programming. Flera av standardexemplen populariserades här.

Krzysztof Apt, Mark Wallace Constraint Logic Programming using Eclipse. Beskriver det Prolog-inspirerade systemet The ECLiPSe Constraint Programming System både vad gäller Prolog-delen och constraint-delen.

Pascal van Hentenryck, Laurent Michel Constraint-Based Local Search. Denna bok presenterar systemet COMET som löser optimeringsproblem med s.k. local search, vilket är en annan metod än den som beskrivs i ovanstående böcker.

Boken är mycket intressant just eftersom den beskriver moderna och mycket snabba tekniker samt dokumenterar ett specifikt system. Tyvärr är den version som finns nedladdningsbar inte riktigt kompatibel med boken så man måste mixtra en hel del.

Krzysztof Apt Principles of Constraint Programming. Detta är en ganska teoretisk bok som går igenom tekniken bakom constraint programming. Används vad jag förstår mycket på universiteten.

Thom Frühwirth, Slim Abdennadher Essentials Of Constraint Programming. Systematisk översikt över constraint programming. Det speciella är att man nästan genomgående använder Constraint Handling Rules (där Frühwirth är en av de stora).


En bok som funderas på att införskaffas är samlingsvolymen Handbook of Constraint Programming. Den innehåller många essäer om state-of-the art inom forskningsområdet. Den är tyvärr lite dyr.


Några böcker om Operations Research


Samtliga dessa har lästs, och presenteras i strikt läsordning (med början hösten 2007).

Microsoft Office Excel 2007 - Data Analysis and Business Modeling. Det var faktiskt denna bok som fick mig börja med OR och sedan constraint programming. Några av kapitlen innehåller exempel från OR. En liten fotnot hänvisade till Winstons OR-bok (se nedan) och sedan var det kört.

(Jag har länge tänkt skriva om mitt Excel-skov som föregick OR- och CP-skoven. Det kommer förhoppningsvis någon gång framgent.)

Wayne Winston Operations Research - Applications and Algorithms. Många exempel, modellerna skrivna i Excel eller Lindo/Lingo.

Hamdy A. Taha Operations Research - An introduction. Också det en introduktionsbok.

Både Winston och Taha är alltså introduktionsböcker. Fastän Taha har exempel i AMPL (och Excel) så tycker jag nog att Winstons bok är något bättre, vilket kan beror på att det var den jag läste först. Båda har många exempel och mycket förklaringar.

En tanke: en annan förklaring till att jag tycker mer om Winstons bok kan vara att jag tyckte det var roligare och mer givande att översätta modeller från Lindo/Lingo än att se färdig kod som i Tahas bok.

Robert Fourer, David M. Gay, Brian W. Kernighan: AMPL: A Modeling Language for Mathematical Programming. AMPL-bibeln. Går minutiöst igenom de olika AMPL-konstruktionerna. Tyvärr inte så mycket om principer för modellering som jag hade hoppats. (Jullklappsbok 2007.)

H. P. Williams Model Building In Mathematical Programming, en översikt över tekniker inom matematisk modellering. En klassiker. Tyvärr gav den mig inte så väldigt mycket men jag är glad att ha läst den.

Lundgren, Rönnqvist, Värbrand: Optimeringslära. En mycket trevlig svensk bok om matematisk programmering.

Tony Hürlimann Mathematical Modelling of Puzzles and Games. En trevlig, ny och rätt okänd bok om matematisk modellering. Vad jag vet går den inte att få tag i på annat sätt än via Lulu.com, antingen att ladda ner som PDF eller beställa en träd-bok (ingendera är speciellt dyr). Exemplen är kodade i systemet LPL. En rolig feature är att koden finns som URL-ar, t.ex. chess4. Många av problemen är från Martin Chlonds Integer Programming in Recreational Mathematics (se ovan).

Så kommer några fria-att-ladda-ner-böcker:

Applications of Optimization with XPress-MP. Introduktion i modellering. Går igenom många modeller med:
- pratversion
- matematisk (generell) modell
- implementation i XPress-MP

Optimization Models For Decision Making: Volume 1, speciellt kapitel 7 "Modeling Integer Programs" var intressant.

Linus Schrage Optimization Modeling with LINGO som till viss del är som "Applications of Optimization with XPress-MP" men är inte riktigt lika systematisk vad gäller modellerna.

Det är alltså detta jag har hållt på med sedan höstas och som orsakade bloggtystnaden.

Några nya MiniZinc-modeller

Sedan förra bloggningen har jag lagt till några nya MiniZinc-modeller på My MiniZinc page (samt även klassifierat modellerna bättre än tidigare). T.ex.:

* knapsack_investment.mzn, ett exempel på optimering av investeringar från ovan nämnda bok Optimeringslära.

* perfect_shuffle.mzn, en modell som visar utvecklingen av en perfekt blandning (en riffelblandning där man blandar exakt varannat kort från de två korthalvorna, en inte helt lätt bedrift att utföra). Se vidare out-shuffle. Med modellen kan man bl.a. se att det endast behövs 8 perfekta blaningar för att återställa ordningen i kortleken (vilket man redan visste och det var därför som man intresserade sig för matematiska modeller av perfekta blandningar:-).

* några varianter på set covering-problemet, samtliga exempel från boken "Optimeringslära":
- set_covering4.mzn
- en variant av samma problem men där mängder används istället: set_covering4b.mzn
- samt set_covering5.mzn som är en form av schemaläggning med lite olika typer av begränsningar.

* två nya global constraints: nvalue.mzn och den mer generella nvalues

* partial_latin_square, som är en variant av latin square.

* en ny variant av set partition, set_partition.mzn

Posted by hakank at 08:43 EM Posted to Constraint Programming | Operations research | Comments (6)

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 06:58 EM Posted to Constraint Programming | Comments (2)

april 11, 2008

Mailen strular förhoppningsvis inte längre

Till dem det berör:

Mail till mitt vanliga mailkonto ( hakank@bonetmail.com ) funkar inte för tillfället. Möjligen beror detta på underhållsarbete hos mailprovajdern. Lika möjligen kan detta mailavbrott vara över helgen. Jag vet inte eftersom det inte kommit någon information och sajten deras är stängd för underhåll.

Vill ni nå mig så använd hakank@gmail.com i stället.

Lördag klockan 17:37 började mailen funka igen.

Uppdatering Lördag 19:15 Nähä. Det slutade funka igen. Så ovanstående gäller fortfarande. (Ledsen alla ni med RSS-bevakare för denna fortlöpande uppdatering.)

Uppdatering Söndag 19:28 Nu beslutar jag att mailen verkar vara OK.


(Eftersom jag nu tydligen har börjat blogga så smått igen - två bloggningar i samma månad ! - kanske det berättigar till att inbjuda till en Malmö-bloggareträff igen? Eller krävs det mer bloggaktivitet för sådant? Någon gång i slutet av april/början av maj? På King Long blir det i så fall. En söndag eller torsdag?)

Posted by hakank at 10:36 EM Posted to Diverse vetenskap | Comments (4)

april 05, 2008

Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc

Minizinc är ett relativt nytt constraint programming-system (startade 2005). Det tillhör G12-projektet som är menat att bli ett öppet (som i open source) state-of-the-art-system.

Samtidigt som det mer kompletta systemet Zink håller på att utvecklas, utvecklas Minizinc en mindre variant som även föreslås att användas som ett gemensamt språk för benchmarks av olika constraint solvers (dvs de system som faktiskt löser problemen, se nedan).

Zinc (storebrodern) finns inte tillgängligt för närvarande. Det finns däremot Minizinc, dels i en officiell version 0.7.1, dels en utvecklingsversion (jag använder utvecklingsversionen). Se vidare Download för nedladdningar.

Specifikationen för både Zinc och MiniZinc är Zinc spec (PDF). Detta dokument och andra nyttigheter finns via MiniZinc and FlatZinc. Uppdaterade versioner av dokumenten finns i utvecklingsversionen.

Många Minizinc-exempel finns här. Fler exempel finns i distributionens kataloger examples respektive benchmark samt till viss del i katalogen test/minizinc.

Jag tycker att Minizinc är ett mycket trevligt och lättarbetat system. Språket har syntaktiskt socker på en bra nivå och är numera min favorit bland constraint programming-systemen.

Det kommer att bli mycket intressant när Zinc släpps eftersom det har en massa skoj finesser som jag saknar i Minizinc, men jag lämnar det för nu. Här nedan kommer jag alltså i stort sett endast att prata om Minizinc.


Lite om Minizinc


En av de stora fördelarna med att använda constraint programming-språk liknande Minizinc är att de är deklarativa, dvs man beskriver vad som ska göras och inte hur saker ska göras (så är i alla fall idealet).

Prolog är ett av de mest kända exemplen på denna typ av programspråk. [Några mindre kända sådana språk är inom stable models/answer set programming-paradigmet såsom smodels/lparse, som nog kan uppfattas som än mer magiska än Prolog.]

Minizinc är dock inget "komplett programspråk" såsom Prolog, t.ex. saknas stöd för rekursion (detta av design för att göra det enkelt att arbeta med för olika solvers), det finns ingen filläsning förutom inkluderande av andra Minizinc-modeller eller data, hantering av strängar är synnerligen begränsat etc.

Trots dessa begränsningar är kan väldigt många problem modelleras i Minizinc. Se den officiella exempelsamlingen som innehåller olika typer av standardproblem från constraint programming, operations research och matematisk programmering. Nedan finns något av det som jag själv knåpat ihop.


Några speciellt trevliga saker i Minizinc

- definition av predicate

Man kan definiera predikat som sedan kan återanvändas via include-direktivet. Det finns en samling sådana i lib/zinc/globals.mzn som är väl värt att studera.

(I Zinc kommer det att finnas möjlighet att definiera funktioner som returnerar värden, men i Minizinc använder man samma teknik som i Prolog för att "returnera" värden, dvs att ange returvärdet i parameterlistan.)


- "bidirectional" predikat

Liksom Prolog har Minizinc den trevliga egenskapen att predikat kan vara "bidirect", dvs att flödet mellan parametrarna kan verka åt båda hållen, kan vara ut- eller in-data. Ett enkelt exempel på detta är konvertering mellan tal och en vektor (givet en bas). Jag har definierat toNum på följande sätt.

predicate toNum(array[int] of var int: vec, var int: n, float: base) =
let {
int: len = length(vec)
}
in
% summera ihop elementen i vec för den givna basen
n = sum(i in 1..len) (
ceil(pow(base, int2float(len-i))) * vec[i] % se nedan för varför denna används
)
% samtliga element i vec måste vara 0
/\ forall(i in 1..len) (vec[i] >= 0)
;

Poängen är att man kan använda detta predikat för att konvertera från ett decimaltal (n) till en vektor (vec) av heltal i den givna basen base, eller konvertera från vektorn av heltal till ett tal (givet en bas). toNum används t.ex. i debruijn_binary.mzn, vilken se. (I teorin skulle man också kunna räkna ut vilken bas som används givet vec och n, men det går inte i Minizinc eftersom pow() inte kan användas på en var-deklarerad variablen utan måste definieras som en fix parameter.)

Här blir n = 7

% ...
constraint
% ....
toNum([1,1,1], n, 2.0)
;

och här blir vec = [1,1,1]:

% ...
constraint
% ...
toNum(vec, 7, 2.0)
;


Det är mycket denna bidirektionella egenskap gör att programmering i Minizinc (och liknande deklarativa språk) känns riktigt magiskt. Och det är synnerligen skoj.

Tyvärr är Minizinc hårt typat så man måste själv konvertera flyttal till heltal, vilket frustrerar mig. [I Zinc/Minizinc-specen står att sådan konvertering kommer att göras automatiskt i storebroderna Zinc, men inte i Minizinc. Jag hoppas att specifikatörerna besinnar sig.] Och eftersom pow()-funktionen för heltal inte funkar i den aktuella versionen är man tvungen att använda float-varianten vilket innebär att man måste använda göra ceil(...)-hacket. Det är ju en hel del sådant i betaversioner som det tar tid att komma på och runt.

Ett något mer avancerad exempel på bidirection är mortgage.mzn (beräkning av lån), som är ett (annat) standardexempel i constraint logic programming (där ofta just Prolog användas som grund eller inspiration för implementationerna). På samma sätt som i toNum kan samma kodbas - med olika initialvärden - användas för att räkna ut de andra parametrarna. Se kommentarerna i programmet för vidare info. Not: för närvarande är det endast ECLiPSe-solvern som klarar detta problem.

Exempel på mer användande av toNum finns i programmen debruijn_binary och gray_code.mzn som beskrivs mer nedan.


* global constraints

I filen lib/zinc/globals.mzn finns ett flertal "global constraints" implementerade (och det antyds att det kommer att fyllas på med fler). Global constraints kan ses som standardrutiner ("standardmönster") att lösa vissa typer av (del)problem, t.ex. all_different(x) som kräver att samtliga element i en vektor ska vara olika, global_cardinality_constraint som räknar hur antal förekomster av olika element det finns i en vektor (och med bidirect-principen kan man ställa krav på antalet förekomster), etc.

Det finns en stor samling definitioner/beskrivningar av sådana global constraints (men tyvärr inga implementationer) i Global Constraint Catalog.

Min personliga fascination för sådana globala constraints är på modelleringsnivå eftersom de kan ses som byggstenar (tankehjälp) för modellering. Som övning har några av dessa implementerats såsom circuit.mzn (som i min implementation bygger på några observationer kring s.k. orbits i permutationer), cycle etc.

En stora vinst med sådana global constraints är att underliggande solvers kan göra specialoptimimeringar, vilket naturligtvis snabbar upp systemen. Studiet av sådana global constraints är en viktig del i forskningen kring constraint programming.


* stöd för flera olika solvers

Språket Minizinc är egentligen bara en del av systemet och det löser inga problem. I stället konverteras till ett annat språk (Flatzinc) som olika solvers kan arbeta med för att faktiskt lösa problemet. (Man skulle kunna översätta "solver" med "problemlösare", men eftersom det ryser varje gång jag använder den svenska versionen av Excels Solver så gör jag inte det :-). I distributionen finns det en solver med: flatzinc.

Redan nu finns det redan tre solvers: flatzinc, Gecode/flatzinc samt ECLiPSe-modulen minizinc. De gås igenom nedan.

Exempel

Som första lite längre kommenterade exempel visas här SEND + MORE = MONEY-problemet (saknas av någon anledning i Minizinc-exempelsamlingen). Problemet är helt enkelt: Byt ut bokstäverna mot unika siffror (0..9) i additionen SEND + MORE = MONEY. Det är ett paradigmatiskt exempel (dvs har "Hello, world"-status) i constraint programming-världen och finns i alla läroböcker.

Så här ser min rättframma implementation ut:

% globals.mzn innehåller den globala constrainten all_different
include "globals.mzn";

% definierar varje bokstav som en variabel
% de är samtliga heltal mellan 0 och 9
var 0..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 0..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;

% vektorrepresentationen av de 8 variablerna för att kunna
% använda all_different
array[1..8] of var int: fd =
[S,E,N,D,M,O,R,Y];


%
% De olika begränsningarna som ska göras, både för själva problemet och
% eventuella hjälpstrukturer
%
constraint

% all_different kräver att alla siffror ska vara olika
all_different(fd) /\

% definiera själva problemet, dvs hur relationen mellan bokstäverna
% ser ut
1000*S + 100*E + 10*N + D +
1000*M + 100*O + 10*R + E =
10000*M + 1000*O + 100*N + 10*E + Y
/\
% varken S eller M får vara 0
S > 0 /\
M > 0
;

%
% solve satisfy ger en lösning, dvs inget att minimera eller maximera
%
solve satisfy;

%
% utskriften
%
output [
% show(fd), "\n",
"S:", show(S), " E:", show(E), " N:", show(N), " D:", show(D),
" M:", show(M), " O:", show(O), " R:", show(R), " Y:", show(Y),
"\n\n",

" ", show(S), show(E), show(N), show(D),"\n",
" + ", show(M), show(O), show(R), show(E),"\n",
" = ", show(M), show(O), show(N), show(E), show(Y), "\n"

];

Sedan kör man programmet lite olika beroende på vilken solver man använder. Jag brukar testa med samtliga tre för att se vilken som är snabbast etc.

Minizinc (anropar flatzinc automatiskt)

minizinc send_more_money.mzn

eller programmet flatzinc direkt via konvertering till .fzn-format.


mzn2fzn send_more_money.mzn
flatzinc send_more_money.fzn

Gecode/flatzinc:

mzn2fzn send_more_money.mzn
fz send_more_money.fzn

ECLiPSe:

eclipse -e "minizinc:mzn_run('send_more_money.mzn',zn_options{solver:fzn_ic})"

Resultatet blir samma för alla

S:9 E:5 N:6 D:7 M:1 O:0 R:8 Y:2

9567
+ 1085
= 10652

Fler exempel

Här är några andra exempel som inte finns på MiniZinc-sajten eller i distributionen. Flera av dem är sådana jag brukar ha som standardproblem för att för att testa olika constraint-system vad gäller språk, performance och rent allmänt hur det är att arbeta med. T.ex. så kollade jag i höstas in AMPL (ett mycket trevligt system för "matematisk programming") men där var man i vissa fall tvungen att trixa ordentligt - i och för sig vedertagna och väl dokumenterade tricks - för att göra sådant såsom "all_different". Minizinc (och de flesta andra constraint system) har all_different implementerat som standard.


I Choco: Constraint Programming i Java gavs några exempel på problem som löstes i constraint programming-systemet Choco. Dessa har nu skrivits om i Minizinc. Som jämförelse länkas även till Choco-varianten.

* Planering av möbelflyttande, använder "global constraint" cumulative

furniture_moving.mzn (FurnitureMoving.java)

* Ett enkelt knapsack-problem (minimering)

knapsack.mzn (Knapsack.java)

* Least diff (minsta differensproblemet som beskrivs i ovanstående blogganteckning)

least_diff.mzn (LeastDiff2.java)

* Sesemans klosterproblem

seseman.mzn (Seseman.java). Se Sesemans matematiska klosterproblem samt lite Constraint Logic Programming för en förklaring av detta problem.


* set_covering_deployment.mzn

Implementation av exemplet på Set Covering Deployment för att optimera antal arméer i gamla romarriket. Problemet beskrivs i detalj i R.R. Rubalcaba Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs (PDF).


de Bruijn-sekvener och "arbiträra de Bruijn-sekvenser"


Jag har länge varit fascinerad att de Bruijn-sekvenserna och publicerat två (eller tre beroende på hur man räknar) webbaserade program:

- de Bruijn sequence, samma som Java Applet

- de Bruijn arbitrary sequences, där man använder "de Bruijn-egenskapen" men tillåter sekvenslängden bestäms av användaren.

Se respektive de Bruijn-sekvenser (portkodsproblemet) och de Bruijn-sekvenser av godtycklig längd för förklaringar av programmen.

Naturligtvis var detta en sak som skulle kodas i Minizinc. Första versionen av programmet byggde liksom webbversionen av "de Bruijn arbitrary sequences" på en speciell typ av graf som traverserades på ett visst sätt. Denna implementation var dock lite trixig att genereralisera till andra baser än n=2. Därefter skrevs en variant där man programmerar de Bruijn-egenskapen direkt i stället för att gå via en graf, vilket gjorde det hela mycket mer generellt och (oftast) snabbare.

Denna senare variant finns att beskåda i debruijn_binary.mzn. (Anledningen till att programmet heter "_binary" är bl.a. för att jag fick idén till implementationen några minuter efter jag kodat klart Gray-koder).


Exempelkörning
Problemet som jag kallar för 2/4/16 är base = 2, n = 4 (antal bitar att använda), m = 16 (längden på sekvensen). Programmet spottar ur sig lite olika typer av information:

- bin_code / binary_code: själva de Bruijn-sekvensen
- x är decimalrepresentationen av vektorerna som utgör sekvensen
- gcc (förkorting av global cardinality constraint) kontrollerar hur många olika siffror (0..base-1) som används. Det finns en begränsning att det måste vara exakt lika många förekomster av de olika siffrorna om det är matematiskt möjligt. Och det är just denna begränsning som gör problemet både intressant och tungt. I exemplet ser vi alltså att det finns 8 stycken 0:or och 8 stycken 1:or.
- sedan kommer listningen av "bit-representation" av vektorerna


n: 4 m: 16 base: 2
bin_code: [0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1]
gcc: [8, 8]
binary code: 0000100110101111
x (decimal representation):
[0, 1, 2, 4, 9, 3, 6, 13, 10, 5, 11, 7, 15, 14, 12, 8]
0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 1
0 0 1 1
0 1 1 0
1 1 0 1
1 0 1 0
0 1 0 1
1 0 1 1
0 1 1 1
1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0


Ett problem som är betydligt tyngre att lösa är 4/3/52, dvs bas=4 (dvs siffrorna 0, 1, 2 och 3 används), 3 "bitar" i varje tals vektor, samt en sekvenslängd på 52. Detta är så tungt så man inte kan använde solve satisfy utan måste använda sökheuristiker för att inte vänta förgäves på en lösning.

Genom experiment (föregånget av luskande i källkod och dokumentation hittades följande

solve :: int_search(x, "first_fail", "indomain_split", "credit(5,bbs(1))") satisfy

(Zinc-specen förklarar ingående vara parametrarna innebär, men det är helt enkelt lite olika metoder att traversera problemträdet.)

Den praktiska innebörden är att Eclipse-solvern hittar 1 lösning mycket snabbt, 65 lösningar på 5 sekunder (jag vet inte hur många olika lösningar som det total finns men det är väldigt många i alla fall). Med credit(4,bbs(2)) blir det 108 lösningar på 8 sekunder, credit(4,bbs(4)) hittar 1104 lösningar på 1:07 minuter etc.

En av dessa lösningar är följande

n: 3 m: 52 base: 4
bin_code: [0,0,2,0,0,3,0,1,0,1,1,0,2,1,0,3,1,1,1,2,0,1,2,1,1,3,0,2,2,0,2,3,0,3,2,0,3,3,1,2,2,1,2,3,1,3,3,2,2,3,3,3]
gcc: [13,13,13,13]
binary code: 0020030101102103111201211302202303203312212313322333
x (decimal representation):
[2,8,32,3,12,49,4,17,5,20,18,9,36,19,13,53,21,22,24,33,6,25,37,23,28,50,10,40,34,11,44,51,14,56,35,15,61,54,26,41,38,27,45,55,31,62,58,43,47,63,60,48]Total time 0.320s cpu (0.040 setup + 0.280 search)

Tyvärr har varken Flatzinc eller fz givit någon lösning alls på detta problem (jag har låtit båda programmen stå minst en timme varderna men sedan tröttnade jag). Om man däremot tar bort kravet att det ska exakt samma antal förekomster av siffror i sekvensen löser även fz problemet snabbt (men minizinc gör det inte).


Olika solvers


För närvarande finns tre olika solvers, med olika för- och nackdelar.


* flatzinc
Det är denna solver som följer med i Minizinc-distributionen.

Fördelar:
- det största fördelen är att den finns med i distributionen och kan alltså användas direkt.

Brister:
- ger endast en lösning oavsett hur många lösningar som problemet har. Detta är för mig en mycket stor brist.
- klen vad gäller beräkning av stora tal. T.ex. klarar den inte av grocery.mzn eftersom det är för stora tal inblandade.
- verkar inte vara känslig för de olika heuristikerna

* Gecode/flatzinc (fz)
Gecode/Flatzinc.

Kräver att Gecode finns installerad. Gecode är ett snabbt open source constraint programming-system (skrivet i C++) och har flera intressanta exempel. Det finns även en Java-implementation ovanpå Gecode Gecode/J. Båda dessa är väl värda att bekanta sig med helt oavsett Minizinc.

Fördelar:
- ofta mycket snabb, ibland snabbare än Eclipse-solvern (även fast man har heuristiker som hjälper Eclipse-solvern)
- ger flera lösningar (alla!) om det finns (såvida man inte "heuristicerar" bort dem)
- summerande statistik som indikerar hur svårt problemet är att lösa

Nackdelar:
- min uppfattning är att fz inte är lika känslig för sök-heuristikerna som Eclipse-solvern vilket gör att den kan vara långsammare än Eclipse-solvern för vissa problem
- klarar inte av vissa typer av flyttalsberäkningar, t.ex. mortgage exemplet ovan.
- kan reagera konstigt på sök-heuristikerna
- man måste installera gecode


* ECLiPSe
Kräver ECLiPSe Constraint Programming System. Det är en variant av Prolog (min favoritvariant och som användes i Sesemans matematiska klosterproblem samt lite Constraint Logic Programming).

För tillfället krävs en utvecklingsversion eftersom Minizinc-stödet ännu inte är officiellt släppt. Eftersom sajten crosscoreop.com kan bete sig konstigt vid hämtande av stora filer är att rekommendera att man hämta filerna från en av speglarna t.ex. http://sunsite.informatik.rwth-aachen.de/ftp/pub/mirror/ECLiPSe-CLP/.

Dokumentation hur man använder Minizinc-modulen finns i library(minizinc).

Ett tips är även att studera ECLiPSe-predikatet search/6 som är inspirationskällan för sök-heuristiken i Minizinc.


Fördelar:
- liksom fz mycket snabbt och ger alla lösningar
- klarar av flyttalsberäkningar (såsom mortgage)

Nackdelar:
- vissa saker är inte implementerade, såsom vissa set_operationer.
- man måste installera ECLiPSe-systemet.

Buggar eller brister

Här är några brister antingen i de aktuella implementationerna eller saker som stör mig i designen av språket.

* Utskrifen är inte fullständigt i den existerande beta-versionen. Det är trixigt att skriva ut mer komplicerade strukturer (se exemplen). Det finns för närvarande inget sätt att villkora så att man bara ska skriva ut vissa element i en var-deklarerad array (såsom endast de element som är större än 0). Till viss del är det ett desginbeslut, möjligen kommer fix() att lösa några av dessa problem.

* Typningen. Personligen tycker jag inte om den strikta typningen av float och int (det är enligt design) som gör att man explicit måste sköta sådant. T.ex. görs '/' (division) endast på flyttal och det gör att vissa problem blir mycket svårare att lösa (såsom några av Integer Programming-pysslen). Det är inte alltid det går att använda div-operatorn (som f.ö. är buggig i fz) eller att (på ett enkelt sätt) skriva om problemet så det inte använder division.

* Det saknas en solver som använder metoder från linjär programmering/heltalsprogramming (såsom simplex-metoden). Det antyds att det finns sådana men de är ännu ej släppta. I och för sig har ECLiPSe-systemet någon form av stöd för eplex i sin Zincinterface-katalog, men det har jag inte fått att fungera ännu. Uppdatering ett halvt dygn senare:: Jodå, eplex funkar för vissa typer av problem såsom några av exempeln i examples-kataloge; queens_ip.mzn, min_cost.mzn, product_lp och multidimknapsack_simple. Får alltså kolla in det mer...

Länkar
Annat som kan vara intressant.

* Integer Programming Puzzles (programmering av lösningarna av Martin Chlond). Detta är en härlig samling "heltalspyssel" (dvs där lösningarna är heltal, eller kan ses som heltal). Send More Money, Least Diff är några andra exempel på sådana problem.

När jag satt med AMPL i höstas konverterade jag i stort sett samtliga dessa problem från XPress till AMPL, och har nu kodat om dessa till Minizinc. Tyvärr är det inte alla Minizinc-implementationer som ger resultat inom rimlig tid. Ett projekt i vardande är att hyfsa till dem och sedan lägga ut dem på sajten.

Jag tänkte här egentligen länka till en del annat som jag hållt på med sedan oktober förra året, såsom Excel, Open Office Calc, Linear Programming, AMPL, GLPK, matematisk programming, Operations Research, andra constraint programming-system etc, men det blir i så fall i separata postningar.


Posted by hakank at 09:33 EM Posted to Constraint Programming | Comments (6)