First Constraint Modelling Challenge http://www.dcs.st-and.ac.uk/~ipg/challenge In conjunction with The Fifth Workshop on Modelling and Solving Problems with Constraints, 31 July, 2005 IJCAI 05, Edinburgh Organisers: Barbara Smith, Cork Constraint Computation Centre, Ireland Ian Gent, University of St Andrews, Scotland Prize generously supported by UK Symmetry and Search Network 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 & 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.) 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. Important Dates --------------- 7 June 2005: Benchmark Suite for Challenge Fixed 29 June 2005: Deadline for Entries to the Challenge 31 July 2005: Report on Challenge at IJCAI 05 Workshop on Modelling and Solving Problems with Constraints Pointers to Literature ---------------------- The problem is described in: Andreas Fink and Stefan Voss, Applications of modern heuristic search methods to pattern sequencing problems. Computers & Operations Research (26), pp. 17-34, 1999. Fink & 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: Alexandre Linhares and Haracio Hideki Yanasse, Connections between cutting-pattern sequencing, VLSI design and flexible machines. Computers & Operations Research (29) pp. 1759-1772, 2002. One starting point to the algorithms literature on pathwidth is: Hans L. Bodlaender. Treewidth: Algorithmic Techniques and Results. Proceedings 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS'97, Lecture Notes in Computer Science, volume 1295, Igor Privara and Peter Ruzicka (editors), Springer-Verlag, Berlin, 1997, p. 29-36. http://www.cs.uu.nl/~hansb/mypapers.html