Sample Instances

• Challenge Home Page

Instances

The set of instances for solution by participants in the challenge is now closed (see below.) However, we still encourage anyone to submit new instances to us by email for use by future researchers. These should all be in the standard format described below.

News!

Unfortunately we failed to upload all of Warwick Harvey's instances in the original distribution. The files available now have all the instances. Participants are encouraged but not required to use the new files. To strengthen this encouragement, the original files are no longer available. If you are concerned about which is the correct download, the new tar/tgz/zip files have a README file indicating they are version 1.1.

File Format

Files may have any number of instances contained within them, separated by a line of whitespace.

Each instance within a file is in the following format:

• First line: free text instance name
• 2nd line: number of customers (n) number of products (m)
• Each of next n lines: m Boolean values, one for each product
• In the matrix of Boolean values a 1 in the row corresponding to customer i and product j means that customer i has ordered product j.

  Anyone proposing new instances should use this file format. They should also ensure that instances mailed to us are free from rows of columns full of 0's.

Fixed Set of Instances for Challenge

June 9, 2005.

We thank the participants who submitted instances to the challenge. We have selected all of them for inclusion, as they have been generated in a number of different ways so should test solvers in interesting ways. (Please note, if your instances do not appear here, please contact us since we may have had email problems.)

• Helmut Simonis provided the following instances, randomly generated but without rows or columns or zeroes.
• Warwick Harvey provided the following instances. He writes that these are "some randomly generated balanced instances (each order has the same number of products, each product has the same number of orders, or both). The instances balanced in one dimension only are selected uniformly at random from the feasible set. The ones balanced in both dimensions are *not* selected uniformly at random; I believe there is no known (practical) algorithm for selecting these uniformly. (For n orders and n products with each row/column containing k entries, this is equivalent to generating a random k-regular labelled n+n bipartite graph - this has been studied but not solved as far as I could determine."
• Nic Wilson, Gilles Pesant, Steve Prestwich and Radoslaw Szymanak provided a small selection of instances. They write that they are "of varying (though generally large) sizes (and varying relative magnitudes of pathwidths) ... They've been produced by three different generation methods."
• Paul Shaw provided some 20/20 instances without describing how they are generated, but hopes they are hard!
• Alice Miller and Patrick Prosser provided a single instance they think is hard.
• The instances are provided in tarred and gzipped format, in uncompressed tar format, and in zip file format.

Please note that we have NOT checked all instances to ensure that they are free of rows or columns full of zeroes. We would expect your solver to deal correctly with these, but if you do find some please let us know.

There are large numbers of instances above (especially in the Simonis and Harvey sets.) All form part of the challenge. However, the numbers should not be insuperable and of course if necessary you may use a timeout, provided this is properly reported.

Also please note that the original instances below do not form part of the final stage of the challenge.

We will shortly release details of the required final format of the appendix describing results. However, if you are starting to run experiments immediately, please be aware of some key points. We will expect a number of statistics of your results, including minimum, maximum, mean, median. Percentages of cases where timeouts impact results must be reported. We will expect statistics categorised by file and in some cases by parts of file (again in the Simonis and Harvey sets.) So please be able to reproduce these. Where optimality is proved we expect time to find optimality and also time to prove that the result is optimal (unless this is inherently impossible in the method.) We expect you to provide both run time statistics and an appropriate search measure (e.g. backtracks, local search steps).

Initial Set of Instances

• Created by Barbara Smith, May 13 2005
  • problems_10_10_35
  • problems_10_20_35
  • problems_15_30_35
  • Please note that some of the above instances have columns of 0's, i.e. products that nobody wants. We intend that the final set of instances used for assessment should be free of this feature.