Linear-time separation algorithms for the three-index assignment polytope

Balas and Saltzman identified several classes of facet inducing inequalities for the three-index assignment polytope, and gave O(n⁴) separation algorithms for two of them. The authors give O(n³) separation algorithms for these two classes of facets, and also for a third class. Since the three-index assignment problem has n³ variables, these algorithms are linear-time and their complexity is best possible.