My Constraint Programming Blog

Ian Gent, a member of the winning team (Mano) in the First International Lightning Model and Solve Competition this conference, has just published a blog post about how and why he and his team won: How I became one of the three "best optimizers in the world".

Ian writes very interesting details about how the team approached the problems, why they decided to solve all problems by hand, etc. I like Ian's conclusions:

What Have We Learnt For Constraint Programming?

One word. Modelling.

To expand, Modelling is hard.

To expand, we need better tools to make it easier to model constraint problems quickly. Every group should have been able to use a simple constraints tool to model the easier problems (like queens) and then get on with the other ones.

This is what I take away, and it's nice that this is research that we in St Andrews are already doing, so I hope we can push this harder after this experience.

As one of the organizers of the competition, I also thank Ian for this comments about what we can do better the next time. [This means that I have read it, but will not promise anything. :-)]

Also, see my summary of the competition: CP-2013: The Conference Day 3 (Thursday) and CP-2013: Competition problems, rules, and instances.

Posted by hakank at 09:11 PM | Permalink

Here are the CP-2013 competition problems (with some small corrections by Peter Stuckey): cp2013_competition_20130919.pdf. The rules might also be interesting to read to see the conditions of the competition: cp2013_competition_rules_20130919.pdf. The problem instances are here: cp2013_competition_instances_20130919.zip and are named as "problem_instance.dzn", where instance 0 is the instance that's shown in the problem documentation.

If you have a nice model (in CP or some other paradigm) that solves the competition instances on any of the problems, feel free to mail me at hakank@gmail.com. If I got more than a few models/programs, I might put them on a web page.

Have fun!

Update 2013-09-24: The problem document, the rules, and the instances has now been added to the competition page. Thanks, Guido.

Posted by hakank at 11:20 PM | Permalink

I am happy and proud to announce the First International Lightning Model and Solve Competition which will be held at CP 2013 (The 19th International Conference on Principles and Practice of Constraint Programming, September 16-20, 2013, Uppsala, Sweden).

Here is the description of the Competition:

First International Lightning Model and Solve Competition

Organizers: Peter J. Stuckey and Håkan Kjellerstrand [that's me]

In order to crown the world champion optimizers we are organizing the first "Lightning Model and Solve" competition for teams of up to 3 people.

The competition presents 6 satisfaction and optimization problems, with 3-5 instances each, and each team tries to find good solutions to these problems within 2 hours. The team can use any optimization technology they desire for any problem, including solving problems by hand. Problem data is presented as text files containing numbers. Solutions are submitted as text files.

Solutions are ranked first by quality (for optimization problems) and then by time of submission. Each team scores one point for each instance and each other team for which their solution is better. Any correct solution is better than no submission at all.

The competition entry is for teams of up to 3 people. Each team can make use of ONLY ONE laptop, and cannot make use of any computing resources other than the laptop itself (no connecting to your CLUSTER at home). We recommend a team of 3, smaller teams will be merged unless the number of entrants is small.

The main aim of the competition is to have fun, and earn the eternal glory of the title of "best optimizers in the world".

To take part in the competition, you need to be a registered participant of the CP 2013 conference and of course physically present.

More information will be added closer to the conference.

Posted by hakank at 07:13 AM | Permalink

Here are some news from the G12 MiniZinc world.

MiniZinc main page: www.minizinc.org

The MiniZinc main page has changed to www.minizinc.org.

MiniZinc challenge

From MiniZinc Challenge 2013:

The aim of the MiniZinc Challenge is to start to compare various constraint solving technology on the same problems sets. The focus is on finite domain propagation solvers. An auxiliary aim is to build up a library of interesting problem models, which can be used to compare solvers and solving technologies.

Entrants to the challenge provide a FlatZinc solver and global constraint definitions specialized for their solver. Each solver is run on 100 MiniZinc model instances. We run the translator mzn2fzn on the MiniZinc model and instance using the provided global constraint definitions to create a FlatZinc file. The FlatZinc file is input to the provided solver. Points are awarded for solving problems, speed of solution, and goodness of solutions (for optimization problems).

Registration opens: Wed, 1 May 2013.
Problem submission deadline: Fri, 14 June 2013.
Initial submission round begins: Mon, 1 July 2013.
Initial submission round ends: Fri, 19 July 2013.
Final submissions: Fri, 2 August 2013.
Announcement of results at CP2013: 17 - 20 September 2013.


For details of the competition see:

http://www.minizinc.org/challenge2013/challenge.html

Note that the scoring system has slightly changed this year, so that solvers that obtain indistiguishable results in quality of solution split the points inversely proportional to the time taken

To register for the challenge please email

mzn-challenge@minizinc.org

Here is the Call for Problem Submission:

The MiniZinc Challenge is an annual solver competition in the Constraint Programming (CP) community held before the International Conference on Principles and Practice of Constraint Programming. The MiniZinc Challenge 2013 is seeking interesting problem sets on which various constraint solving technologies should be compared on this year. Everyone is allowed to submit problems regardless of whether they are an entrant in the challenge.

Important dates and deadlines:

Problem submission open: now
Problem submission deadline: Fri, 14 June 2013

Problem submission

Send an email with the subject line “[MZNC13] benchmark” to mzn-challenge 'at' minizinc.org

There are no restrictions on the kind of problems, but ideally they should be of interesting nature such as practice-related problems and puzzles etc. Problem submissions with real-world instances are welcome warmly. Models for the 2013 challenge can only use integer and Boolean variables.

The problem submitter provides a MiniZinc model of the problem and 20 instances ranging from easy-to-solve to hard-to-solve for an “ordinary” CP system. It is strongly encouraged to make use of the global constraint definitions provided in the MiniZinc 1.6 distribution. Please, follow the links below for submission instructions and requirements.
MiniZinc Challenge 2013

Also see: MiniZinc Challenge Medals 2008-2012

MiniZinc forum

Also just released is The MiniZinc forums with three forums:

• Beginners: All beginner-level questions about MiniZinc.
• Users: General discussion about MiniZinc. For beginners' questions please use the dedicated Beginners' Forum.
• Developers: Discussions about developing the MiniZinc system and solvers that interface with MiniZinc.

Posted by hakank at 06:40 AM | 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

The MiniZinc Challenge 2012 is now underway:

The Challenge

The aim of the challenge is to start to compare various constraint solving technology on the same problems sets. The focus is on finite domain propagation solvers. An auxiliary aim is to build up a library of interesting problem models, which can be used to compare solvers and solving technologies.

Entrants to the challenge provide a FlatZinc solver and global constraint definitions specialized for their solver. Each solver is run on 100 MiniZinc model instances. We run the translator mzn2fzn on the MiniZinc model and instance using the provided global constraint definitions to create a FlatZinc file. The FlatZinc file is input to the provided solver. Points are awarded for solving problems, speed of solution, and goodness of solutions (for optimization problems).

...

Dates

• Registration opens: 1 May 2012.
• Problem submission deadline: 12 July 2012.
• Initial submission round begins: 1 August 2012.
• Initial submission round ends: 20 August 2012.
• Final submissions: 1 September 2012.
• Announcement of results at CP2012: 8-12 October 2012.

For more about the result of the last year MiniZinc Challenge: MiniZinc Challenge 2011 Results.

Posted by hakank at 08:27 PM | Permalink

The results of the MiniZinc Challenge 2011 has been published.

From the result page:

The entrants for this year (with their descriptions, when provided):

BProlog. A CLP(FD) solver.
Bumblebee. Translates to SAT, uses CryptoMiniSAT.
Gecode. A C++ FD solver.
JaCoP. A Java FD solver.
Fzn2smt . Translates to SMT, uses Yices.
SCIP. A CP/MIP solver.

In addition, the challenge organisers entered the following FlatZinc implementations:

Chuffed. A C++ FD solver using Lazy clause generation.
CPX. A C++ FD Solver using Lazy Clause Generation.
G12/FD. A Mercury FD solver (the G12 FlatZinc interpreter's default solver).
G12/LazyFD. A Mercury FD solver using Lazy Clause Generation.
G12/CBC. Translates to MIP, uses Cbc version 2.6.2.
G12/CPLEX. Translates to MIP, uses CPLEX version 12.1
. G12/Gurobi. Translates to MIP, uses Gurobi Optimizer version 4.5.

As per the challenge rules, these entries are not eligible for prizes, but do modify the scoring results. Furthermore, entries in the FD search category (BProlog, Gecode, JaCoP, Chuffed, CPX and G12/FD) were automatically included in the free search category, while entries in the free search category (Bumblebee, Fzn2smt, SCIP, CBC, CPLEX, Gurobi and promoted FD entries) were automatically included in the parallel search category.

The slides for the presentation of the results at CP2011 are here (PDF).

Summary of results

The results for the MiniZinc Challenge 2011 were

Fixed search:
* Gold medal: Gecode
* Silver medal: JaCoP
* Bronze medal: BProlog

Free search:
* Gold medal: Gecode
* Silver medal: fzn2smt
* Bronze medal: JaCoP

Parallel search:
* Gold medal: Gecode
* Silver medal: fzn2smt
* Bronze medal: JaCoP

Congratulations to all!

As in the MiniZinc Challenge 2010, the Chuffed solver did very well on the benchmarks (though not eligible for a price). More details in presentation and the result page (where the models and data instances are shown).

Posted by hakank at 05:55 PM | Permalink

Today the MiniZinc Challenge 2011 (the fourth) was announced:

The aim of the challenge is to start to compare various constraint solving technology on the same problems sets. The focus is on finite domain propagation solvers. An auxiliary aim is to build up a library of interesting problem models, which can be used to compare solvers and solving technologies.

Entrants to the challenge provide a FlatZinc solver and global constraint definitions specialized for their solver. Each solver is run on 100 MiniZinc model instances. We run the translator mzn2fzn on the MiniZinc model and instance using the provided global constraint definitions to create a FlatZinc file. The FlatZinc file is input to the provided solver. Points are awarded for solving problems, speed of solution, and goodness of solutions (for optimization problems).

See the MiniZinc Challenge 2011 -- Rules for more details. Note, for example, that the scoring procedure has been changed from previous competitions.

If you haven't, now can be a good time to read the paper Philosophy of the MiniZinc Challenge by Peter J. Stuckey, Ralph Becket, Julien Fischer (from 2010) that discuss the MiniZinc Challenge is more detail.

Posted by hakank at 07:35 AM | Permalink

The results of MiniZinc Challenge 2010 has been published: MiniZinc Challenge 2010 Results:

The entrants for this year (with their descriptions, when provided):

• Gecode (description). A C++ FD solver.
• JaCoP (description). A Java FD solver.
• Fzn2smt (description). Translates to SMT, uses Yices.
• SCIP. A CP/MIP solver.

In addition the challenge organisers entered the following FlatZinc implementations:

• Chuffed (description). A C++ FD solver using Lazy clause generation.
• Fzntini. Translates to SAT, uses TiniSAT.
• G12/FD. A Mercury FD solver (the G12 FlatZinc interpreter's default solver).
• G12/CPLEX. Translates to MIP, uses CPLEX12.1.

As per the challenge rules, these entries are not eligible for prizes, but do modify the scoring results. Furthermore, entries in the FD search category (Gecode, JaCoP, Chuffed, G12/FD) were automatically included in the free search category, while entries in the free search category (Fzn2smt, Fzntini, SCIP, CPLEX and promoted FD entries) were automatically included in the parallel search category.

I'm really curious about Chuffed (which I have not tested). As far as I know, it is not public available.

Results

This year the results are not in fixed result lists. Instead there is a Javascript application where one can choose different combinations of solvers and problems.

Update some hours later: I have been informed that my summaries was not correct so I have removed them to not confuse anyone. Sorry for any confusions. Please see the Results page.

See also

The results of the earlier MiniZinc Challenges:
* MiniZinc Challenge 2009 Results. Results of the MiniZinc challenge 2009.
* MiniZinc Challenge 2008 Results. Results of the MiniZinc challenge 2008

Posted by hakank at 09:25 AM | Permalink