### Fast separation for the three-index assignment problem

*Trivikram Dokka, Ioannis Mourtos, Frits C. R. Spieksma*

#### Abstract

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector *x* violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables *n*. Here, we argue that a separation algorithm may instead process the vector containing the positive components of *x*, denoted as *supp*(*x*), which offers a more compact representation, especially if *x* is sparse; we also propose to express the time complexity in terms of |*supp*(*x*)|. Although several well-known separation algorithms exploit the sparsity of *x*, we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |*supp*(*x*)| instead of *n*. We indicate that this can be generalized to the axial *k*-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.

Full Text: PDF

© MPS 2008-2018