Constraint Modelling Challenge 2005

Winners and Runners-Up

Maria Garcia de la Banda and Peter Stuckey were announced as prizewinners for best paper of the 2005 Constraint Modelling Challenge on 31 July 2005.

Because of the extremely high quality of entries, we also announced three runners-up: Steven Prestwich, Paul Shaw and Philippe Laborie, and Nic Wilson and Karen Petrie.

The standard of entries was remarkably high, and many other entrants deserve plaudits.

The draft proceedings are now available including all entries and the report by the organisers. It is more than 4MB, sorry. (It is a draft because the organisers' report should be updated to reflect the prizes and in other small ways.) The slides of the talk at the IJCAI 05 Workshop are also available.

(Old) News

June 17, 2005: Detailed rules for entry are below. Please note that failure to follow these rules may result in disqualification.

  1. Each team is limited to one entry, and each entry must be limited to a single model. It is your job, not ours, to decide which is your best model. Exceptionally, we may allow you to submit more than one entry, but only with our prior permission in cases such as two extremely different paradigms being used or a single co-author in otherwise disparate teams.
  2. Each entry consists of a four page paper with appendices as described below not counting in the page limit, together with the code used to generate the results. It is compulsory to submit both a paper and code.
  3. The prize for best paper will be awarded solely at our discretion, and will be judged on the quality of the model together with the scientific quality of the submitted paper. For example, the submitted paper may describe alternative models and good and bad points of them and reasons for selecting your preferred model. The paper must be self contained, but if necessary may refer to other documents, e.g. a tech report describing details too long for the paper.
  4. The first appendix is compulsory, and contains your experimental results on your preferred model (and solely your preferred model). This MUST be in the format described in the file ResultsAppendix.doc or file ResultsAppendix.pdf. You may make reasonable efforts to keep these tables on the page (e.g. reducing font sizes, present pages in landscape), as long as results are clearly legible and follow the rules laid out in the document. Unfortunately we do not have a tex file describing the layout - if you create one and are public spirited to help others, please send it to us!

June 10, 2005: Unfortunately we failed to upload all of Warwick Harvey's instances. The full set is now uploaded. You are strongly encouraged to use the new set but will not be penalised if you don't. Only the full sets are now available. To help some users, a zip file has been added.

June 9, 2005: The set of instances for the final stage of the challenge has now been fixed (two days late, apologies.) Go the the instances page for details.



We are pleased to announce the First Constraint Modelling Challenge.

In fields such as SAT, Planning, and Theorem Proving, regular competitions proved extremely fruitful in pushing the field further. To date, no similar attempt has been made in Constraints. We challenge the community to provide constraint models for the problem described below, and to submit short papers describing their models. The best paper will win a small prize to a value of about £100.

We have chosen a problem which can be seen as a manufacturing scheduling problem, but is also equivalent to pathwidth. Despite the importance of this problem to the theory of constraints, and an extensive algorithmic literature, there is little understanding of how to model and solve the problem using constraints.

The First Constraint Modelling Challenge is to model this problem as a constraint problem in the constraint programming or constraint logic programming language of your choice. There are no restrictions on the languages you may use. We describe the problem and then the challenge in detail.

The Problem

Minimizing the maximum number of open stacks (from Fink and Voss, reference below)

A manufacturer has a number of orders from customers to satisfy; each order is for a number of different products, and only one product can be made at a time. Once a customer's order is started (i.e. the first product in the order has been made) a stack is created for that customer. When all the products that a customer requires have been made, the order is sent to the customer, so that the stack is closed. Because of limited space in the production area, the number of stacks that are in use simultaneously i.e. the number of customer orders that are in simultaneous production, should be minimized.

More formally: we are given a Boolean matrix in which the columns correspond to the products required by the customers and each row corresponds to the order of a particular customer. The entry c_ij = 1 iff customer i has ordered some quantity of product j (the quantity ordered is irrelevant). The objective is to find a permutation of the products such that the maximum number of open orders at any point in the sequence is minimized: order i is open at point k in the production sequence if there is a product required in order i that appears at or before position k in the sequence and also a product that appears at or after position k in the sequence.

The Challenge

The challenge opens immediately, and will run in three stages.

The first stage will be the development of the benchmark suite for testing. An initial set of instances is already available. We will add instances during the initial phase. Participants in the challenge have the option to submit their own instances together with their best known results and an indication of whether optimality is known. The organisers will select instances to be uploaded, to broaden the scope of the benchmark set. This should help us find interesting and hard instances to challenge the community. The solutions to the initial instances are not known: participants who solve these optimally or find good solutions should notify the organisers who will add this information to the Web site.

At the second stage, the set of benchmarks for the challenge will be fixed. Entrants will be required to present results for all instances at this stage, together with whether or not optimality has been proved (or to declare that they are unable to solve certain instances.)

The final stage will be the presentation of results at the Workshop at IJCAI 05. Given the limited time available, the organisers will present a report on the competition at the workshop. (While this means that entrants won't have the chance to present their work in person, it will allow us to draw together ideas that may have occurred in multiple entries).

The variety of tools available to entrants means that we will NOT be awarding a prize for the fastest run times reported. Instead, the organizers will award a prize for the best paper, based on their judgment of the quality of analysis and writing in the paper as well as the modelling ideas used. There will be a prize for best paper, to a value of approximately £100 , supported by SymNet, the UK's Symmetry and Search Network.

We plan to submit the benchmark instances to CSPLib, with a pointer to a web page where the submitted papers will be available. (Authors will be asked whether they agree to this publication of their work immediately after the workshop.)

How To Take Part

Please address all correspondence and entries to

Entry to the Challenge is by submission of a short paper (maximum 4 pages) in IJCAI Format by the submission deadline listed below. Additionally to the 4 pages, an appendix should present results on the benchmark set in a format to be decided at the close of the first stage. Papers may of course mention unsuccessful modelling ideas as well as those the author found to work best. Papers will be put on the Challenge Website and distributed at the workshop. Code used to generate results should be submitted to the organisers, but entrants can decide whether or not they wish to make their code public on the website.

Important Dates

Pointers to Literature

The problem is described in:

Fink and Voss cite several papers on this problem, using a variety of Operations Research techniques. The following paper lists several equivalent problems, including graph path-width:

One starting point to the algorithms literature on pathwidth is:


We especially thank Patrick Prosser for proposing the Modelling Challenge as a part of the 2005 Workshop. For help in various ways we would like to thank Zeynep Kiziltan, Ian Miguel, Sylvain Soliman, and members of the CP Pod research group.

We are certainly missing people we should be thanking and apologise in advance for that.