Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut |
| |
Authors: | B Fortz A R Mahjoub S T McCormick P Pesneau |
| |
Institution: | (1) Institut d'Administration et de Gestion, Université Catholique de Louvain, Louvain-la-Neuve, Belgique;(2) LIMOS CNRS, Université Blaise Pascal, Clermont-Ferrand, France;(3) Sauder School of Business, University of British Columbia, Vancouver, Canada;(4) LIMOS CNRS, Université Blaise Pascal, Clermont-Ferrand, France;(5) IAG, Université Catholique de Louvain, Louvain-la-Neuve, Belgique |
| |
Abstract: | We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that
the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together
with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design
variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We
give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated
with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results. |
| |
Keywords: | 90B10 90C27 90C57 |
本文献已被 SpringerLink 等数据库收录! |
|