New 1D Bin Packing Benchmark Problems Available

The literature describes many instances of benchmark 1D bin-packing problems, mainly due to Scholl[1] and Falkenauer[2]. Gathering these instances together results in a large set of 1370 problems, of which subsets have been used to illustrate the performance of a range of different optimisation algorithms and simple deterministic heuristics.

Some preliminary work we’ve been doing showed (not surprisingly) that generally, instances in a particular set are best solved by the same heuristic, while problems in a number of the sets are solved by many heuristics, suggesting they are not particularly difficult. This is illustrated in the graphic – ffd-djd each horizontal row represents one of the benchmark sets from Scholl or Falkenauer (which containing either 10 or 20 instances). Each cell (an instance) is coloured green or blue according to which of two heuristics (FFD or DJD respectively)  it is best solved by. If the cell is white then the instance is solved equally by both heuristics. Obvious patterns are apparent, suggesting strong commonalities between instances in a set. More on this soon in a paper we’re currently working on  mapping problem characteristics to heuristics.

This led us to thinking that the current benchmarks are too easy.. so we decided to generate some new ones. The new benchmarks are available here for downloading, with a detailed description of how they were generated.

Problem Set A contains 15,830 problem instances – these instances are all hard. What does hard mean ? In this case, it means that none of these instances can be solved optimally by Falkenauer’s Hybrid Grouping Genetic Algorithm, or four well-known deterministic heuristics (FFD, DJD, DJT, ADJD).. These instances were used in our recent GECCO 2013 paper Generating Single and Multiple Cooperative Heuristics for the One Dimensional Bin Packing Problem Using a Single Node Genetic Programming Island Model

Problem Set B contains a further 3968 problem instances. Three new problem instances were generated for the parameters sampled from each of the 1370 problem instances outlined above using the procedure outlined on the Benchmark page – all feasible instances were retained. These problems were used to test the AIS hyper-heuristic system described in our ECAL 2013 paper Learning to Solve Bin Packing Problems with an Immune Inspired Hyper-heuristic