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: | Appa G., Magos D., Mourtos I. |
Keywords: | programming: assignment |
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.