Computational Investigations on 3-dimensional Axial Assignment Problems

. Branch and bound approaches for axial three-dimensional assignment problems are considered. Several branching schemes arising from facet defining inequalities are investigated. Further different bounding procedures are tested, such as reduction methods and bounds found by non-smooth nonlinear programming methods. The computational tests show that the classical branching on one variable together with a reduction step and bounds obtained by subgradient methods yield the best results. Keywords. 3-dimensional assignment problems, branch and bound methods, subgradient methods. 1 Introduction Axial 3-dimensional assignment problems of size n, 3AP for short, are combinatorial problems of the form (3AP ) min n X i=1 n X j=1 n X k=1 c ijk x ijk subject to n X i=1 n X j=1 x ijk = 1 8 k = 1; : : : ; n n X i=1 n X k=1 x ijk = 1 8 j = 1; : : : ; n n X j=1 n X k=1 x ijk = 1 8 i = 1; : : : ; n where x ijk 2 f 0; 1g: It is known that axial 3AP s are NP-hard (Karp [10]),..