Integer Programming Formulations for the k-Edge-Connected 3-Hop-Constrained Network Design Problem

Mahjoub, Ali Ridha; Diarrassouba, Ibrahima; Gabrel, Virginie

Mahjoub, Ali Ridha; Diarrassouba, Ibrahima; Gabrel, Virginie (2010), Integer Programming Formulations for the k-Edge-Connected 3-Hop-Constrained Network Design Problem, 24th European Conference on Operational Research, 2010-07, Lisbonne, Portugal

Type

Communication / Conférence

Date

2010

Conference title

24th European Conference on Operational Research

Conference date

2010-07

Conference city

Lisbonne

Conference country

Portugal

Metadata

Show full item record

Author(s)

Mahjoub, Ali Ridha
Diarrassouba, Ibrahima
Gabrel, Virginie

Abstract (EN)

In this paper, we study the k-edge-connected network design problem with bounded paths. We introduce new integer programming formulations for this problem. Then we study the polytopes associated with these formulations and introduce some classes of valid inequalities as well as conditions for these inequalities to deﬁne facets. Using these results, we devise Branch-and-Cut and Branch-and-Cut-and-Price algorithms for the problem and give some computational results.

Subjects / Keywords

k-edge-connected network