Home > Research > Publications & Outputs > Fast separation for the three-index assignment ...

Electronic data

  • MPC_R2

    Accepted author manuscript, 929 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

View graph of relations

Fast separation for the three-index assignment problem

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
Close
<mark>Journal publication date</mark>03/2017
<mark>Journal</mark>Mathematical Programming Computation
Issue number1
Volume9
Number of pages21
Pages (from-to)39-59
Publication StatusPublished
Early online date7/05/16
<mark>Original language</mark>English

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.