1. Polyhedral results for two-connected networks with bounded rings
- Author
-
Marylène Labbé, Bernard Fortz, Fortz, Bernard, Graphes et Optimisation Mathématique [Bruxelles] (GOM), and Université libre de Bruxelles (ULB)
- Subjects
Facet (geometry) ,Ring (mathematics) ,021103 operations research ,[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO] ,General Mathematics ,0211 other engineering and technologies ,Graph theory ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] ,Edge (geometry) ,Polyhedral combinatorics ,01 natural sciences ,Telecommunications network ,Combinatorics ,Network planning and design ,Communication networks ,Polyhedron ,branch-and-cut ,010201 computation theory & mathematics ,Bounded function ,Recherche opérationnelle ,Software ,Mathematics - Abstract
We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “ring”) does not exceed a given length K.¶We present here a new formulation of the problem and derive facet results for different classes of valid inequalities. We study the separation problems associated to these inequalities and their integration in a Branch-and-Cut algorithm, and provide extensive computational results., SCOPUS: ar.j, info:eu-repo/semantics/published
- Published
- 2002