The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation

Mourad Baïou () and José Rafael Correa
Additional contact information
Mourad Baïou: CECO - Laboratoire d'économétrie de l'École polytechnique - X - École polytechnique - IP Paris - Institut Polytechnique de Paris - CNRS - Centre National de la Recherche Scientifique
José Rafael Correa: CECO - Laboratoire d'économétrie de l'École polytechnique - X - École polytechnique - IP Paris - Institut Polytechnique de Paris - CNRS - Centre National de la Recherche Scientifique

Working Papers from HAL

Abstract: Let G=(V,E) be an undirected 2-edge connected graph with weights on its edges and nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G , of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP is studied. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, a class of new valid inequalities is defined together with sufficient conditions for them to be facet-defining. Finally, a polynomial time algorithm is given to separate a subclass of these new iinequalities. As a consequence, all these new inequalities may be separated in polynomial time when G is series-parallel.

Keywords: Combinatorial optimization; Polyhedral combinatorics; Graph connectivity; Optimisation combinatoire; La connexité dans les graphes; Polyèdres (search for similar items in EconPapers)
Date: 2003
Note: View the original document on HAL open archive server: https://hal.science/hal-00242945
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://hal.science/hal-00242945/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:wpaper:hal-00242945

Access Statistics for this paper

More papers in Working Papers from HAL
Bibliographic data for series maintained by CCSD ().