Title: On the complexity of separation: the three-index assignment problem
Authors: Dokka Venkata Satyanarayana, Trivikram
Mourtos, Ioannis
Spieksma, Frits
Issue Date: Oct-2012
Publisher: KU Leuven - Faculty of Economics and Business
Series Title: FEB Research Report KBI_1221 pages:1-24
Abstract: A fundamental step in any cutting plane algorithm is separation: deciding whether a violated inequality exists within a certain class of inequalities. It is customary to express the complexity of a separation algorithm in n, the number of variables. Here, we argue that the input to a separation algorithm can be expressed in jsup(x)j, where sup(x) denotes the vector containing the positive components of x. This input measure allows one to take sparsity into account. We apply this idea to two known classes of valid inequalities for the three-index assignment problem, and we nd separation algorithms with a better complexity than the ones known in literature. We also show empirically the performance of our separation algorithms.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven

Files in This Item:
File Description Status SizeFormat
KBI_1221.pdfOn the complexity of separation: the three-index assignment problem Published 607KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.