My Constraint Programming Blog

Nicolas Beldiceanu and Helmut Simonis has written a very interesting paper about A Model Seeker, a system that finds the problem given a solution. Or more to the truth: suggests the appropriate global constraints given positive data instances (solution(s) to a certain problem). It was presented at the technical track of CP2012 (18th International Conference on Principles and Practice of Constraint Programming).

The system (A Model Seeker) is described in the paper: A Model Seeker: Extracting Global Constraint Models From Positive Examples (also: Presentation and Poster from the CP2012 conference).

From the Abstract:

We describe a system which generates finite domain constraint models from positive example solutions, for highly structured problems. The system is based on the global constraint catalog, providing the library of constraints that can be used in modeling, and the Constraint Seeker tool, which finds a ranked list of matching constraints given one or more sample call patterns.
We have tested the modeler with 230 examples, ranging from 4 to 6,500 variables, using between 1 and 7,000 samples. These examples come from a variety of domains, including puzzles, sports-scheduling, packing & placement, and design theory. When comparing against manually specified “canonical” models for the examples, we achieve a hit rate of 50%, processing the complete benchmark set in less than one hour on a laptop. Surprisingly, in many cases the system finds usable candidate lists even when working with a single, positive example.

A companion technical report presents the details of the 230 tested examples: A Model Seeker Description and Detailed Results (over 1400 pages).

This is a system I really would like to test...

Posted by hakank at 08:11 AM | Permalink

Just a short note about the next Constraint Programming Conference (CP2013). It will be in Uppsala, Sweden. From SweConsNet:

CP'13, the 19th International Conference on the Principles and Practice of Constraint Programming, will be held at Uppsala University on 16 - 20 September 2013.

More details will come.

I'm quite excited about this since it's in my home country which makes everything easier. At last I will have a chance to meet all the nice, smart and interesting people that I have read and read about (and in some case had mail conversation with).

See a list of the former CP conferences: International Conference on Principles and Practice of Constraint Programming. The last one finished some days ago: CP2012.

Posted by hakank at 07:55 PM | Permalink

The result from MiniZinc Challenge 2012 was presented this Friday (the last day of CP2012, 18th International Conference on Principles and Practice of Constraint Programming ).

The official contestants (solvers) this year was:

• BProlog (description)
• Choco (description)
• Fzn2smt (description). Translates to SMT, uses Yices.
• Gecode (description)
• izplus (description) (note: the site is in Japanese)
• JaCoP (description)
• Mistral 2.0 (description)
• OR-Tools (description)

Of these solvers, the only one I haven't tested (yet) is izplus.

Official results

The official results are:

• Fixed search:
  • Gold medal: Gecode
  • Silver medal: Jacop
  • Bronze medal: OR-Tools
• Free search:
  • Gold medal: Gecode
  • Silver medal: Fzn2smt
  • Bronze medal: izplus
• Parallel search:
  • Gold medal: Gecode
  • Silver medal: Fzn2smt
  • Bronze medal: izplus

Congratutations to all!

Result including all solvers

It can be interesting to see the results for all solvers in the Challenge, including the G12's internal solvers such as Chuffed and CPX (which "are not eligible for prizes, but do modify the scoring results"). For a short description of these non-eligible solvers, see the short description at the result page.

I took the results from the "Selection" section of the result page and for each categories selected "Select all problems", "Compute results" and then sorted on the points (most is best). The result is quite interesting since it shows that Chuffed and G12 CPX got most points in all the three categories, and G12 Lazy FD also got good places.

Note: The mixing in the categories is explained by the management: entries in the FD search category were automatically included in the free search category, while entries in the free search category (including promoted FD entries) were automatically included in the parallel search category. The official winners (gold, silver, bronze) has been embolded.

• Fixed search ("FD category solvers")
  

  chuffed-fd	1136
  g12_cpx-fd	1060
  gecode-fd	881
  g12_lazyfd-fd	783
  jacop-fd	548
  g12_fd-fd	525
  or_tools-fd	488
  choco-fd	430
  bprolog-fd	265

  
  
• Free category ("Free category solvers")
  

  chuffed-free	2359
  g12_cpx-free	1915
  g12_lazyfd-free	1782
  gecode-free	1620
  fzn2smt-free	1522
  gurobi-free	1481
  izplus-free	1413
  cplex-free	1367
  jacop-free	1326
  bprolog-free	1203
  mistral-free	1199
  g12_fd-free	998
  choco-free	805
  or_tools-free	692
  minisatid-free	648
  cbc-free	222

  
  
• Par category ("Par category solvers")
  

  chuffed-free	2341
  g12_cpx-free	1897
  gecode-par	1846
  g12_lazyfd-free	1758
  fzn2smt-free	1504
  gurobi-par	1499
  izplus-free	1380
  cplex-par	1351
  jacop-free	1293
  bprolog-free	1178
  mistral-free	1173
  g12_fd-free	974
  or_tools-par	810
  choco-free	789
  minisatid-free	627
  cbc-free	222

  
  

Note that all the problem instances are available for download from the Result page (mznc12-problems.tar.gz).

Also see: MiniZinc Challenge Medals 2008-2012

Posted by hakank at 08:40 PM | Permalink