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
* (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 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.
På 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)