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.
June 17, 2005: Detailed rules for entry are below. Please note that failure to follow these rules may result in disqualification.
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.
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 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.)
Please address all correspondence and entries to challenge05@dcs.st-and.ac.uk.
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.
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.