Weight Annealing Heuristics for Solving Bin Packing and other Combinatorial Optimization Problems: Concepts, Algorithms and Computational Results

Abstract

The application of weight annealing to combinatorial optimization problems is relatively new, compared to applications of well-known optimization techniques such as simulated annealing and tabu search. The weight annealing approach seeks to expand a neighborhood search by creating distortions in different parts of the search space. Distortion is controlled through weight assignment based on insights gained from one iteration of the search procedure to the next with a view towards focusing computational efforts on the poorly solved regions of the search space. The search for the global optimum should be accelerated and the solution quality should be improved with weight annealing.

In this dissertation, we present key ideas behind weight annealing and develop algorithms that solve combinatorial optimization problems. Our weight annealing-based heuristics solve the one-dimensional bin packing problem and the two-dimensional bin packing problem with and without guillotine cutting and item orientation constraints. We also solve the maximum cardinality bin packing problem and the multidimensional multiple knapsack problem with our heuristics.