A branch & cut algorithm for a four-index assignment problem

A branch & cut algorithm for a four-index assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20051537
Country: United Kingdom
Volume: 55
Issue: 3
Start Page Number: 298
End Page Number: 307
Publication Date: Mar 2004
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: programming: assignment
Abstract:

In this paper, we examine the orthogonal Latin squares (OLS) problem from an integer programming perspective. The OLS problem has a long history and its significance arises from both theoretical aspects and practical applications. The problem is formulated as a four-index assignment problem whose solutions correspond to OLS. This relationship is exploited by various routines (preliminary variable fixing, branching, etc) of the Branch & Cut algorithm we present. Clique, odd-hole and antiweb inequalities implement the ‘Cut’ component of the algorithm. For each cut type a polynomial-time separation algorithm is implemented. Extensive computational analysis examines multiple aspects concerning the design of our algorithm. The results illustrate clearly the improvement achieved over simple Branch & Bound.

Reviews

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