Fast separation for the three-index assignment problem

T. Dokka, I. Mourtos, F.C.R. Spieksma

Research output: Contribution to journalArticleAcademicpeer-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
Number of pages21
JournalMathematical Programming Computation
Volume9
Issue number1
DOIs
Publication statusPublished - Mar 2017
Externally publishedYes

Keywords

  • 90C10
  • 90C27
  • 90C57

Cite this