Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4959775 | European Journal of Operational Research | 2017 | 35 Pages |
Abstract
We propose a cut-based formulation for the problem, and design two exact algorithmic approaches: one based on the separation of connectivity cut inequalities, and the other corresponding to a Benders decomposition of the former model. Both approaches are enhanced by various techniques, including (i) preprocessing, (ii) stabilized cut generation, (iii) primal heuristics, and (iv) cut management. These two algorithmic alternatives are computationally evaluated and compared with a previously proposed flow-based formulation. We illustrate the effectiveness of the algorithms on two types of instances derived from protein-protein interaction networks (available from the previous literature) and from telecommunication access networks.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Eduardo Álvarez-Miranda, Ivana LjubiÄ, Martin Luipersbeck, Markus Sinnl,