hakank.blogg

« Complete Rewrite: Intressant blogg om databaser och systemutveckling | Main | My Constraint Programming Blog »

december 27, 2008

Constraint programming-nyheter samt nya MiniZinc-modeller

Här är några nyheter kring constraint programming sedan cirka oktober 2008 och inkluderar naturligtvis även en del MiniZinc-modeller.

My Constraint Programming page

För att samla ihop mina constraint programming-modeller/-referenser har skapats Constraint Programming som i stort sett endast är länkar till respektive "My XXXXXX page" (där "XXXXX" in {MiniZinc, Choco, JaCoP}).

MiniZinc

• version 0.9 har kommit ut. Finns att ladda ner här, NEWS
  
• Roligt nog finns två av mina modeller med i benchmark-katalogen. Det är:
  • debruijn_binary.mzn
    
  • quasiGroup7.mzn

För vidare info, se My MiniZinc page.

JaCoP

• Har flyttat. Nya sajten är www.jacop.eu. Ny Wikisida.
• Sedan version 2.3 är JaCoP open source och glädjande nedladdningsbar.
• Några av mina JaCoP-modeller finns med i distributionen. Notera att de är något redigerade för att passa in i exempelstrukturen:
  • DeBruijn.java
  • Diet.java
  • FurnitureMoving.java
  • LeastDiff.java
  • MineSweeper.java
  • SurvoPuzzle.java

För vidare info, se My JaCoP page.

Choco

• finns nu i version 2.0.0.3
  

För vidare info, se My Choco page.

Minion/Tailor

Tailor är ett trevligt modelleringsspråk som översätter en Essence'-modell (en nedstrippad variant av modelleringsspråket Essence) till Minion. Tailor är implementerat i Java.

Jag har skrivit några Tailor-modeller men de är ännu inte publikt publicerade, bland annat eftersom specifikationen av Tailor/Essence' inte har varit stabil. Återkommer om detta. Kan också notera att några av mina MiniZinc-modeller är portade från just Tailor/Essence'.

Global Constraint Catalog

Global constraint catalogue uppdaterades 2008-11-15. Det var några nya constraints, framförallt geost och andra packnings-constraints.

Det gjordes då också en strukturell förändring av sajten med ett nytt URL-schema. I stället för URL-ar såsom http://www.emn.fr/x-info/sdemasse/gccat/sec4.5.html (för alldifferent_cst), så är URL-en numera http://www.emn.fr/x-info/sdemasse/gccat/Calldifferent_cst.html, dvs .../C följt av constraint-namnet. Jag har dock inte ändrat referenserna i mina MiniZinc-modeller på My MiniZinc page; däremot har nya modeller den nya URL-en.

Gecode

Gecode har inte kommit ut med någon ny officiell release sedan augusti 2008. Däremot har Gecode/flatzinc uppdaterats (SVN-versionen) några gånger för att stödja nya versioner av MiniZinc. Som tidigare sagt är Gecode/flatzinc min favorit-MiniZinc-solver.

Gecode/R

Gecode/R är ett Ruby-gränssnitt till Gecode:

Gecode/R provides access to many, but not all, of the features in Gecode 2.2.0. Gecode/R is only a modelling interface, it does not provide support for e.g. creating new propagators.

Version 1.0 kom i september. Har inte kollat in Gecode/R så mycket, vilket emellanåt förvånar mig...

Comet

Comet är ett constraint programming-system som bygger på "local search". Det har kommersialierats och en tidsbegränsad version av 1.02 finns nu att ladda ner på Dynadec.

Denna version är mer kompetent och komplett än förra, men det är nu ännu fler skillnader mot det som beskrivs i boken Constrant-based local search av Pascal Van Hentenryck, Laurent Michel.

Nya MiniZinc modeller

Sedan sist har det skrivit ett flertal nya MiniZinc-modeller (och några har uppdaterats men det - med ett undantag - noteras inte här nedan). Som vanligt finns de alla samlade på My MiniZinc page.

Referenser och oftast en kort förklaring finns att läsa i respektive modell.

Pyssel och andra matematiska förströelse

• atom_smasher.mzn: sqrt(ATOM) = A + TO + M
  
• bus.mzn: bus problem (rec.puzzle FAQ)
  
• coins_41_58.mzn: Yet another coin problem
  
• collatz.mzn: Collatz-problemet
  
• consecutive_digits.mzn: (Martin Gardner)
  
• crossfigure.mzn: Crossfigure problem, CSPLib problem 21
  
• crypto.mzn: standard constraint programming problem
  
• cube_sum.mzn: Cube sum problem
  
• digital_roots.mzn: (tvärsumma)
  
• dimes.mzn: rec.puzzle FAQ
  
• ein_ein_ein_ein_vier.mzn: EIN+EIN+EIN+EIN = VIER
  
• eliza_pseudonym7.mzn: Från A Cleverly-Titled Logic Puzzle Blog
  
• hardy_1729.mzn: Hardy-Ramanjuan number 1729 (taxi cab number)
  
• hidato.mzn: Se http://hidato.com
  
• high_iq_problem.mzn: (Simon Colton)
  
• just_forgotten.mzn: Just forgotten puzzle (Enigma 1517)
  
• knight_path.mzn: Knight path
  
• logic_puzzle.mzn"> Logisk pyssel från The Art of Prolog
  
• map.mzn: Färgläggningsproblem
  
• minesweeper_model.mzn: Har separerat model och data (jämfört med minesweeper.mzn). Följande är data-filer:
  • minesweeper_0.mzn
    
  • minesweeper_1.mzn
    
  • minesweeper_2.mzn
    
  • minesweeper_3.mzn
    
  • minesweeper_4.mzn
    
  • minesweeper_5mzn
    
  • minesweeper_6mzn
    
  • minesweeper_7.mzn
    
  • minesweeper_8.mzn
    
  • minesweeper_9.mzn
    
  • minesweeper_basic3.mzn
    
  • minesweeper_basic4.mzn
    
  • minesweeper_basic4x4.mzn
    
  • minesweeper_config_page2.mzn
    
  • minesweeper_config_page3.mzn
    
  • minesweeper_german_Lakshtanov.mzn
    
  • minesweeper_splitter.mzn
    
  • minesweeper_wire.mzn
    
  
  
• missing_digit.mzn: Missing digit
  
• monkey_coconuts.mzn: Classic puzzle
  
• monks_and_doors.mzn: Lögnarproblem
  
• number_puzzle.mzn: Alfametisk gåta
  
• relative_sizes.mzn: Enigma 1515
  
• rook_path.mzn:
  
• rookwise_chain.mzn: Martin Gardner
  
• send_more_money_any_base.mzn: SEND + MORE = MONEY i vilken bas som helst
  
• square_root_of_wonderful.mzn: Martin Gardner
  
• subsets_100.mzn: Från rec.puzzle FAQ
  
• tickTackToe.mzn: Tic-tac-toe (från Minion/Tailor)
  
• vingt_cinq_cinq_trente.mzn: VINGT + CINQ + CINQ = TRENTE
  
• war_or_peace.mzn: War or Peace problem
  
• wwr.mzn: WRONG + WRONG = RIGHT
  
• zebra_inverse.mzn: Zebra-problemet med global constraint inverse i stället för all_different
  

GLPK

GLPK (GNU:s Linear Programming Kit) är en open source-projekt för linjär/heltals-programmering. GLPK har bl.a. ett AMPL-liknande språk kallat MathProg varpå följande MathProg-exempel har konverterats till MiniZinc. Några av de allra största exemplen har - ännu - inte konverterats.

• assignment6.mzn: Assignment problem
  
• bpp.mzn: Bin packing problem
  
• coloring_ip.mzn: Graph coloring, integer programming version
  
• crypto_ip.mzn: Crypto problem, integer programming
  
• curve_fitting1.mzn: Curve fitting
  
• curve_fitting2.mzn: Curve fitting
  
• curve_fitting3.mzn: Curve fitting
  
• diet2.mzn: diet problem
  
• fixed_charged_transportation_problem.mzn: Transportation problem
  
• food.mzn: Food manufacture problem
  
• food2.mzn: Food manufacture problem
  
• gap.mzn: Generalized Assignment Problem
  
• jssp.mzn: Job-Shop Scheduling Problem
  
• magic.mzn: Magic square integer programming
  
• max_cut.mzn: Maximum Cut Problem
  
• maxflow.mzn: Maximum Flow Problem, integer programming
  
• mfasp.mzn: Minimum Feedback Arc Set Problem
  
• mfvsp.mzn: Minimum Feedback Vertex Set Problem
  
• misp.mzn: Maximum Independent Set Problem
  
• mvcp.mzn: Minimum Vertex Cover Problem
  
• plan.mzn: Planning model
  
• queens_ip.mzn: Queens problem, integer programming
  
• sat.mzn: Satisfiability Problem
  
• send_more_money_ip.mzn: Send More Money, integer programming
  
• spp.mzn: Shortest Path Problem
  
• stigler.mzn: Original Stigler's 1939 diet problem
  
• sudoku_ip.mzn: Sudoku, integer programming
  
• transp.mzn: Transportation problem
  
• tsp.mzn: Traveling Salesman Problem, integer programming
  
• zebra_ip.mzn: Zebra puzzle, integer programming
  

Global constraints

En handfull global constraints från Global constraint catalogue har skapats:

• all_equal.mzn: all_equal
  
• bipartite.mzn: bipartite
  
• lex_alldifferent.mzn: lex_alldifferent
  
• soft_all_equal_ctr.mzn: soft_all_equal_ctr
  
• symmetric.mzn: symmetric
  

Operations research, linear programming, integer programming

Kommentaren "Williams" refererar till den mycket trevliga boken om modellering inom operations research och matematisk programmering: Model Building in Mathematical Programming (4th edition), skriven av H. Paul Williams.

• OandX.mzn: Three Dimensional Nought and Crosses, Tic-Tac-Toe (Williams)
• agprice.mzn: Agricultural pricing (Williams)
• assignment5.mzn: Assignment problem
• bratko_scheduling.mzn: Scheduling (Bratko)
• bratko_scheduling2.mzn: Scheduling (Bratko)
• constraint.mzn: Optimizing a Constraint (Williams)
• decent.mzn: Decentralization problem (Williams)
• ice_cream.mzn: Ice cream production
• logical_design.mzn: Logical design problem (Williams)
• max_flow_winston1.mzn: Maximum Flow (Winston)

Combinatorial

• full_adder.mzn: Full Adder (logical circuit)
• lams_problem.mzn: Lam's problem, CSPLib 25
• ramsey_partition.mzn: Ramsey Partition
• satisfy.mzn: Satisfication problem
• traffic_lights.mzn: Traffic lights, CSPLib problem 16

Övrigt

• celsius_fahrenheit.mzn: Konverterar Celsius <-> Fahrenheit, ett standardexempel på "bidirect programmering"
  
• matrix2num.mzn: Konverterar en binär matris till en vektor av tal
  
• penguin.mzn: Nonmonotonic reasoning
  
• sum_sets.mzn: Sums the integers in a set
  

Slutord

Det har sedan länge insetts att målgruppen för ovanstående saker i svensk språkdräkt inte är så väldigt stor, varför det har tänkts att starta en separat blogg på engelska som endast handlar om constraint programming och relaterade paradigm såsom nyheter samt nyskrivna modeller. Mer om detta senare.

Posted by hakank at december 27, 2008 10:51 EM Posted to Constraint Programming

Comments

Posted by: thebe at december 28, 2008 12:10 EM

Posted by: hakank at december 28, 2008 07:43 EM

Posted by: Håkan (hakke) at januari 2, 2009 01:39 EM

Posted by: hakank at januari 2, 2009 06:19 EM