Journal
OPTIMIZATION METHODS & SOFTWARE
Volume 20, Issue 1, Pages 127-143Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/10556780410001697695
Keywords
multidimensional assignment problem; combinatorial optimization; computational results
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available