Development of a Problem Generator for Bin Packing Problems: An Analysis of Benchmark Problems and Current Stochastic Deterministic Problem Solving Techniques

Sim, K. (2010). Development of a Problem Generator for Bin Packing Problems: An Analysis of Benchmark Problems and Current Stochastic Deterministic Problem Solving Techniques (MSc Advanced Software Engineering Dissertation). Edinburgh Napier University.


ISBN:
ISSN:

Abstract

The one dimensional bin packing problem (BPP) was investigated with attention
paid to the benchmark problems used in the literature along with the performance
of a number of deterministic heuristic techniques and stochastic meta-heuristic
approaches used to solve the NP-Hard problems.
A large set of benchmark problems used extensively throughout the literature was
investigated. For all 1370 problems a range of techniques were applied to each
problem instance and the results obtained by different methods cross examined.
The characteristics used to define benchmark problems were standardised by
identifying a range of parameters that differentiated problem instances in order to
homogenise different methods used in the literature to construct problems.
Using the results of an analysis of benchmark problems the possibility of defining
a mapping between a problems characteristics and the suitability of different
techniques to solve the problem was explored.
A problem generator was developed that allowed for problems to be created that
covered a wider area of the search space than previous benchmark problems.
The generator developed was tested by creating problems of differing
characteristics in order to investigate the mappings proposed between a
problems characteristics and the effectiveness of differing (meta) heuristic
techniques.
[Read More]

Authors

Kevin Sim
Lecturer
K.Sim@napier.ac.uk
+44 131 455 2497

Areas of Expertise

Associated Projects