Fast separation for the three-index assignment problem

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

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)39–59
JournalMathematical Programming Computation
Early online date07 May 2016
DOIs
Publication statusPublished - Mar 2017
Externally publishedYes

Cite this