« MiniZinc-sida samt fler MiniZinc-exempel | Main | Bloggareträff uti Malmö, söndagen 4 maj (2008), klockan 13:00 på Kin Long »

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 april 21, 2008 08:43 EM Posted to Constraint Programming | Operations research

Comments

*Wow* Hade jag betat av all den litteraturen hade min bloggtystnad varat betydligt längre! :)

Jag läste igår en offentlig handling i form av en kostutredning för en liten svensk kommun. De har idag ett antal kök som bereder mat till skolor, förskolor och äldrevård, men de är gamla och behöver renoveras för att uppfylla den nya lagstiftningen inom miljö, mat och hälsa. Dessutom ökar andelen åldringar så att ett nytt äldreboende behöver byggas.

Rapporten presenterade ett antal förslag, med redovisning av siffror för investeringar, arbetstillfällen och antal måltider. Dessutom ska hänsyn tas till miljöpåverkan, näringsvärde, matens temperatur, trivsel, med mera. Jag har faktiskt funderat på vad det finns för alternativ inom programmering för att lösa denna typen av icke-triviala analyser.

(Svaret på analysen ska naturligtvis bli att maten tillagas lokalt av ekologiska råvaror, så att det dels smakar och doftar gott, dels ger barn och gamla möjligheten att vara delaktiga i såväl utformning av matsedel som tillagning.)

Posted by: Håkan (hakke) at april 22, 2008 05:23 EM

Hakke: På ditt första utrop svarar jag ":-)".


Vad gäller kostutredningen skulle detta mycket väl kunna vara något för någon av de metoder som nämns ovan. Det krävs dock att det på något sätt går att kvantifiera kraven, t.ex. trivsel.

Det finns också en del förutsättningar som måste vara uppfyllda för att modellerna ska vara giltiga (vettiga). T.ex. för linjär programmering krävs att sambanden är faktiskt är linjära (proportionella), kan delas i flyttal, att ingångsvärdena stämmer etc. Gäller inte dessa förutsättningar krävs en annan typ av modell, t.ex. heltalsprogrammering eller icke-linjär programmering.

Sedan finns det andra metoder för att lösa denna typ av optimeringsproblem än de ovan nämnda, t.ex. (för att nämna några som iofs brukar räknas in i metoderna som tillhör operations research): genetiska algoritmer, tabu-sökning (en local search-metod) etc.

En längre lista över metoder med vidarelänkar finns på Wikipedias Optimization (mathematics).

Din parentetiska kommentar är intresserant eftersom dessa krav är inte helt lätt att kvantifiera.

Skriver man något om den/de bakomliggande modellen/modellerna som man bygger förslagen på?


Inom disciplinen operations research ingår även själva projektdelen, dvs hur man bemöter uppdragsgivarens krav, skapar modeller, kodar modellerna och sedan utvärderar dem. Att koda är egentligen alltså bara en del i detta; som vilket data-relaterat projekt som helst, vare sig det är t.ex. tunga e-handelssystem eller data mining-analys. (Och som vanligt går cirka 65 procent av tiden åt att fibbla med data fram och tillbaka mellan olika format/system eller verifiera att datan är korrekt.)


Det jag är mest intresserad av nu - och det är det jag bloggar mest om - är att hitta intressanta/skoj problem, bygga modellen och sedan koda den så effektivt som möjligt. Modellbyggande och kodning kan vara synnerligen integrerade i varandra, speciellt i högnivåspråk som Minizinc (tänk rapid application development).

För tillfället görs alltså kodningen främst i MiniZinc, för att lära mig dess principciella gränser det finns i systemet (t.ex. vad avsaknaden av rekursion och "imperativa loopar" innebär), och även vilka konkreta buggar som finns i betaversionen.

Posted by: hakank [TypeKey Profile Page] at april 22, 2008 06:12 EM

Lundgren, Rönnqvist och Värbrands "Linjär och ickelinjär programmering" höll jag i senast igår när jag ordnade om i min bokhylla. Jag hade Peter Värbrand i en kurs i optimeringslära. Jag tror det är samma bok som bytt namn sedan jag köpte mitt ex (som är från 2001). Jag tyckte laborationsuppgifterna i den kursen var riktigt roliga.

Posted by: David Hall at april 22, 2008 09:09 EM

David: Ja, det är vad jag förstår en utveckling av den bok du håller i handen.

Vilket modelleringsspråk/-system använde du för labbarna?

Posted by: hakank [TypeKey Profile Page] at april 23, 2008 10:10 EM

Vi körde AMPL.

Posted by: David Hall at april 24, 2008 01:10 FM

Man kan nog sammanfatta utredningens modell med att den nämnde ett flertal kriterier, exempelvis trivsel, smak och miljöpåverkan, men bara kvantifierade antal kök, antal anställda investeringskostnad och driftskostnad. En parameter som tydligen också ansågs viktig var "besvärsfrihet". Den var dock bara viktig för beslutsfattaren, inte alls för alla de som påverkas av beslutet.

Min förra kommentar, inklusive parentesen, och denna kanske kan uppfattas som att jag raljerar, och det är förstås sant i någon mån. Men jag är samtidigt uppriktigt nyfiken på hur man ställer upp en modell (med eller utan programmering) som faktiskt ger beslutsfattare en betydligt större chans att ta väl underbyggda beslut. Flera konsultbolag har modeller för att just kvantifiera nyttan inför ett beslut som medför kostnader (som PENG-modellen från Sweco) men jag tror att lite korsbefruktning från de typer av programmering (eller problemlösning) som du behärskar skulle berika dessa modeller ganska mycket.

Posted by: HÃ¥kan (hakke) [TypeKey Profile Page] at april 24, 2008 10:36 EM