Iterative improvement approaches for collecting weighted items in directed bipartite graphs

Abstract

In this paper, an iterative improvement heuristic based on the simulated annealing is designed for a weighted item collecting problem in directed bipartite graphs. The weighted item collecting problem is a generalization of an integrated circuit design problem, and it is also a variant of 0-1 knapsack problems in graphs. Recently, a greedy heuristic algorithm has been presented for the weighted item collecting problem. The greedy heuristic algorithm obtains an optimal solution of a known test instance of the original integrated circuit design problem in a short execution time, while for a randomly generated instance, there may be some room for improvement of the heuristic quality. In order to search for a better heuristic solution, some neighborhood structures for an incumbent solution are defined, and each of them is embedded in a framework of the simulated annealing. Numerical experiments are conducted to examine the iterative improvement performance, and the results are reported.

Keywords

• engineering optimization
• 0-1 knapsack problems
• directed bipartite graphs
• arc reversing strategy
• simulated annealing