Mathematical Programming Computation, Volume 9, Issue 1, March 2017

Font Size:  Small  Medium  Large

Fast separation for the three-index assignment problem

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


p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Times; color: #181a18} span.s1 {font: 10.0px Helvetica}


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

mpc footer
© MPS 2008-2018