Abstract—The bin packing problem is well known as an NP-hard problem. Our project analyzes polynomial-time approximation algorithms, i.e., algorithms that construct packing that use relatively few bins, although not necessarily the smallest possible number. We will try to analyze the efficacy of various approximation algorithms by implementing in a software. We will make an empirical study of various approximation algorithms by generating test cases and eval- uate the performance of the algorithms by comparing these approximation algorithms against each other and see how close each of them gets to optimal solution.
Keywords- Bin packing, Empirical study of algorithms, Heuristics, Operational complexity, Run time complexity, Approximation algorithm.
INTRODUCTION
Bin packing problem is known to be NP-hard. Therefore the research focus has been on approximation algorithms. Approximation algorithms are algorithms used to find approximate solutions to optimization problems. In the classical one-dimensional bin packing problem, one is given a list of elements, with an element height for each element in the list. One desires to pack the elements into a minimum number of fixed capacity (of capacity bin height) bins. In other words this problem can be translated as a partition of the items into disjoint subsets such that the sum of the sizes of the items in each subset is no more than the bin size, and such that the number of the bins used is as small as possible. This problem finds many industrial applications such as filling up containers, loading trucks with weight capacity, and creating file
backup in removable media.The approximation algorithms use heuristics. A heuristic is a method to help solve a problem in an informal way by using educated guesses, intuitive judgments or simply common sense. Heuristics give a solution that is usually reasonably close to the best possible answer. By using heuristics in bin packing problem we can accomplish results which, though very good in most cases, may not be the optimal solution.
Heuristics help us make algorithms that compromises with the optimal solution for an improvement in run
time. Each approximation algorithm that is used for bin packing will make a choice between good running time and proximity to optimal solution for different number of object quantities.
PROJECT OBJECTIVE
To make an empirical study of the performance of different approximation algorithms for the bin packing
problem and, to evaluate the experimental performance against the claimed theoretical performance and compare the various algorithms.
PROJECT METHODOLOGY
1) To design and implement a system which incorporates alternative approximate algorithms for the bin
packing problem
2) Simulate the system with suitable family of test cases.
3) Analyze the results and evaluate the performance of each approximation algorithm against each other.
SYSTEM DESCRIPTION
Basically the whole system is divided into 3 modules.
1) Problem Generator:
• Given the number n of objects to be packed, this module randomly generates n objects whose height lies between 0 and 1.
• The option to select the distribution from which the element heights are to be selected is also
given in automatic element generation.
• The option to enter the height of the n objects manually is also provided.
2) Simulator:
• Given an array of n objects to be sorted into bins, this module utilizes the different approximation
algorithms to carry out the sorting.
• The defined parameters such as number of bins, running time, number of operations, etc are
output and stored in files.
3) Analyzer:
• Analyzes the output parameters, using statistical tools if suitable.
• Displays the analysis in suitable formats, graphs, charts etc.
Post a Comment