Branch and bound algorithms for the multidimensional assignment problem

Branch and bound algorithms for the multidimensional assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20053301
Country: United Kingdom
Volume: 20
Issue: 1
Start Page Number: 127
End Page Number: 143
Publication Date: Feb 2005
Journal: Optimization Methods & Software
Authors: , ,
Keywords: programming: branch and bound
Abstract:

This work investigates two branch and bound algorithms based on different tree representations of the multidimensional assignment problem (MAP). The MAP may be depicted as either an index-based tree in which every level of the tree represents a different value of the first index or as a permutation-based tree that has vertices representing different permutation vectors of a feasible solution. We also look at the benefits of sorting the cost coefficients on each index tree level, performing a local search on either just the initial solution or every time we find a better solution, and attempting to use characteristics of previous good solutions through path relinking. The number of dimensions and the number of elements in each dimension will affect algorithm performance. We demonstrate the benefits and drawbacks of using different modifications to the branch and bound approach on different sizes of MAP instances.

Reviews

Required fields are marked *. Your email address will not be published.