Professeur Mr A Ridha Mahjoub

Mr Faouzi

Ben Charrada

Keywords: k-node-connected graph, k-node-disjoint hop-constrained paths, survivable network, polytope, facet, separation, Branch-and-Cut, Branch-and-Cut-and-Price. vi . . .

Je tiens à remercier

Résumé long

La conception des réseaux fiables est un large domaine de recherche qui est question importante dans les télécommunications. L'objectif est de concevoir des réseaux efficaces, fiables et à coût réduit, avec des caractéristiques et des exigences spécifiques sur la topologie. La fiabilité est généralement exprimée en termes de connectivité dans le réseau. Le niveau de connectivité dépend des exigences de chaque opérateur de télécommunication. Il peut être nécessaire de concevoir plusieurs chemins pour relier chaque paire de sommets pour assurer la transmission en cas de déconnexion ou de panne, tout cela au moindre coût possible.

Par conséquent, il devient nécessaire de proposer des solutions pour satisfaire la demande des utilisateurs et d'assurer une utilisation efficace des ressources du réseau.

La majorité des travaux proposés dans la littérature ont considéré uniquement les graphes k-arête-connexe. Pour plusieurs types de graphes, cette conception peut ne pas être très fiable. En effet, plusieurs noeuds ou routeurs dans le cas des réseaux de télécommunication peuvent tomber en panne et cela peut causer une mauvaise circulation et une perte des données. L'étude des graphes k-sommet-connexes devient donc un critère fondamental dans la mise en place d'une conception efficace des réseaux, pour éviter les pannes engendrant une interruption du service, et pour assurer l'acheminement permanent des données.

Un réseau peut être représenté par un graphe G = (V, E) où V est l'ensemble de sommets et E, l'ensemble des arêtes. Plusieurs topologies ont été proposées pour la conception de réseaux. Cependant, la plus fréquente et la plus utile en pratique est la topologie uniforme. C'est à dire que tous les sommets du réseau ont la même importance, et il est requis que entre chaque paire de sommets il existe au moins k chemins arête-(sommet-)disjoint, où k est un entier donné tel que k ≥ 2. Ainsi le réseau peut demeurer fonctionnel quand au plus k -1 arêtes (sommets) tombent en panne. Le problème consiste à déterminer, compte tenu des poids sur les liens possibles du graphe, un sous-graphe de poids minimum satisfaisant l'arête ou la sommet connexité.

Résumé long vii polyèdrale en particulier. Nous donnons notamment un aperçu des méthodes des plans sécants et de génération de colonnes, ainsi que des algorithmes de coupes et branchements, et de génération de colonnes et branchements. Nous donnons alors quelques définitions basiques sur la théorie des graphes et introduisons la terminologie et les notations utilisées dans ce manuscrit. Enfin, nous présentons un état de l'art sur les problèmes de conception de réseaux. Dans le chapitre suivant nous présentons le contexte pratique ainsi que les enjeux technologiques de ce travail.

Dans le deuxième chapitre, nous considérons le problème du sous-graphe k-sommetconnexe, avec k ≥ 3. Nous nous intéressons au polyèdre associé à ce problème et à l'étude de sa dimension. Nous présentons certaines classes d'inégalités valides et nous décrivons certaines conditions pour que ces inégalités définissent des facettes pour le polytope associé. Nous étudions également les propriétés structurelles des points extrêmes de la relaxation linéaire du problème et présentons des opérations de réduction, qu'on utilise comme préprocessing avant la phase de séparation. Ces opérations permettent d'effectuer la séparation des inégalités valides dans un graphe réduit.

Le troisième chapitre porte sur l'algorithme de coupes et branchements que nous proposons pour la formulation du problème. Cet algorithme est basé sur les résultats théoriques introduits dans le chapitre précédent. Nous donnons d'abord un aperçu du fonctionnement de cet algorithme, puis nous détaillons les procédures de séparation utilisées. L'objectif de ce chapitre est de présenter la mise en oeuvre de l'approche proposée dans le chapitre précédent et de donner un aperçu de l'efficacité des contraintes utilisées en pratique. Nous présentons des résultats de calcul pour k = 3, 4, 5 (voir les Tableaux 1 et 2 pour k = 3). L'algorithme est testé sur des instances réelles issues de la SNDlib[1] et de la TSPlib [2]. Les expériences montrent en particulier l'efficacité des procédures de séparation qu'on utilise dans l'algorithme de Branch-and-Cut et l'amélioration significative fournie par les inégalités introduites pour renforcer la relaxation linéaire du problème. Les résultats de calcul qu'on obtient montrent aussi que les inégalités de F -sommet-partition, les inégalités de SP-sommet-partition et les inégalités de partition sont efficaces pour résoudre le problème. En outre, les opérations de réduction que nous utilisons se révèlent efficaces dans la phase de séparation de l'algorithme Branch-and-Cut. Les expériences montrent également que le problème devient plus facile lorsque k augmente, et est plus difficile lorsque k est impair que lorsque k est pair. L'étude présentée dans ce chapitre montre l'efficacité de certaines inégalités valides, à savoir les F -sommet-partition, les SP-sommet-partition et les inégalités de partition, dans la résolution du problème. Il serait intéressant d'approfondir l'étude du polytope du problème et d'identifier les cas où ces inégalités définissent complètement le polytope Dans le quatrième chapitre, nous présentons une formulation étendue pour le problème du sous-graphe k-sommet-connexe pour k = 2. Nous étudions un algorithme de génération de colonne et des heuristiques efficaces pour résoudre le problème. Et en utilisant ces résultats, nous mettons au point un algorithme Branch-and-Cut-and-Price pour résoudre le problème.

Les résultats de calcul montrent que l'algorithme de génération de colonnes est effi-Résumé long ix cace pour résoudre le problème et pour produire une bonne borne supérieure pour le problème (voir Tableaux 3 et 4). En outre, on démontre que l'algorithme de Branchand-Cut est plus efficace pour résoudre le problème à l'optimalité. Nous observons également que lorsque l'on s'approche d'une valeur de LP optimale, l'algorithme de génération de colonnes a du mal à trouver la valeur optimale bien qu'elle soit proche. Ce phénomène est connu comme l'effet de "tailing off". Comme décrit dans [START_REF] Desrosiers | A Primer in Column Generation[END_REF], une explication principale pour l'effet de "tailing off" est que les variables convergent lentement vers leur valeur optimale respective et, d'une itération à l'autre, prennent des valeurs non liées et aléatoires. Comme que travail futur, nous pouvons considérer des solutions pour diminuer cet effet, ce qui pourra améliorer l'efficacité de la résolution en introduisant un algorithme qui stabilise et accélère le processus de solution tout en restant dans le cadre de programmation linéaire. L'algorithme de stabilisation peut être utilisé pour améliorer le temps de résolution des solutions pour les cas difficiles et pour résoudre des problèmes plus importants.

On peut également essayer d'étendre l'approche développée dans ce chapitre pour Les instances que nous avons testés dans ce chapitre montrent que l'algorithme de Branch-and-Cut est assez efficace pour résoudre le problème lorsque L = 3 et k = 3, 4, 5, et ceci, pour les deux ensembles d'instances, arbitraires et routées. Il est également à souligner que les instances de grande taille sont encore difficiles à résoudre dans les 5 heures de temps maximal, mais les gaps obtenus sont dans la plupart des cas sont assez intéressants. De plus, les expériences montrent l'importance des inégalités de doublecut et de Steiner-SP-partition, alors que les inégalités de partition semblent être moins efficaces.

Il convient également de noter que, contrairement au problème de conception de réseaux fiables sans contraintes de borne, nos expériences ne permettent pas de conclure sur l'impact d'une augmentation de la connectivité k sur la résolution du problème. En fait, les expériences antérieures faites pour le problème de conception de réseaux fiables ont conclu que le problème sans considérer les contraintes de borne semble devenir plus xii Résumé long facile lorsque k augmente. Dans notre cas, l'impact de la connectivité sur la résolution est moins clair. Il semble même, lors de la comparaison des résultats pour L = 3 et L = 4, que le problème devient plus difficile à résoudre lorsque L augmente. L'étude du calcul souligne qu'un très grand nombre d'inégalités de st-cut et de 3-stpath-cut ont été générées lors de la résolution du problème. Cela peut être un problème puisqu'il oblige l'algorithme Branch-and-Cut de gérer un énorme pool de contraintes et peut impliquer une consommation de temps de CPU excessive pour la gestion de ces contraintes. Cela peut empêcher l'algorithme d'avoir une bonne exploration de l'arbre Branch-and-Cut.

Les expériences que nous avons effectuées pour le problème de conception de réseaux fiables k-sommet-connexes avec contraintes de borne pour k = 3, 4, 5 et L = 3 ont un temps CPU relativement élevé. Ces observations suggèrent qu'un algorithme efficace pour le problème nécessite une formulation plus étroite pour le problème. On peut mener une étude plus approfondie sur le polytope du problème afin de fournir plus d'inégalités définissant des facettes et de produire un algorithme efficace de coupe et branchement.

On peut également utiliser les graphes orientés appropriés et en exploitant les résultats connus sur les problèmes de chemins disjoints dans les graphes orientés. Cela peut aider à fournir de nouvelles facettes pour le problème. Il serait également intéressant, d'un point de vue algorithmique, d'améliorer les procédures de séparation prévues pour les différentes inégalités que nous avons introduites dans ce travail. Nous devons développer des heuristiques de séparation plus efficaces pour l'algorithme de Branch-and-Cut. Il sera également intéressant de se concentrer sur des méthodes de prétraitement plus sophistiquées afin de faciliter la résolution du problème. Il sera également intéressant d'effectuer les expérimentations pour L = 4 et tout k. Le même type d'étude peut être utilisé pour le problème lorsque L ≥ 5. Si possible, cela peut fournir une formulation en nombres entiers pour le problème ainsi qu'un algorithme de Branch-and-Cut pour tout k ≥ 2 et L = 5.

Il existe de nombreuses directions dans lesquelles la recherche dans cette thèse peut être poursuivie pour les deux problèmes considérés. À des fins théoriques, il devrait être intéressant d'étudier le polyope du problème dans certains cas spéciaux, comme par exemple lorsque le graphe est série-parallèle. En outre, on pourrait étudier le problème du point de vue de la répartition des demandes, car cela peut influencer la description

Introduction

The design of survivable networks is an important issue in telecommunications. The aim is to conceive cheap, efficient and reliable networks with specific characteristics and requirements on the topology. Survivability is generally expressed in terms of connectivity in the network. The level of connectivity depends on the need of each telecommunication operator. We may have to conceive several paths to link each pair of nodes to ensure the transmission in case of disconnection or breakdown, all this at the cheapest possible cost. Therefore, it becomes necessary to propose solutions to satisfy user demand, and ensure an efficient use of network resources.

A network can be represented by a graph G = (V, E) where V is the set of nodes and E, the set of edges. Different topologies have been proposed to design survivable networks. However, as we can see in [START_REF] Kerivin | Design of survivable networks: A survey[END_REF][START_REF] Ko | Heuristics for designing highly survivable communication networks[END_REF], the most frequent and useful case in practice is the uniform topology. This means that the nodes of the network have all the same importance and it is required that between every pair of nodes there are at least k edge-(node-) disjoint paths, where k is a fixed integer such that k ≥ 2. Thus the network will be still functional when at most k -1 edges (nodes) fail. The underlaying problem is to determine, given weights on the possible links of the network, a minimum weight network satisfying the edge or the node connectivity. This thesis deals with the node connectivity of the problem. However this connectivity requirement may not unfortunately be sufficient to guarantee a high survivability and a routing quality. In fact, for some special networks such as VPN (Virtual Private Networks), we may need a higher degree of connectivity. Moreover, the alternative routing path in the network may be too long and costly and this may cause a significant degradation in the transfer speed. In order to limit the rerouting length and guarantee a high QoS, it is commonly required that the length (number of edges) of the paths between an origin-destination pair is bounded by a given number L depending on technological parameters. The problem is then to determine, given weights on the possible links of the network, and pairs of origin-destinations, a minimum weight network containing at least k edge (node) disjoint paths between each pair of origin-destination of length no more than L. This thesis deals with the node connectivity case of the problem.

As the 2-connected topolgy (k = 2) provides an adequate level of survivability since most failure usually can be repaired relatively quickly, we will study the problem for k = 2, with a different, but related method to solve MIPs, namely the branch-andprice method and its extension, the branch-cut-and-price method. It relies on exploiting problem structures in a MIP via a decomposition. The problem is split into a coordinating problem and one or more typically well structured subproblems that can often be solved efficiently. For many difficult but well structured combinatorial optimization problems, this approach leads to a better performance than a branch-and-cut algorithm.

The survivable network design problem has been widely studied when the paths required between the nodes are edge-disjoint or when the connectivity requirement is low (k = 2). However the high node-connectivity requirement case (k ≥ 3) has received a little attention. In this thesis, we study the survivable network design problem with high node-connectivity requirement. In particular, we focus on two variants of the problem: when k-node-disjoint paths are required between every pair of nodes (the knode-connected subgraph problem) and when k-node-disjoint paths of length at most L are required between certain pairs of nodes (the k-node-disjoint hop-constrained network design problem). The study is led using the polyhedral approach and provides exact and efficient algorithms to solve these problems. This thesis is organized as follows. In Chapter 1, we present the basic notions of combinatorial optimization and notations that will be used throughout this thesis. We laso present a state-of-the-art on survivable network design problems. Chapters 2 and 3 concern the first considered network design problem, that is the k-Node-Connected Subgraph Problem (kNCSP). We investigate the kNCSP polytope and present several classes of valid inequalities. Then we discuss the conditions under which these inequalities define facets of the polytope. We also consider the polytope associated with the linear relaxation of the problem and present some structural proporties as well as some reduction operations. Using these results we devise a Branch-and-Cut algorithm, and we give some experimental results. In Chapter 5 and 6 we discuss the hop-contrained version of the first problem, namely the k Node-Disjoint Hop-Constrained survivable network Problem(kNDHP). We introduce a new integer programming formulation for this problem and study the associated polytope. We devise a Branch-and-Cut algorithm for the problem and present extensive computational results. In Chapter 4 we devise a Branch-and-Cut-and-Price algorithm for the 2-node-connected subgraph problem and present extensive computational results. This chapter is dedicated to the presentation of some preliminary notions concerning combinatorial optimization, exact approaches and polyhedra. In particular, we give an overview of cutting planes methods as well as Branch-and-Cut algorithms. We then give some basic definitions in graph theory and introduce some notations and terminology that will be used throughout the dissertation. Finally, we give a state-of-the-art on network design problems.

Preliminaries Notions

Combinatorial optimization

Combinatorial optimization is the field of discrete optimization problems. In many applications, the most important decisions (control variables) are discrete in nature. Binary variables model on/off decisions to buy, invest, hire, send a vehicle, or enforce a precedence. Integer variables model indivisible quantities. Extra variables can represent continuous adjustments or amounts. This results in models known as mixed integer programs (MIP), where the relationships between variables and input parameters are expressed as linear constraints and the goal is defined as a linear objective function. MIPs are among the most widely used modeling tools. They allow a fair description of reality; they are versatile; they can handle many non-linearities (and even non-convexities) in the cost function and in the constraints; they are also well-suited for global optimization. However useful they may be, these models are notoriously difficult to solve: good quality estimations of the optimal value (bounds) are required to prune enumeration-based global-optimization algorithms whose complexity is exponential. In the standard approach to solving an MIP is so-called branch-and-bound algorithm : (i) one solves the linear programming (LP) relaxation using the simplex method; (ii) if the LP solution is not integer, one adds a disjunctive constraint on a factional component (rounding it up or down) that defines two sub-problems; (iii) one applies this procedure recursively, thus defining a binary enumeration tree that can be pruned by comparing the local LP bound to the best known integer solution. State-of-the-art MIP solvers, such as the commercial solvers CPLEX of Ilog or Dash-Optimization's Xpress-mp, are remarkably effective. But many real-life applications remain beyond their scope, and the scientific community is actively seeking to extend the capabilities of MIP solvers. Developments made in the context of specific applications often become generic tools over time and see their way into commercial software.

The most effective solution schemes are a complex blend of techniques: cutting planes to better approximate the convex hull of feasible (integer) solutions and hence provide better LP bounds, Lagrangian decomposition methods to produce alternative powerful relaxations, constraint programming to actively reduce the solution domain through logical implications, heuristics and meta-heuristics (greedy, local improvement, or randomized partial search procedures) to produce good candidate solutions, and specialized branch-and-bound or dynamic programming enumeration schemes to find a global optimum. The real challenge is to integrate the most efficient methods into one global system. Another key to further progress is the development of stronger problem formulations whose relaxations provide approximations that enable enhanced truncation of enumerative solution schemes. Tighter formulations are also much more likely to yield good quality approximate solutions through rounding techniques. With properly chosen formulations, exact optimization tools can be competitive with other methods (such as meta-heuristics) in constructing good approximate solutions within limited computational time, and of course has the important advantage of being able to provide a performance guarantee through the relaxation bounds.

Combinatorial Optimization is a branch of operations research related to computer science and applied mathematics. Its purpose is the study of optimization problems where the set of feasible solutions is discrete or can be represented as a discrete one. Typically, the problems concerned with combinatorial optimization are those formulated as follows. Let E = {e 1 , . . . , e n } be a finite set called basic set where each element e i is associated with a weight c(e i ). Let F be a family of subsets of E. If F ∈ F, then c(F ) = e i ∈F c(e i ) denotes the weight of F . The problem consists in identifying an element F * of F whose weight is minimum or maximum. In other words, min(or max){c(F ) : F ∈ F}.

Such a problem is called combinatorial optimization problem. The set F represents the set of feasible solutions of the problem.

The term combinatorial refers to the discrete structure of F. In general, this structure is represented by a graph. The term optimization signifies that we are looking for the best element in the set of feasible solutions. This set generally contains an exponential number of solutions, therefore, one can not expect to solve a combinatorial optimization problem by exhaustively enumerate all its solutions. Such a problem is then considered as a hard problem.

Various effective approaches have been developed to tackle combinatorial optimization problems. Some of these approaches are based on graph theory, while others use linear and non-linear programming, integer programming and polyhedral approach. Besides, several practical problems arising in real life, can be formulated as combinatorial optimization problems. Their applications are in fields as diverse as telecommunications, transport, industrial production planing or staffing and scheduling in airline companies. Over the years, the discipline got thus enriched by the structural results related to these problems. And, conversely, the progress made in computed science have made combinatorial optimization approaches even more efficient on real-world problems.

In fact, combinatorial optimization is closely related to algorithm theory and computational complexity theory as well. The next section introduces computational issues of combinatorial optimization.

Computational complexity

Computational complexity theory is a branch of theoretical computer science and mathematics, whose study started with works of Cook [START_REF] Diarrassouba | The k-node-connected subgraph problem: Formulation, polyhedra and branch-and-cut[END_REF], Edmonds [START_REF] Edmonds | Covers and packings in a family of sets[END_REF] and Karp [START_REF] Karp | Reducibility Among Combinatorial Problems[END_REF]. Its objective is to give a classify a given problem depending on its difficulty. A plentiful literature can be find on this topic, see for example [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] for a detailed presentation of NP-completeness theory.

A problem is a question having some input parameters, and to which we aim to find an answer. A problem is defined by giving a general description of its parameters, and by listing the properties that must be satisfied by a solution. An instance of the problem is obtained by giving a specific value to all its input parameters. An algorithm is a sequence of elementary operations that allows to solve the problem for a given instance. The number of input parameters necessary to describe an instance of a problem is the size of that problem.

An algorithm is said to be polynomial if the number of elementary operations necessary to solve an instance of size n is bounded by a polynomial function in n. We define the class P as the class gathering all the problems for which there exists some polynomial algorithm for each problem instance. A problem that belongs to the class P is said to be "easy" or "tractable".

A decision problem is a problem with a yes or no answer. Let P be a decision problem and I the set of instances such that their answer is yes. P belongs to the class class NP (Nondeterministic Polynomial) if there exists a polynomial algorithm allowing to check if the answer is yes for all the instances of I. It is clear that a problem belonging to the class P is also in the class NP . Although the difference between P and NP has not been shown, it is a highly probable conjecture.

In the class NP , we distinguish some problems that may be harder to solve than others. This particular set of problems is called NP-complete. To determine whether

Preliminaries Notions

7

a problem is NP-complete, we need the notion of polynomial reducibility. A decision problem P 1 can be polynomially reduced (or transformed) into an other decision problem P 2 , if there exists a polynomial function f such that for every instance I of P 1 , the answer is "yes" if and only if the answer of f (I) for P 2 is "yes". A problem P in NP is also NP-complete if every other problem in NP can be reduced into P in polynomial time. The Satisfiability Problem (SAT) is the first problem that was shown to be NP-complete (see [START_REF] Diarrassouba | The k-node-connected subgraph problem: Formulation, polyhedra and branch-and-cut[END_REF]).

With every combinatorial optimization problem is associated a decision problem. Furthermore, each optimization problem whose decision problem is NP-complete is said to be NP-hard. Note that most of combinatorial optimization problems are NPhard. One of the most efficient approaches developed to solve those problems is the so-called polyhedral approach.

Polyhedral approach and Branch-and-Cut

Elements of polyhedral theory

The polyhedral method was initiated by Edmonds in 1965 [START_REF] Edmonds | Maximum matching and a polyhedron with 0,1-vertices[END_REF] for a matching problem. It consists in describing the convex hull of problem solutions by a system of linear inequalities. The problem reduces then to the resolution of a linear program. In most of the cases, it is not straightforward to obtain a complete characterization of the convex hull of the solutions for a combinatorial optimization problem. However, having a system of linear inequalities that partially describes the solutions polyhedron may often lead to solve the problem in polynomial time. This approach has been successfully applied to several combinatorial optimization problems. In this section, we present the basic notions of polyhedral theory. The reader is referred to works of Schrijver [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Efficiency[END_REF] and [START_REF] Mahjoub | Polyhedral Approaches[END_REF].

We shall first recall some definitions and properties related to polyhedral theory.

Let n be a positive integer and x ∈ R n . e say that x is a linear combination of

x 1 , x 2 , . . ., x m ∈ R n if there exist m scalar λ 1 , λ 2 , . . ., λ m such that x = m i∈1 λ i x i . If m i=1 λ i = 1, then x is said to be a affine combination of x 1 , x 2 , . . ., x m . Moreover, if λ i ≥ 0, for all i ∈ {1, . . . , m}, we say that x is a convex combination of x 1 , x 2 , . . ., x m .
Given a set S = {x 1 , . . . , x m } ∈ R n×m , the convex hull of S is the set of points x ∈ R n which are convex combination of x 1 , . . ., x m (see Figure 1.1), that is

conv(S) = {x ∈ R n |x is a convex combination of x 1 , . . . , x m }.

Preliminaries Notions and State-of-the-Art

The points x 1 , . . ., x m ∈ R n are linearly independents if the unique solution of the

elements of S conv(S) Figure 1.1: A convex hull system m i=1 λ i x i = 0 is λ i = 0
, for all i ∈ {1, . . . , m}. They are affinely independent if the unique solution of the system

m i=1 λ i x i = 0, m i=1 λ i = 1, is λ i = 0, i = 1, . . ., m.
A polyhedron P is the set of solutions of a linear system Ax ≤ b, that is P = {x ∈ R n |Ax ≤ b}, where A is a m-row n-columns matrix and b ∈ R m . A polytope is a bounded polyhedron. A point x of P will be also called a solution of P .

A polyhedron P is said to be of dimension p if it has at most p+1 affinely independent solutions. We denote it by dim(P ) = p. We also have that dim(P ) = nrank(A = ), where A = is the submatrix of A of inequalities that are satisfied with equality by all tje solutions of P (implicit equalities). The polyhedron P is full dimensional if dim(P ) = n.

An inequality ax ≤ α is valid for a polyhedron P ⊆ R n if for every solution x ∈ P , ax ≤ α. This inequality is said to be tight for a solution x ∈ P if ax = α. The inequality ax ≤ α is violated by x ∈ P if ax > α. Let ax ≤ α be a valid inequality for the polyhedron P . F = {x ∈ P |ax = α} is called a face of P . We also say that F is a face induced by ax ≤ α. If F = ∅ and F = P , we say that F is a proper face of P . If F is a proper face and dim(F ) = dim(P ) -1 , then F is called a facet of P . We also say that ax ≤ α induces a facet of P or is a facet defining inequality.

If P is full dimensional, then ax ≤ α is a facet of P if and only if F is a proper face and there exists a facet of P induced by bx ≤ β and a scalar ρ = 0 such that F ⊆ {x ∈ P |bx = β} and b = ρa.

If P is not full dimensional, then ax ≤ α is a facet of P if and only if F is a proper face and there exists a facet of P induced by bx ≤ β, a scalar ρ = 0 and λ ∈ R q×n (where q is the number of lines of matrix A = ) such that F ⊆ {x ∈ P |bx = β} and b = ρa + λA = .

An inequality ax ≤ α is essential if it defines a facet of P . It is redundant if the system A ′ x ≤ b ′ } obtained by removing this inequality from Ax ≤ b defines the same polyhedron P . This is the case when ax ≤ α can be written as a linear combination of inequalities of the system A ′ x ≤ b ′ . A complete minimal linear description of a polyhedron consists of the system given by its facet defining inequalities and its implicit equalities.

A solution is an extreme point of a polyhedron P if and only if it cannot be written as the convex combination of two different solutions of P . It is equivalent to say that x induces a face of dimension 0. The polyhedron P can also be described by its extreme points. In fact, every solution of P can be written as a convex combination of some extreme points of P . Figure 1.2 illustrates the main definitions given is this section.

Cutting plane method

Now let P be a combinatorial optimization problem, E its basic set, c(.) the weight function associated with the variables of P and S the set of feasible solutions. Suppose that P consists in finding an element of S whose weight is maximum. If F ⊆ E, then the 0-1 vector x F ∈ R E such that x F (e) = 1 if e ∈ F and x F (e) = 0 otherwise, is called the incidence vector of F . The polyhedron P (S) = conv{x S |S ∈ S} is the polyhedron of the solutions of P or polyhedron associated with P. P is thus equivalent to the linear program max{cx|x ∈ P (S)}. Notice that the polyhedron P (S) can be described by a set of a facet defining inequalities. And when all the inequalities of this set are known, then solving P is equivalent to solve a linear program.

Recall that the objective of the polyhedral approach for combinatorial optimization problems is to reduce the resolution of P to that of a linear program. This reduction induces a deep investigation of the polyhedron associated with P. It is generally not easy to characterize the polyhedron of a combinatorial optimization problem by a system of linear inequalities. In particular, when the problem is NP-hard there is a very little hope to find such a characterization. Moreover, the number of inequalities describing this polyhedron is, most of the time, exponential. Therefore, even if we know the complete description of that polyhedron, its resolution remains in practice a hard task because of the large number of inequalities.

Fortunately, a technique called the cutting plane method can be used to overcome this difficulty. This method is described in what follows.

The cutting plane method is based on the so-called separation problem. This consists, given a polyhedron P of R n and a point x * ∈ R n , in verifying whether if x * belongs to P , and if this is not the case, to identify an inequality a T x ≤ b, valid for P and violated by x * . In the later case, we say that the hyperplane a T x = b separates P and x * (see Figure ).

Grötschel, Lovász and Schrijver [START_REF] Grötschel | The ellipsoid method and its consequences in combinatorial optimization[END_REF] have established the close relationship between separation and optimization. In fact, they prove that optimizing a problem over a polyhedron P can be performed in polynomial time if and only if the separation problem

P x * ax ≥ α Figure 1
.3: A hyperplan separating x * and P associated with P can be solved in polynomial time. This equivalence has permitted an important development of the polyhedral methods in general and the cutting plane method in particular. More precisely, the cutting plane method consists in solving successive linear programs, with possibly a large number of inequalities, by using the following steps. Let LP = max{cx, Ax ≤ b} be a linear program and LP ′ a linear program obtained by considering a small number of inequalities among Ax ≤ b. Let

x * be the optimal solution of the latter system. We solve the separation problem associated with Ax ≤ b and x * . This phase is called the separation phase. If every inequality of Ax ≤ b is satisfied by x * , then x * is also optimal for LP . If not, let ax ≤ α be an inequality violated by x * . Then we add ax ≤ α to LP ′ and repeat this process until an optimal solution is found. Algorithm 1 summarizes the different cutting plane steps.

Note that at the end, a cutting-plane algorithm may not succeed in providing an optimal solution for the underlying combinatorial optimization problem. In this case a Branch-and-Bound algorithm can be used to achieve the resolution of the problem, yielding to the so-called Branch-and-Cut algorithm.

Branch-and-Cut algorithm

Consider again a combinatorial optimization problem P and suppose that P is equivalent to max{cx|Ax ≤ b, x ∈ {0, 1} n }, where Ax ≤ b has a large number of inequali-

= max{cx|A 0 x ≤ b 0 , x ∈ R n }, where A 0 x ≤ b 0 is a subsystem of Ax ≤ b
having a small number of inequalities. Then we solve the linear relaxation of P that is LP = {cx|Ax ≤ b, x ∈ R n } using a cutting plane algorithm whose starting from LP 0 . Let x * 0 denote its optimal solution and A ′ 0 x ≤ b ′ 0 the set of inequalities added to LP 0 at the end of the cutting plane phase. If x * 0 is integral, then it is optimal. If x * 0 is fractional, then we perform a branching phase. This step consists in choosing a variable, say x 1 , with a fractional value and adding two nodes P 1 and P 2 in the Branch-and-Cut tree. The node P 1 corresponds to the linear program

LP 1 = max{cx|A 0 x ≤ b 0 , A ′ 0 x ≤ b ′ 0 , x 1 = 0, x ∈ R n } and LP 2 = max{cx|A 0 x ≤ b 0 , A ′ 0 x ≤ b ′ 0 , x 1 = 1, x ∈ R n }. We then solve the linear program LP 1 = max{cx|Ax ≤ b, x 1 = 0, x ∈ R n } (resp., LP 2 = max{cx|Ax ≤ b, x 1 = 1, x ∈ R n }
) by a cutting plane method, starting from LP 1 (resp. LP 2 ). If the optimal solution of LP 1 (resp. LP 2 ) is integral then, it is feasible for P. Its value is then a lower bound of the optimal solution of P, and the node P 1 (resp. P 2 ) becomes a leaf of the Branch-and-Cut tree. If the solution is fractional, then we select a variable with a fractional value and add two children to the node P 1 (resp. P 2 ), and so on.

Note that sequentially adding constraints of type x i = 0 and x i = 1, where x i is a fractional variable, may lead to an infeasible linear program at a given node of the Branch-and-Cut tree. Or, if it is feasible, its optimal solution may be worse than the best known lower bound of the problem. In both cases, that node is pruned from the Branch-and-Cut tree. The algorithm ends when all nodes have been explored and the optimal solution of P is the best feasible solution given by the Branch-and-Bound tree. This algorithm can be improved by computing a good lower bound of the optimal solution of the problem before it starts. This lower bound can be used by the algorithm to prune the node which will not allow an improvement of this lower bound. This would permit to reduce the number of nodes generated in the Branch-and-Cut tree, and hence, reduce the time used by the algorithm. Furthermore, this lower bound may be improved by comparing at each node of the Branch-and-Cut tree a feasible solution when the solution obtained at the root node is fractional. Such a procedure is referred to as a primal heuristic. It aims to produce a feasible solution for P from the solution obtained at a given node of the Branch-and-Cut tree, when this later solution is fractional (and hence infeasible for P). Moreover, the weight of this solution must be as best as possible. When the solution computed is better than the best known lower bound, it may significantly reduce the number of generated nodes, as well as the CPU time. Moreover, this guarantees to have an approximation of the optimal solution of P before visiting all the nodes of Branch-and-Cut tree, for example when a CPU time limit has been reached.

The Branch-and-Cut approach has shown a great efficiency to solve various problems of combinatorial optimization that are considered difficult to solve, such as the Travelling Salesman Problem [START_REF] Applegate | Implementing the dantzigfulkerson-johnson algorithm for large traveling salesman problems[END_REF]. Note a good knowledge of the polyhedron associated with the problem, together with efficient separation algorithms (exacts as well as heuristics), might help to improve the effectiveness of this approach. Besides, the cutting plane method is efficient when the number of variables is polynomial. However, when the number of variables is large (for example exponential), further methods, as column generation are more likely to be used. In what follows, we briefly introduce the outline of this method.

Column generation and Branch-and-Price

Compact formulations of combinatorial optimization problems often provide a weak linear relaxation. Those problems require then further formulations, whose linear relaxation is closer to the convex hull of feasible solutions. Those reformulations may have a huge number of variables, so that one can not consider them explicitly in the model. we describe a method that suits well to such reformulation, that is the so-called column generation method.

Column generation procedure

The column generation method is used to solve linear programs with a huge number of variables only by considering a few number among these variables. This method was pioneered by Dantzig and Wolfe in 1960 [START_REF] Dantzig | Decomposition principle for linear programs[END_REF] in order to solve problems that could not be handled efficiently because of their size (CPU time and memory consumption). Column generation is generally used either for problems whose structure is suitable for a Dantzig-Wolfe decomposition, or for problems with a large number of variables. Gilmore and Gomory [START_REF] Gilmore | A linear programming approach to the cuttingstock problem[END_REF][START_REF] Gilmore | A linear programming approach to the cuttingstock problem -part ii[END_REF] used this method to solve a cutting stock problem belonging to the later class.

The overall idea of column generation is to solve a sequence of linear programs with a restricted number of variables (also referred to as columns). The algorithm starts by solving a linear program having a small number of variables, and such that a feasible solution for the original problem may be identified using this basis. At each iteration of the algorithm, we solve the so-called pricing problem whose objective is to identify the variables which must enter the current basis. These variables are characterized by a negative reduced cost. The reduced cost associated with a variable is computed using the dual variables associated with the constraints of the problem. We then solve the linear program obtained by adding the generated variables, and repeat the procedure until no variable with reduced cost can be identified by the pricing problem. In this case, the solution obtained from the last restricted program is optimal for the original model. The main step of column generation procedure is summarized in Algorithm 2.

The column generation method can be seen as the dual of the cutting plane method since it adds columns (variables) instead of rows (inequalities) in the linear program. Furthermore, the pricing problem may be NP-hard. One can then use heuristic procedures to solve it. For more details on column generation algorithms, the reader is referred to [START_REF] Vanderbeck | An exact algorithm for IP column generation[END_REF][START_REF] Irnich | Shortest Path Problems with Resource Constraints[END_REF][START_REF] Desrosiers | A Primer in Column Generation[END_REF].

Branch-and-Price algorithm

The solution obtained by a column generation procedure may not be integer. Therefore, to solve an integer programming problem, the column generation method has to be integrated within a Branch-and-Bound framework. This is known a Branch-and-Price algorithm. Branch-and-Price is similar to Branch-and-Cut approach, except that procedure focuses on column generation rather than row generation. In fact, generating variables (pricing) and adding inequalities (cutting plane) are complementary operations to strengthen the linear relaxation of a integer programming formulation.

Algorithm 2: A column generation algorithm

Data : A linear program MP (Master Problem) with a huge number of variables Output : optimal solution x * of MP 1: Consider a linear program RMP (Restricted Master Problem) including only a small subset of variables of the MP; 2: Solve RMP and let x * be an optimal solution; 3: Solve the pricing problem associated with the dual variables obtained by the resolution of the RMP; 4: If there exists a variable x with a negative reduced cost then; 5: add x to RMP. 6: go to 2. 7: else 8:

x * is optimal for MP. 9: return x * .

The Branch-and-Price procedure works as follows. Each node of the Branch-and-Bound tree is solved by column generation, so that variables may be added to improve the linear relaxation of the current LP. The branching phase occurs when no columns price out to enter the basis and the solution of the linear program is not integer.

Branch-and-Price approaches have been widely used in the literature to solve large scale integer programming problems. The applications are in various fields, and even real life problems such as Cutting stock problem [START_REF] Wierstra | The c-myc promoter: Still mystery and challenge[END_REF], Generalized Assignment Problem (GAP) [START_REF] Savelsbergh | A branch-and-price algorithm for the generalized assignment problem[END_REF], Airline Crew Scheduling [START_REF] Fuentes | A new approach to crew scheduling in rapid transit networks[END_REF], Multi-commodity Flow Problems [START_REF] Barnhart | Planning and control of transportation systems: stochastic optimization for robust planning in transportation[END_REF], etc.

Note that, at each node of the Branch-and-Price tree, column generation may be combined with cutting plane approach, to tighten the LP relaxation of the problem. In this case, the algorithm is called Branch-and-Cut-and-Price algorithm. Such a method can be difficult to handle, since adding valid inequalities to the initial model may change the structure and complexity of the pricing problem. However, some successful applications of this algorithm can be found in the literature (see [START_REF] Røpke | Theories of practice -new inspiration for ecological economic studies on consumption[END_REF], [START_REF] Barnhart | Planning and control of transportation systems: stochastic optimization for robust planning in transportation[END_REF] for instance).

Graph theory

In this section we will introduce some basic definitions and notations of graph theory that will be used throughout the chapters of this dissertation. For more details, we refer the reader to [START_REF] Schrijver | Combinatorial Optimization : Polyhedra and Efficiency[END_REF].

The graphs we consider are undirected, finite and loopless.

An undirected graph is denoted by G = (V, E) where V is the node set and E is the edge set. If e ∈ E is an edge with endnodes u and v, we also write uv to denote e. Given a set of nodes Z ⊂ V , we denote by G \ Z the subgraph obtained from G by deleting the nodes in Z and all their incident edges. For W ⊆ V , we let W = V \ W . Given W and W ′ , two disjoint subsets of V , [W, W ′ ] denotes the set of edges of G having one endnode in W and the other one in W ′ . If W ′ = W , then [W, W ′ ] is called a cut of G and denoted by δ G (W ). We will write δ(W ) if the meaning is clear from the context. For W ⊂ V , we denote by E(W ) the set of edges of G having both endnodes in W and by G[W ] the subgraph induced by W . If π = (V 1 , ..., V p ), p ≥ 2, is a partition of V , then we denote by δ G (π) the set of edges having their endnodes in different sets. We may also write δ

G (V 1 , ..., V p ) for δ G (π). Note that for W ⊂ V , δ G (W ) = δ G (W, W ). Let G ′ = (V ′ , E ′ ) with V ′ ⊆ V and E ′ ⊆ E be a subgraph of G. If w(.
) is a weight function which associates with each edge e ∈ E the weight w(e), then the total weight of

G ′ is w(E ′ ) = e∈E ′ w(e).
Given an undirected graph G = (V, E), for all F ⊆ E, V (F ) will denote the set of nodes incident to the edges of F . For W ⊆ V , we denote by E(W ) the set of edges of G having both endnodes in W and G[W ] the graph induced by W , that is the graph (W, E(W )). Given an edge e = uv ∈ E, contracting e consists in deleting e, identifying the nodes u and v and in preserving all the adjacencies. Contracting a node subset W consists in indentifying all the nodes of W and preserving the adjacencies. Given a partition π = (V 1 , ..., V p ), p ≥ 2, we will denote by G π the subgraph induced by π, that is, the graph obtained from G by contracting the sets V i , for i = 1, ..., p. Note that the edge set of G π is the set δ(V 1 , ..., V p ).

A path P of an undirected graph G is an alternate sequence of nodes and edges (u 1 , e 1 , u 2 , e 2 , ..., u q-1 , e q-1 , u q ) where e i ∈ [u i , u i+1 ] for i = 1, ..., q -1. We will denote a path P either by its node sequence (u 1 , ..., u p ) or its edge sequence (e 1 , ..., e q-1 ). The nodes u 1 and u q are called the endnodes of P , while its other nodes are said to be internal. A path is simple if it does not contain the same node twice. In the sequel, we will always consider that the paths are simple. A path whose endnodes are s and t will be called an st-path. A cycle in G is a path whose endnodes coincide, that is u 1 = u q . Also, a cycle is simple if it does not contain twice the same node, excepted u 1 . We call a chord an edge between two non-adjacent nodes of a path. A matching of G is a set of pairwise nonadjacent edges. Given a fixed integer L ≥ 1 and a pair of nodes {s, t} ∈ V × V , an L-st-path in G is a path between s and t whose length is at most L, where the length is the number of edges of that path. The number of edges of a path is also called hops and we also speak of L-hop-constrained paths for paths whose length is at most L.

An undirected graph is connected if for every pair of nodes (u, v) there is at least one path between u and v. A connected graph which have no cycle is called a spanning tree. A connected component of a graph G is a connected subgraph of G which is maximal, that is adding a node or an edge to that subgraph gives a non-connected graph.

Given an undirected graph G = (V, E), two st-paths are edge-disjoint if they have no edge in common. They are node-disjoint if they have no internal node in common. A graph is said to be k-edge-connected if it contains at least k edge-disjoint st-paths for all pair of nodes {s, t} ∈ V × V . It is k-node-connected if it contains at least k node-disjoint st-paths for all pair of nodes {s, t} ∈ V × V . The largest integer k such that the graph is k-node-connected is the node-connectivity of the graph. We say that a graph is Steiner k-edge-connected (k-node-connected) if it is k-edge-connected (k-node-connected) relatively to a certain pair of privileged nodes. We ommit the qualificative Steiner when the required connectivity is for every pair of nodes of the graph. The privileged nodes are called terminal nodes while non-privileged ones are called Steiner nodes.

Given an undirected graph G = (V, E), a demand set D ⊆ V × V is a subset of pairs of nodes, called demands. For a demand {s, t} ∈ D, s is the source of the demand and t is the destination of that demand. If several demands {s, t 1 }, ..., {s, t d } have the same node s as source node, then these demands are rooted in s. A node involved in at least one demand is said to be terminal. A node which does not belong to any demand is called a Steiner node.

A complete graph is a graph in which there is an edge between each node and the others. A complete graph with n nodes is denoted by

K n . A bipartite graph G = (V, E) is an undirected graph such that V = V 1 ∪ V 2 with V 1 ∩ V 2 = ∅ and for every pair of nodes u, v ∈ V 1 (resp. u, v ∈ V 2 ), [u, v] = ∅.
A complete bipartite graph is a bipartite graph where there is an edge between each node of V 1 and the nodes of V 2 . A bipartite complete graph is denoted K m,n where m = |V 1 | and n = |V 2 |. An undirected graph is outerplanar when it can be drawn in the plane as a cycle with non crossing chords. A graph is series-parallel if it can be obtained from a single edge by iterative application of the two operations: i) addition of a parallel edge;

ii) subdivision od an edge.

Observe that a graph is series-parallel (outerplanar) if and only if it is not contractible to K 4 (K 4 and K 3,2 ). Therefore, an outerplanar graph is also series-parallel.

State-of-the-art on network design problems

Survivable network design problems have been widely studied. The aim of the first studies was to produce heuristics and approximation algorithms for these problems. In the last decades, studies starts focusing on exact algorithms with, in particular, the use of the polyhedral approach.

In this section we present the previous works in the litterature related to survivable network design problems. We first present the general survivable network design problem, the related works and main results on this problem. Then we discuss two variants of the problem, the k-node-connected subgraph problem and the k-node-disjoint hopconstrained network design problem. The first one will be studied in Chapters 2, 3 and 4 and the second one in the Chapters 5 and 6.

The general survivable network design problem

A network can be represented by a graph, directed or undirected, where each node of the network corresponds to a node of the graph and a link between two nodes of the network is represented by an edge or an arc of the graph.

Consider an undirected graph G = (V, E) representing a telecommunication network and w(.) a weight function which associates the weight w(e) with an edge e ∈ E. Each node v ∈ V is associated with an integer, denoted by r(v) and called connectivity type of v, which can be seen as the minimum number of edges connecting v to the rest of the network. The vector (r(v) | v ∈ V ) is the connectivity type vector associated with the nodes of G. We say that a subgraph H = (U, F ), U ⊆ V and F ⊆ E, satisfies the edge-connectivity (resp. node-connectivity) requirement if for every pair of nodes (s, t) ∈ V × V , there exist at least r(s, t) = min{r(s), r(t)} edge-disjoint (resp. node-disjoint) paths between s and t. This condition ensures that the traffic will still be routed between s and t when at most r(s, t) -1 links, in the case of edge-connectivity, and at most r(s, t)-1 nodes, in the case of node-connectivity, fail.

Let r max = max{r(v) | u ∈ V }. When r max ≤ 2 we speak of low connectivity requirement and of high connectivity requirement when r max ≥ 3.

Grötschel, Monma and Stoer [START_REF] Grötschel | Polyhedral approaches to network survivability[END_REF] introduced the general survivable network design problem which consists in finding a minimum weight subgraph of G which satisfies the connectivity requirement. This problem is NP-hard as it contains the Steiner tree problem as a special case (r(u) ∈ {0, 1} for all u ∈ V ) which is known to be NP-hard [START_REF] Garey | Computer and intractability: A guide to the theory of NP -completness[END_REF].

Menger [START_REF] Menger | Zur allgemeinen kurventhorie[END_REF] showed the relation between the number of edge-disjoint paths and the cardinality of cuts in the graph G. This relation is given in the theorem below.

Theorem 1 [START_REF] Menger | Zur allgemeinen kurventhorie[END_REF] Let G = (V, E) be an undirected graph and s, t two nodes of G. Then there exist at least k edge-disjoint paths between s and t if and only if every st-cut of G contains at least k edges.

We will denote the edge version (resp. nodes version) of the survivable network design problem by ESNDP (resp. NSNDP). By Theorem 1, the ESNDP can be described as a linear integer program. To this end we introduce some notations.

r(W ) = max{r(u) | u ∈ W } for all W ⊆ V, con(W ) = max{r(u, v) | u ∈ W, v ∈ W } = min{r(W ), r(W )} for all W ⊂ V, ∅ = W = V.
The ESNDP is equivalent to the following linear integer program

Minimize e∈E c(e)x(e)
x(δ(W )) ≥ con(W ), for all W V, W = ∅, (1.1)

x(e) ≥ 0, e ∈ E, (1.2)

x(e) ≤ 1, e ∈ E, (1.3)

x(e) ∈ {0, 1}.

(1.4) Grötschel and Monma [START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF] study the polyhedral aspects of that model. They discuss the dimension of the associated polytope and the facial aspect of the basic inequalities. In [START_REF] Grötschel | Polyhedral approaches to network survivability[END_REF], Grötschel et al. study further polyhedral aspects of that model. They devise cutting plane algorithms and give computational results. In [START_REF] Michel | Survivable networks, linear programming relaxations and the parsimonious property[END_REF], Goemans and Bertsimas give an approximation algorithm based for the ESNDP based on a new analysis of a well-known algorithm for the Steiner tree problem.

The k-edge(node)-connected subgraph problem

The kNCSP has applications in communication and transportation networks ( [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF][START_REF] Grötschel | Polyhedral approaches to network survivability[END_REF][START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF][START_REF] Grötschel | Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints[END_REF][START_REF] Grötschel | Polyhedral and computational investigations for designing communication networks with high survivability requirements[END_REF]). The edge version of the problem has been widely studied in the literature ( [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF][START_REF] Chopra | The k-edge connected spanning subgraph polyhedron[END_REF][START_REF] Biha | k-edge connected polyhedra on series-parallel graphs[END_REF][START_REF] Grötschel | Polyhedral approaches to network survivability[END_REF][START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF][START_REF] Grötschel | Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints[END_REF][START_REF] Grötschel | Polyhedral and computational investigations for designing communication networks with high survivability requirements[END_REF][START_REF]Two-edge Connected spanning subgraphs A. R. Mahjoub and polyhedral. Twoedge connected spanning subgraphs and polyhedra[END_REF]).

In [START_REF] Chopra | The k-edge connected spanning subgraph polyhedron[END_REF] Chopra studied the polyhedron defined by the convex hull of k-edge-connected spanning subgraphs of a given graph G where multiple copies of an edge are allowed. A complete inequality description of the polytope when k is odd and G is an outer planar graph is given. He described a family of facet-defining inequalities of the polytope that have the same support graph and coefficients that depend on the connectivity.

In [START_REF]Two-edge Connected spanning subgraphs A. R. Mahjoub and polyhedral. Twoedge connected spanning subgraphs and polyhedra[END_REF], Mahjoub study the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. He discusses the polytope associated with the solutions to this problem, and shows that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. He also gives some classes of facet defining inequalities of this polytope when the graph is general, and later in [START_REF] Biha | k-edge connected polyhedra on series-parallel graphs[END_REF], Didi Biha and Mahjoub give a complete description of the k-edge connected spanning subgraph polytope, for all k ≥ 0 on series-parallel graphs.

In [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF], Bendali et al. consider the k-edge connected subgraph problem from a polyhedral point of view. They introduce further classes of valid inequalities for the associated polytope and describe sufficient conditions for these inequalities to be facet defining. They also devise separation routines for these inequalities and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, they develop a Branch-and-Cut algorithm and present some computational results.

The kNCSP has been particulary considered for k = 2 (see [START_REF] Diarrassouba | Two node-disjoint hopconstrained survivable network design and polyhedra[END_REF][START_REF] Mahjoub | On the linear relaxation of the 2-node connected subgraph polytope[END_REF]). A little attention has been given for the high connectivity case where k ≥ 3. The kNCSP has been studied by Grötschel et al. ([45,[START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF][START_REF] Grötschel | Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints[END_REF][START_REF] Grötschel | Polyhedral and computational investigations for designing communication networks with high survivability requirements[END_REF]) within a more general survivability model. Grötschel et al. study the model from a polyhedral point of vue and propose cutting plane algorithms.

In [START_REF] Mahjoub | On the linear relaxation of the 2-node connected subgraph polytope[END_REF], Mahjoub and Nocq discuss the linear relaxation of the 2NCSP(G). They describe some structral properties and characterize which they called extreme points of rank 1. They introduce an ordering on the fractional extreme points of the polytope and give a characterization of the minimal extreme points with respect to that ordering. This yields a polynomial method to separate a minimal extreme point of the polytope from the 2-node connected subgraph polytope. It also provides a new class of facet defining inequalities for this polytope.

The k-edge(node)-connected hop-constrained network design problem

The problem is to determine, given weights on the possible links of the network, and pairs of origin-destinations, a minimum weight network containing at least k edge (node) disjoint paths between each pair of origin-destination of length no more than L. This thesis deals with the node connectivity case of the problem.

Consider an undirected graph G = (V, E) with weights c(e), e ∈ E, on the edges, an integer L ≥ 2, and a set of demands D ⊂ V × V . Each demand is an ordered pair (s, t) of nodes, with s = t. Node s is called the source (or origin) of the demand and t its destination. The k-Node-Disjoint Hop-Constrained Network Design Problem (kNDHP for short) is to find a minimum weight subgraph of G containing at least k node-disjoint L-st-paths, that is, paths from s to t with at most L edges (also called hops), between each pair of nodes (s, t) ∈ D. The edge version of the problem has been widely studied in the literature. However, the kNDHP has been only considered for k = 2.

Node version with bounds

The edge version of the problem has been widely studied in the literature. However, the kNDHP has been only considered for k = 2. In [START_REF] Diarrassouba | Two node-disjoint hopconstrained survivable network design and polyhedra[END_REF], Diarrassouba et al. consider the kNDHP for k = 2. Here it is supposed that the two paths are node disjoint and each path does not exceed L edges for a fixed integer L ≥ 1. They investigate the structure of the associated polytope and describe several classes of valid inequalities when L ≤ 3. Based on this, they devise a Branch-and-Cut algorithm. Huygens and Mahjoub [START_REF] Huygens | Integer programming formulations for the two 4-hop-constrained paths problem[END_REF] study the problem when L = 4 and k = 2. They show that the so-called cut and L-path-cut inequalities suffice for formulating the problem in this case. In [START_REF] Chimani | Orientationbased models for {0,1,2}-survivable network design: theory and practice[END_REF], Chimani et al. consider {0, 1, 2}-Survivable Network Design problems with nodeconnectivity constraints. Given an edge-weighted graph and two customer sets R 1 and R 2 , they look for a minimum cost subgraph that connects all customers, and guarantees two-node-connectivity for the R 2 customers. They give a graph characterization of 2-node-connected graphs via orientation properties. Using this, they propose integer programming formulations based on directed graphs.

Edge version with bounds

The edge version of the problem has also been studied by several authors when L = 2, 3. In particular, in [START_REF] Huygens | Two edge-disjoint hop-constrained paths and polyhedra[END_REF] Huygens et al. give a complete and minimal linear description of the corresponding polytope when L = 2, 3 and |D| = 1. In [START_REF] Huygens | The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut[END_REF], Huygens et al. consider the problem when |D| ≥ 2 and two edge disjoint paths are required for each demand. They show that the problem is strongly NP-hard even when the demands in D are rooted at some node s and the costs are unitary. However, if the graph is complete, they prove that the problem in this case can be solved in polynomial time. They give an integer programming formulation of the problem in the space of the design variables when L = 2, 3, and they study the associated polytope. Moreover, they describe several classes of valid inequalities along with necessary and/or sufficient conditions to be facet defining, and propose a Branch-and-Cut algorithm.

In [START_REF] Bendali | The k edge-disjoint 3-hop-constrained paths polytope[END_REF] Bendali et al. consider the more general k edge-disjoint hop-constrained problem (kEDHP) when k edge disjoint paths are required. They discuss a Branchand-Cut algorithm for the problem when L = 2, 3. Huygens and Mahjoub [START_REF] Huygens | Integer programming formulations for the two 4-hop-constrained paths problem[END_REF] study the kEDHP when L = 4 and k = 2. They introduce a new general class of valid inequalities. Using this, they give an integer programming formulation of the problem in the natural space of variables. In [START_REF] Dahl | Notes on polyhedra associated with hop-constrained paths[END_REF], Dahl considers the hop-constrained path problem, that is the problem of finding between two distinguished nodes s and t a minimum cost path with no more than L edges when L is fixed. He gives a complete description of the dominant of the associated polytope when L ≤ 3 and a class of facet defining inequalities for k ≥ 4. Dahl and Gouveia [START_REF] Dahl | On the directed hop-constrained shortest path problem[END_REF] consider the directed hopconstrained shortest path problem. They describe valid inequalities and characterize the associated polytope when L = 2, 3. A related problem is considered in Dahl et al. [START_REF] Dahl | A note on hopconstrained walk polytopes[END_REF], the hop-constrained walk problem. The authors discuss the associated polytope in directed graphs when L = 4.

In [START_REF] Gouveia | Design of survivable networks with vulnerability constraints[END_REF], Gouveia and Leitner consider the Network Design Problem with Vulnerability Constraints. The solutions to the problem are subgraphs containing a path of length at most H st for each commodity {s, t} and a path of length at most H ′ st between s and t after at most k -1 edge failures. They give characterizations of feasible solutions and propose integer programming formulations. In [START_REF] Gouveia | Compact models for hop-constrained node survivable network design, an application to mpls, telecommunications planning: Innovations in pricing, network design and management[END_REF] Gouveia et al. consider the problem with bounded lengths in the context of an MPLS (Multi-Protocol Label Switching) network design model. They discuss two models involving one set of variables associated to each path between each pair of demand nodes (a standard network flow model with additional cardinality constraints and a model with hop-indexed variables) and a third model involving one single set of hop-indexed variables for each demand pair. They show that the aggregated more compact hop-indexed model produces the same linear programming bound as the multi-path hop-indexed model.

Extended formulations for the edge version with bounds

In [START_REF] Botton | On the hop-constrained survivable network design problem with reliable edges[END_REF] Botton et al. consider the hop-constrained survivable network design problem with reliable edges, i.e., edges that are not subject to failure. They study two variants, a static problem where the reliability of the edges is given, and an upgrading problem where edges can be upgraded to the reliable status at a given cost. They adapt for the two variants an extended formulation proposed in Botton et al. [START_REF] Botton | Benders decomposition for the hopconstrained survivable network design problem[END_REF] for the case without reliable edges. They use Benders decomposition to accelerate the solution process. Their computational results indicate that these two variants appear to be more difficult to solve than the original problem (without reliable edges). In [START_REF] Mahjoub | Hop-level flow formulation for the hop constrained survivable network design problem[END_REF] Mahjoub et al. propose an extended formulation for the rooted case, when all the demands have a common vertex, called hop-level multicommodity flow formulation, inspired from the formulation given in [START_REF] Botton | Benders decomposition for the hopconstrained survivable network design problem[END_REF]. The authors introduce the concept of solution level. To each solution of the problem, a partition of the node set into L + 2 levels can be associated according to the distance to the root in the solution. Then they reduce the problem to a specific multicommodity flow problem in an auxiliary layered directed graph.

In Table 1.1 a summary of the previously studied hop constrained network design problems is presented.

Edge and node versions without bounds

The k-node-connected subgraph problem without bounds on the paths has been considered in the literature. In [START_REF] Mahjoub | On the linear relaxation of the 2-node connected subgraph polytope[END_REF], Mahjoub and Nocq discuss structural properties of the 2-node-connected polytope (see also [START_REF] Barahona | On two-connected subgraph polytopes[END_REF]). Grötschel et al. ([45,[START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF][START_REF] Grötschel | Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints[END_REF][START_REF] Grötschel | Polyhedral and computational investigations for designing communication networks with high survivability requirements[END_REF]) study the problem within a more general survivability model. In [START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF] The uniform edge case without hop constraints has been widely investigated. The reader can be referred to [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF][START_REF] Biha | k-edge connected polyhedra on series-parallel graphs[END_REF][START_REF] Biha | The k-edge connected subgraph problem i: Polytopes and critical extreme points[END_REF][START_REF] Grötschel | Polyhedral approaches to network survivability[END_REF][START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF][START_REF] Grötschel | Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints[END_REF][START_REF] Grötschel | Polyhedral and computational investigations for designing communication networks with high survivability requirements[END_REF] for more details.

In Table 1.2, we show the studied survivable network models with node versus edge connectivity.

As indicated in Table 1.2, the kNDHP has not been considered for k ≥ 3. In this chapter we consider the k-Node-Connected Subgraph Problem (kNCSP). We investigate the kNCSP polytope and present several classes of valid inequalities. Then we discuss the conditions under which these inequalities define facets of the polytope. We also we consider the polytope associated with the linear relaxation of the problem and present some structural proporties as well as some reduction operations. Using these results we devise a Branch-and-Cut algorithm, and we give some experimental results. This work has led to a work published in the proceedings of the International Conference CIE45 [START_REF] Diarrassouba | The k-node-connected subgraph problem: Formulation, polyhedra and branch-and-cut[END_REF] and an article published in Computers and Industrial Engineering [START_REF] Mahjoub | The survivable knode-connected network design problem: Valid inequalities and branch-and-cut[END_REF].

Formulation

A graph G = (V, E) is called k-node (resp. k-edge) connected (k ≥ 0) if
for every pair of nodes i, j ∈ V , there are at least k node-disjoint (resp. edge-disjoint) paths between i and j. Given a graph G = (V, E) and a weight function c on E that associates with an edge e ∈ E a weight c(e) ∈ R, the k-node-connected subgraph problem (kNCSP for short) is to find a k-node-connected spanning subgraph

H = (V, F ) of G such that e∈F c(e) is minimum.
Let F be an edge subset of E, then the incidence vector of F , denoted by x F , is the 0 -1 vector defined by

x F (e) = 1 if e ∈ F 0 otherwise. Let F ⊆ E be an edge subset of G. Then F induces a solution of the kNCSP for G, that is, the subgraph of G induced by F is k-node-connected, if x F satisfies the following inequalities
x(e) ≥ 0, e ∈ E, (2.1)

x(e) ≤ 1, e ∈ E, (2.2)

x(δ G (W )) ≥ k, for all W V with W = ∅, (2.3) x(δ G\Z (W )) ≥ k -|Z|, for all Z ⊆ V such that 1 ≤ |Z| ≤ k -1, and (2.4) all W V \Z with W = ∅.
Conversely, any integer solution of the system above is the incidence vector of the edge set of a k-node-connected subgraph of G. Hence, the kNCSP is equivalent to

min{cx | x satisfies (2.1) -(2.4) and x ∈ Z E + }. (2.5)
Constraints (2.3) and (2.4) are called cut and node-cut inequalities, respectively. The convex hull of all integer solutions of (2.1)-(2.4), denoted by kNCSP(G), will be called kNCSP(G) the k-node-connected subgraph problem polytope.

We will also denote by P (G, k) the polytope described by constraints (2.1)

-(2.4).
In what follows we give an alternative formulation for the problem. This consists in restricting the node-cut inequalities (2.4) to the node sets Z ⊂ V such that |Z| = k -1. We hence consider the following set of inequalities

2.1 Formulation 29 x(δ G\Z (W )) ≥ 1, ∅ = Z ⊆ V, |Z| = k -1, (2.6) ∅ = W ⊂ V \Z.
Theorem 2 The kNCSP is equivalent to

min{cx | x satisfies (2.1) -(2.3), (2.6) and x ∈ Z E + }. (2.7)
Proof. It suffices to show that any integer solution x of (2.1)-(2.3),(2.6) also satisfies (2.4). For this we will show that if x satisfies all inequalities x(δ

G\Z (W )) ≥ k -|Z| with |Z| = t for some t ∈ {k -1, ..., 2}, then x satisfies x(δ G\Z ′ (W ′ )) ≥ k -|Z ′ | for all Z ′ ⊂ V with |Z ′ | = t -1 and W ′ ⊂ V \ Z ′ . Indeed, first note that either |V \(W ′ ∪ Z ′ )| ≥ 2 or |W ′ | ≥ 2 or both. In fact, if |V \(W ′ ∪ Z ′ )| = |W ′ | = 1, then |Z ′ | = n -2 (= t -1). But this implies that t = n -1, and, as t ≤ k -1, it follows that k ≥ n, which is impossible. In what follows we suppose, w.l.o.g., that |V \(W ′ ∪ Z ′ )| ≥ 2. We claim that there is at least one node, say u, in V \(W ′ ∪ Z ′ ) such that x([u, W ′ ]) ≥ 1. In fact, let u 0 ∈ V \ (W ′ ∪ Z ′ ). Let Z = Z ′ ∪ {u 0 }. By our assumption, x(δ G\Z (W ′ )) ≥ k -|Z| = k -t. As t ≤ k -1, it follows that x(δ G\Z (W ′ )) ≥ 1. Therefore there is a node u in V \ (W ′ ∪ Z ′ ∪ {u}) such that x([u, W ′ ]) ≥ 1. Now let u ∈ V \(W ′ ∪ Z ′ ) such that x([u, W ′ ]) ≥ 1, and let Z * = Z ′ ∪ {u}. We have |Z * | = t. Again, by our assumption, we have that x(δ G\Z * (W ′ )) = x(δ G\Z ′ (W ′ )) - x([u, W ′ ]) ≥ k -|Z * | = k -t. As x([u, W ′ ]) ≥ 1, it then follows that x(δ G\Z ′ (W ′ )) = x(δ G\Z * (W )) + x([u, W ′ ]) ≥ k -t + 1 = k -|Z ′ |.
As before, we will denote by Q(G, k) the polytope associated with the linear relaxation of (2.7). Clearly, P (G, k) ⊆ Q(G, k). Moreover, the two polytopes may be different, that is P (G, k) = Q(G, k), for some graph G and connectivity k. For example, consider the graph and the solution of Figure 2.1 for k = 3. The solution satisfies the cut inequalities and the node-cut inequalities with |Z| = k -1 = 2, and violates a node-cut inequality with |Z| = k -2 = 1. Indeed, for Z = {v 7 } and W = {v 1 , v 2 , v 3 }, x(δ G\Z (W )) < 2. Thus, formulation (2.5) may produce a better linear relaxation than (2.7). We will hence consider formulation (2.5) for solving the kNCSP.

In the next sections, we investigate the polytope kNCSP(G) and describe some valid inequalities.

The k-node-connected subgraph problem

edges with value 1/3 edges with value 1/2 edges with value 1

1 4 6 7 8 2 3 5 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 Figure 2.1: A solution of Q(G, k) \ P (G, k) for k = 3.

Dimension and Valid inequalities

In this section, we will discuss the polytope kNCSP(G). We will establish its dimension and describe some classes of valid inequalities.

Dimension

Let G = (V, E) be a graph. An edge e is said to be essential if the solutions set of kNCSP(G\e) is empty. Let E * be the set of essential edges of kNCSP. We have the following result. Thus, the result follows.

Theorem 3 dim(kNCSP(G))= |E| -|E * |.
Corollary 1 kNCSP(G) is full-dimensional if and only if G is (k +1)-node-connected.
Now we describe some classes of valid inequalities for kNCSP(G). One can easily see that any solution of the kNCSP on G is also solution of the kECSP on G. Thus, any valid inequality for the kECSP polytope on G is also valid for kNCSP(G).

In the following, we introduce a notation that will be used throughout the remainder of the chapter. Given a partition π = (V 1 , ..., V p ), p ≥ 2, we will denote by G π the subgraph induced by π, that is, the graph obtained by contracting the sets V i , i = 1, ..., p. We will denote by δ G (V 1 , ..., V p ) the set of edges of G π , that is, the edges that have their endnodes in different elements of π.

Node-partition inequalities

In [START_REF] Grötschel | Polyhedral approaches to network survivability[END_REF], Grötschel et al. introduce a class of valid inequalities for a more general version of the kNCSP as follows. Consider a subset Z ⊂ V , such that |Z| ≤ k -1, and let

V 1 , ..., V p , p ≥ 2 be a partition of V \Z. Then the inequality x(δ G\Z (V 1 , ..., V p )) ≥    p(k-|Z|) 2 if |Z| ≤ k -2, p -1 if |Z| = k -1, (2.8)
is valid for the kNCSP(G). Inequalities of type (2.8) are called node-partition inequalities.

SP-node-partition inequalities

Now we introduce a class of inequalities called SP-node-partition inequalities, which generalize the so-called SP-partition inequalities introduced by Didi Biha and Mahjoub [START_REF] Biha | k-edge connected polyhedra on series-parallel graphs[END_REF] for the kECSP(G), where kECSP(G) is the convex hull of the solutions of the kedge-connected subgraph problem. These latter inequalities are defined as follows. Let π = (V 1 , ..., V p ) be a partition of V such that the graph G π is series-parallel. Recall that a graph is series-parallel if it is not contractible to K 4 , the complete graph on four nodes. The SP-partition inequality associated with π is given by

x(δ G (V 1 , ..., V p )) ≥ k 2 p -1.
(2.9)

Didi Biha and Mahjoub [START_REF] Biha | k-edge connected polyhedra on series-parallel graphs[END_REF] showed that these inequalities are valid for the kECSP(G), for every k ≥ 1.

For the kNCSP, we introduce a similar type of inequalities. Let Z ⊂ V such that |Z| ≤ k -1 and k -|Z| is odd, and consider a partition

π = (V 1 , ..., V p ) of V \Z such that (G\Z) π is series-parallel. The SP-node-partition inequality associated with π is The k-node-connected subgraph problem x(δ G\Z (π) ≥ k -|Z| 2 p -1.
(2.10)

Theorem 4

The SP-node-partition inequalities (2.10) are valid for kNCSP(G).

Proof.

Let x ∈ kNCSP(G) and consider x ′ the restriction of x on G\Z. As x ′ ∈ (k -|Z|)ECSP(G\Z), and the SP-partition inequalities (2.9) are valid for (k-|Z|)ECSP(G\Z), we have

x(δ G\Z (V 1 , ..., V p )) = x ′ (δ G\Z (V 1 , ..., V p )) ≥ k -|Z| 2 p -1,
which proves the result.

Chopra [START_REF] Chopra | The k-edge connected spanning subgraph polyhedron[END_REF] (see also Didi Biha and Mahjoub [START_REF] Biha | k-edge connected polyhedra on series-parallel graphs[END_REF]) described a lifting procedure for inequalities (2.10). This can be easily extended to the SP-node-partition inequalities. Let G = (V, E) be a graph and k ≥ 3 an odd integer. Consider the graph G ′ = (V, E∪T ) obtained from G by adding an edge set T . Let Z ⊂ V and π = (V 1 , ..., V p ) be a partition of V \Z such that (G\Z) π is series-parallel. Then the lifted SP-node-partition inequality induced by π is

x(δ G\Z (V 1 , ..., V p )) + e∈T ∩δ G ′ (V 1 ,...,Vp) a(e)x(e) ≥ k -|Z| 2 p -1, (2.11)
where a(e) is the length, that is to say the number of edges, of the shortest path in (G\Z) π between the endnodes of e, for all e

∈ T ∩ δ G ′ (V 1 , ..., V p ).
Chopra [START_REF] Chopra | The k-edge connected spanning subgraph polyhedron[END_REF] shows that inequalities (2.11) are valid for kECSP(G). Therefore they are also valid for kNCSP(G).

F-node-partition inequalities

Let G = (V, E) be a graph and Z a node subset of V . Let π = (V 0 , V 1 , ..., V p ) be a partition of V \Z and F an edge subset of δ G\Z (V 0 ). Let Z i ⊂ Z be the set of nodes of

Z adjacent to the nodes in V i , i = 1, ..., p. Suppose that |Z i | ≤ k -1, for i = 1, ..., p, and Z = i=1,...,p Z i . The following inequality x(δ G\Z (π)\F ) ≥       p i=1 (k -|Z i |) -|F | 2       (2.12)
is called an F -node-partition inequality.

Theorem 5 F -node partition inequalities are valid for the kNCSP(G).

Proof. Consider the following valid inequalities

x(δ G\Z i (V i )) ≥ k -|Z i |, for all i = 1, ..., p, -x(e) ≥ -1, for all e ∈ F,
x(e) ≥ 0, for all e ∈ δ G\Z (V 0 )\F.

By summing these inequalities, we obtain

2x(δ G\Z (π)\F ) ≥ p i=1 (k -|Z i |) -|F |.
By dividing by 2 and rounding up the right hand, we get inequality (2.12).

Facial aspect

In this section, we discuss the facial aspect of the kNCSP polytope. Namely, we investigate the conditions under which the inequalities presented in the previous section define facets of kNCSP(G). In the following we assume that G is (k + 1)-node-connected. By Corollary 1, kNCSP(G) is then full-dimensional.

In [START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF], Grötschel et al. characterize when the trivial inequalities define facets.

Theorem 6 [START_REF] Grötschel | Integer polyhedra arising from certain network design problems with connectivity constraints[END_REF] 1) Inequality (2.1) defines a facet for kNCSP(G) if and only if e does not belong to a cut δ G\Z (W ) for some Z ⊂ V containing exactly k + 1 -|Z| edges.

2) Inequalities (2.2) define facets for kNCSP(G) for every e ∈ E.

The next theorem deals with conditions for the cut inequalities to define facets. Before, we give the following remark that will be helpful for proving the results below.

Remark 2.1 Let W and W be a partition of G such that |W | ≥ k, |W | ≥ k + 1 and G[W ] and G[W ] are both k-node-connected. Let {e 1 , ..., e k } be edges of δ G (W ) forming a matching of G. Let S = E(W ) ∪ E(W ) ∪ {e 1 , ..., e k }. Then S is a solution of kNCSP(G). Theorem 7 The cut inequality (2.3), induced by a node set W ⊂ V , defines a facet for kNCSP(G) if the following hold. i) G[W ] and G[W ] are (k + 1)-node-connected.
ii) A maximum cardinality matching M in δ G (W ) contains at least k + 1 edges.

Proof.

Let us denote by ax ≥ α the cut inequality induced by W , and let F = {x ∈ kNCSP (G) | ax = α}. Suppose there exists a defining facet inequality bx ≥ β such that F ⊆ F = {x ∈ kNCSP (G) | bx = β}. We will prove that there is a scalar ρ such that b = ρa. By ii) there exists a matching M = {e 1 , ..., e p }, p

≥ k + 1, in δ G (W ) of p edges such that e i = u i v i , i = 1, ..., p, with u i ∈ W and v i ∈ W . Let U 1 = {u 1 , ..., u p } and V 1 = {v 1 , ..., v p }. Let T 1 = E(W ) ∪ E(W ) ∪ {e 1 , ..., e k }. As by i) G[W ] and G[W ] are (k + 1)-node-connected, by Remark 2.1, T 1 is a solution of kNCSP(G). We will
show in what follows that the coefficients b e are equal for all e ∈ δ G (W ). First we show that b e i = b e j for i, j ∈ {1, ..., p}.

Let T 2 = (T 1 \ {e 1 }) ∪ {e k+1 }. Clearly T 2 is a solution of kNCSP. As x T 1 , x T 2 ∈ F , we have that bx T 1 = bx T 2 = β.
∈ δ(W ) \ M is adjacent to M. Consider an edge f = u i v ∈ [U 1 , W \ V 1 ], i ∈ {1, ..., p}. Let T 3 = (T 1 \ {e i }) ∪ {f }. As x T 1 , x T 3 ∈ F ⊂ F , we have that bx T 1 = bx T 3 = β. This yields b f = b e i = ρ. Thus b f = ρ for all f ∈ [U 1 , W \V 1 ]. By symmetry we also have b f = ρ for all f ∈ [V 1 , W \U 1 ].
Finally consider an edge h = u i v j , i, j ∈ {1, ..., p}, with i = j. W.l.o.g., we suppose i, j ≤ k. Consider the subset T 4 = (T 1 \{e i , e j }) ∪ {h, e k+1 }. We have that T 4 is a solution of kNCSP(G), and x

Corollary 2 If the graph G is complete, the cut inequality (2.3) induced by W ⊂ V is facet-defining for kNCSP(G) if |W | ≥ k + 2 and |W | ≥ k + 2.
The following theorems give necessary conditions and sufficient conditions for the node-cut inequalities to be facet-defining.

Theorem 8

The node-cut inequality (2.4), induced by a node-cut δ G\Z (W ) for some node sets W and Z, defines a facet for kNCSP(G)

only if |[W, Z]| ≥ |Z| + 1 and |[V \ (W ∪ Z), Z]| ≥ |Z| + 1. Proof. Suppose for instance that |[W, Z]| < |Z|+1, the case where |[V \(W ∪Z), Z]| < |Z| + 1 is similar. Thus, if |[W, Z]| < |Z| + 1, then for any solution x ∈ kNCSP(G) we have that -x([W, Z]) ≥ -|Z|, and x(δ G (W )) ≥ k. Hence we obtain that x(δ G\Z (W )) = x(δ G (W )) -x([W, Z]) ≥ k -|Z|. In consequence, x(δ G\Z (W )) ≥ k -|Z| is redundant
with respect to the cut and trivial inequalities, and hence cannot define a facet.

Theorem 9 The node-cut inequality (2.4) defines a facet for kNCSP(G) if the following hold

. i) G[W ] and G[W ] are (k + 1)-node-connected. ii) A maximum cardinality matching C in δ G (W ) contains at least k + 1 edges such that |C ∩ [Z, W ]| =
|Z| and there exists a node in W which is not incident to the matching C and it is adjacent to all the nodes of Z.

Proof. Let us denote by ax ≥ α the cut inequality induced by W , and let F = {x ∈ kNCSP (G) | ax = α}. Suppose there exists a defining facet inequality bx ≥ β such that F ⊆ F = {x ∈ kNCSP (G) | bx = β}. We will prove that there is a scalar ρ such that b = ρa. By ii) there exists a matching C = {e 1 , ..., e p }, p

≥ k + 1, in δ G (W ), such that e i = u i v i , i = 1, ..., p, u i ∈ W and v i ∈ W , and e k-t+j ∈ [W, Z], j = 1, ..., t, with |Z| = t. Let U 1 = {u 1 , ..., u p } and V 1 = {v 1 , ..., v p }. And let T 1 = E(W ) ∪ E(W ) ∪ {e 1 , ..., e k } ∪ [W, Z]. As by i) G[W ] and G[W ] are (k + 1)- node-connected, by Remark 2.1, T 1 is a solution of kNCSP(G). Hence x T 1 ∈ F . Let T 2 = (T 1 \ {e 1 }) ∪ {e k+1 } (Recall that p ≥ k + 1). Clearly, T 2 is a solution of kNCSP. As x T 1 , x T 2 ∈ F , we have that bx T 1 = bx T 2 = β, implying that b e 1 = b e k+1 = ρ for some ρ ∈ R. By symmetry, we obtain that b e i = ρ for all e i ∈ C\[W, Z]. As C has a maximum cardinality, any edge e ∈ δ G\Z (W ) \ C is adjacent to C. Consider an edge f = u i v ∈ [U 1 , V \ (W ∪ Z ∪ V 1 )]. W.l.o.g., we suppose i ∈ {1, ..., k -t}. Let T 3 = (T 1 \{e i }) ∪ {f }. Set T 3 is a solution of kNCSP(G). Moreover x T 3 ∈ F ⊆ F . Hence bx T 1 = bx T 3 = β, implying that b f = b e i = ρ. Thus b f = ρ for all f ∈ [U 1 , V \ (W ∪ Z ∪ V 1 )]. By symmetry, we also have that b f = ρ, for all f ∈ [V 1 \ Z, W \ U 1 ]. Now let h = u i v j , i = j, i, j ∈ {1, ..., p} \ {k -t + 1, ..., k}. Consider T 4 = (T 1 \{e i , e j }) ∪ {h, e k+1 }. Set T 4 is a solution of kNCSP(G). Moreover x T 4 ∈ F ⊆ F . Hence b e i + b e j = b h + b e k+1 .
As b e i = b e j = b e k+1 = ρ, this implies that b h = ρ. Therefore we obtain that b e = ρ for all e ∈ δ G\Z (W ). Now consider an edge e ∈ E(W ), and let

T 5 = T 1 \{e}. As G[W ] is (k + 1)-node-connected, G[W ]\{e} is k-node-connected,

Theorem 10 Let G = (V, E) be a graph and an integer

k ≥ 2. Let Z ⊂ V . Let Z i ⊂ Z, with |Z i | ≤ k -2, for i = 1, ..., p, and π = (V 0 , V 1 , ..., V p ) be a partition of V \Z
where p is odd. Suppose that the following hold.

Z edges of δ G\Z (π) \ F V 0 V 1 V 3 V 4 V 5 V 2 edges of δ(Z) edges of F Figure 2.2: A F -node-partition configuration with k = 4 i) G[Z] is a complete graph. ii) G[V i ] is (k + 1)-node-connected, for i = 0, 1, ..., p. iii) For i = 1, ..., p, there exists a subset S i of k + 1 edges of δ(V i ) such that 1) |S i ∩ [Z i , V i ]| = |Z i | and covering all the nodes of Z i , 2) |S i ∩ [V 0 , V i ]| = k -|Z i | -1 and covering k -|Z i | -1 nodes of V 0 , 3) |S i ∩ [V i , V i-1 ]| = |S i ∩ [V i , V i+1 ]| = 1,
where the indices are taken modulo p. (see figure 2.2 for an illustration for k = 4)

Moreover, if |V i | ≥ 2, S i must cover at least k + 1 nodes of V i . iv) [Z, V 0 ] contains a set of k + 1 edges covering k + 1 nodes of V 0 and min(|Z|, k + 1) nodes of Z. v) For i = 1, ..., p, [V 0 , V i ∪ V i+1 ] contains a set R i ⊆ S i ∪ S i+1 of k -|Z i | + 1 edges covering k -|Z i | + 1 nodes of V 0 . Let F i = S i ∩ [V 0 , V i ], for i = 1, ...,

Proof.

Remark that under these conditions we can easily see that G is (k + 1)-nodeconnected, thus kNCSP(G) is full dimensional. Let us denote the F -node-partition inequality by ax ≥ α and let F = {x ∈ kNCSP (G) | ax = α}. Clearly, F is a proper face of kNCSP(G). Now suppose that there exists a facet defining inequality bx ≥ β of kNCSP(G) such that F ⊆ F ′ = {x ∈ kNCSP (G) | bx = β}. We will show that b = ρa for some scalar ρ ∈ R. For this, first remark that the right hand side of the inequality (2.12) here is p 2 . Let E 0 be the set of edges in E\F having both endnodes in the same element of π.

Let Γ = E 0 ∪ F ∪ E(Z) ∪ δ(Z).
Let e l be an edge of S l ∩ [V l , V l+1 ], l = 1, ..., p. For l ∈ {1, ..., p} consider the edge set

T l = Γ ∪ {e l+2r , r = 0, ..., p -1 2 },
where the indices are taken modulo p. Observe that x T l (δ G\Z (π) \ F ) = p+1 2 . Moreover, we have the following.

Claim 1 T l induces a k-node-connected subgraph of G.
Proof. Let G l be the subgraph of G induced by T l . First, we give the following remarks.

a) |δ G l (V j )| = k for j ∈ {1, ..., p}\{l} and |δ G l (V l )| = k + 1. b) F i = ∅ since |Z i | ≤ k -2,
for i ∈ {1, ..., p}, and the graph obtained from G l by removing subsets from

{Z, V 1 , ..., V p } is connected, c) The graph G * l obtained from G l by contracting the sets V 0 , V 1 , .
.., V p , Z, and replacing the multiple edges by a single edge, and deleting the edges between V i and V j , i = j, i, j = 1, ..., p, is connected.

Let Z ′ ⊂ V with |Z ′ | = k -1. We will show that the graph G l \Z ′ is connected. Case 1. Z ′ ⊂ Z or Z ′ ⊂ V i , for some i ∈ {1, ..., p}. Suppose that Z ′ ⊂ Z. If |Z| = |Z ′ | = k -1, then by the Remark b) above, G l \Z ′ is connected. So suppose |Z| ≥ k. As |Z ′ | = k -1 and G[Z]
is complete, the subgraph induced by Z\Z ′ is connected. Moreover, by Condition iv), there exists at least one edge connecting

Z\Z ′ to V 0 . Since G l \Z is connected, we obtain that G l \Z ′ is also connected. Now suppose Z ′ ⊂ V i for some i ∈ {1, ..., p}. As G[V i ] is (k + 1)-node-connected and |Z ′ | = k -1, G[V i \ Z ′ ]
is connected. Therefore, using Condition iii), the proof can be done along the same line.

Case 2. Z ′ ⊂ V 0 . As |Z ′ | = k-1, by Condition iv), it follows that [Z, V 0 \Z ′ ] G l = ∅. We distinguish two cases. Suppose first that for every s ∈ {1, ..., p} such that [V s , V s+1 ] G l = ∅, at least one of the sets V s and V s+1 is adjacent to Z in G l . Then the graph obtained from G l by removing V 0 is connected. Moreover, since G[V 0 ] is (k + 1)-node-connected, we have that G[V 0 \Z ′ ] is connected. Therefore G l \Z ′ is connected. If this is not the case, then there is s ∈ {1, ..., p} such that [V s , Z] G l = ∅ = [V s+1 , Z] G l and [V s , V s+1 ] G l = ∅. We then have Z s = Z s+1 = ∅. Moreover, by Condition v), it follows that there is a set of k + 1 edges between V 0 and V s ∪ V s+1 that cover k + 1 nodes of V 0 . As |Z ′ | = k -1, at least one edge remains linking V 0 \Z ′ to V s ∪ V s+1 . Thus for j = 1, ..., p, if [V j , V j+1 ] G l = ∅, then at least one of the sets [V 0 \Z ′ , V j ∪ V j+1 ] G l and [Z, V j ∪ V j+1 ] G l is not empty. As G[V 0 ] is (k + 1)-node-connected and |Z ′ | = k -1, G[V 0 \Z ′ ] is connected, and hence G l \Z ′ is connected. Case 3. Z ′ ⊆ i∈I V i , where I ⊂ {1, ..., p}. Note that |I| ≤ k -1. Let I ′ = {i ∈ I | |V i | = 1}. First note that, by Remark b) above, the graph G l \ i∈I V i is connected.
Also note that as |Z ′ | = k -1, and Z ′ is not contained in a single set, we have

|Z ′ ∩ V i | ≤ k -2 for i ∈ I\I ′ . Since G[V i ] is (k + 1)-node-connected, it follows that G[V i \Z ′ ] is connected for i ∈ I\I ′ . Also by construction, we have |[V i , V 0 ∪Z] G l | ≥ k -1 for i ∈ I\I ′ . Moreover by Condition iii), [V i , V 0 ∪ Z] G l covers at least k -1 different nodes in V i , for i ∈ I\I ′ . So, if no more than k -2 nodes are removed from V i , at least one edge remains connecting V i \Z ′ to Z ∪V 0 for i ∈ I\I ′ . Therefore G l \Z ′ is connected. Case 4. Z ′ ⊂ V 0 ∪Z ∪( i∈I V i ) where I ⊆ {1, ..., p}. Let I ′ = {i ∈ I | |V i | = 1}. Suppose first that Z ′ ∩ Z = ∅, Z ′ ∩ V 0 = ∅ and Z ′ ∩ i∈I V i = ∅. We have that |Z ′ ∩ Z| ≤ k -2 and |Z ′ ∩ V 0 | ≤ k -2. By Condition v), |[V i ∪ V i+1 , V 0 ] G l | ≥ k -|Z i | + 1 and covers k -|Z i | + 1 nodes of V 0 .
Then there exists at least one edge linking V 0 \Z ′ and

V i ∪ V i+1 . Thereby G l [(V 0 \Z ′ ) ∪ ( p i=1 V i )] is connected, which is equal to G l \Z. Now suppose Z\Z ′ = ∅. Since G[V 0 ] is (k+1)-node-connected and G[Z] is a complete graph, it follows that G[V 0 \Z ′ ] and G[Z\Z ′ ] are connected. By Condition iv), [Z\Z ′ , V 0 \Z ′ ] G l = ∅.
Moreover, by construction, at least one edge remains connecting V i to V i+1 ∪ V i-1 . And we can show along the same way as in Case 2, that

V i is connected to V 0 \Z ′ . Thus The k-node-connected subgraph problem G l \Z ′ is connected. Now suppose that Z ′ ∩ Z = ∅, Z ′ ∩ V i = ∅, for i ∈ I, I ⊆ {1, ..., p}, and Z ′ ∩ V 0 = ∅. If Z ⊂ Z ′ , the proof is similar to the previous case. Suppose that Z\Z ′ = ∅. We have that |Z ′ ∩ Z| ≤ k -|I| -1. Let I ′ = {i ∈ I | V i ∩ Z ′ = ∅ and |V i | = 1}. Since G[V i ], for i ∈ I\I ′ , is (k + 1)-node-connected and G[Z] is complete, it follows that G[Z\Z ′ ],
and G[V i \Z ′ ], for i ∈ I\I ′ , are connected. By Condition iv) there exists at least one edge connecting

Z\Z ′ to V 0 . Also by Condition iii), [V i , V 0 ∪ Z] G l contains k -1 edges covering different nodes in V 0 ∪ Z and covers k -1 nodes in V i . So if no more than k -2 nodes are removed from V i ∪ V 0 ∪ Z, at least one edge remains connecting V i \Z ′ to (Z\Z ′ ) ∪ V 0 . Thus G l \Z ′ is connected. Now, if Z ′ ∩ V 0 = ∅ and Z ′ ∩ V i = ∅, for i ∈ I, and Z ′ ∩ Z = ∅, then we have that |Z ′ ∩V 0 | ≤ k -|I|-1 and |Z ′ ∩V i | ≤ k -|I|-1 for i ∈ I. Since G[V i ], for i ∈ {0}∪(I\I ′ ), is (k + 1)-node-connected, it follows that G[V i \Z ′ ] is connected, for i ∈ {0} ∪ (I\I ′ ). By Condition iv) we have that [V 0 \Z ′ , Z] = ∅. Moreover by Condition iii), [V i , V 0 ∪ Z] contains k -1 edges that covers k -1 nodes in V 0 ∪ Z and k -1 nodes in V i . So if no more than k -2 nodes are removed from V i ∪ V 0 at least an edge remains connecting V i \Z ′ to Z ∪ (V 0 \Z ′ ). Thus G l \Z ′ is connected. Suppose now that Z ′ ∩ Z = ∅, Z ′ ∩ V 0 = ∅ and Z ′ ∩ ( i∈I V i ) = ∅. We have that |Z ′ ∩ Z| ≤ k -|I| -2 and |Z ′ ∩ V i | ≤ k -|I| -2 for i ∈ I. Since G[V i ], for i ∈ {0} ∪ I\I ′ , is (k + 1)-node-connected and G[Z] is complete, it follows that G[Z\Z ′ ] and G[V i \Z ′ ]
are connected, for i ∈ {0} ∪ I\I ′ . By Condition iv), there exists at least one edge connecting Z\Z ′ to V 0 . Also by Condition iii), there are

|[V i , V 0 ∪ Z] G l | ≥ k -1 edges covering different nodes in V i , V 0 and Z. So if no more than k -4 nodes are removed from V i ∪ V 0 ∪ Z, then at least an edge remains connecting V i \Z ′ to (Z\Z ′ ) ∪ (V 0 \Z ′ ). Thus G l \Z ′ is connected. Consequently G l = (V, T l ) is k-node-connected. Thus x T l ∈ F .
[V 1 , V 2 ] and [V p , V 1 ], respectively, we obtain b(e) = ρ for all e ∈ [V i , V i+1 ], i = 1, ..., p, for some ρ ∈ R.
Let g l+1 be a fixed edge of [V l+1 , V 0 ]\F , for l ∈ {0, ..., p -1}. Consider the edge set Tl = (T l \{e l }) ∪ {g l+1 }.

Similary, we can show that Tl induces a k-node-connected subgraph of G. As x T l and x Tl belong to F , it follows in a similar way that b(e l ) = b(g l+1 ). As b(e l ) = b(e l+1 ) = ρ, this yields b(g l+1 ) = ρ. By exchanging the roles of V l+1 and V l , l = 1, ..., p, we obtain that b(e) = ρ for all e ∈ δ G (V 0 )\F . In consequence, the b(e), for all e ∈ E\Γ have the same value ρ.

Next, we will show that b(e) = 0 for all e ∈ Γ.

Note that there are k + 1 edges incident to V l in the graph induced by T l . By using Condition iii) we can show in a similar way as in the claim above that for any edge e ∈ F l , l ∈ {0, ..., p}, T * l = T l \{e} also induces a k-node-connected subgraph of G. As x T l and x T * l belong to F , it follows that bx T l = bx T * l = β, implying that b(e) = 0 for all e ∈ F l . As l is arbitrarily chosen, we obtain that b(e) = 0 for all f ∈ F . Moreover, as the subgraphs induced by V 0 , ..., V p are all (k + 1)-node-connected, the subgraph induced by T l \{e}, for all e ∈ E 0 , is k-node-connected. This yields as before b(e) = 0 for all e ∈ E 0 . Now suppose that e ∈ E(Z). By Conditions i) and iv) we can clearly see that T l \{e} also induces a k-node-connected subgraph of G. Implying that b(e) = 0.

Let h be an edge of δ(Z). We can show in a similar way as in the claim above that

T l = T l \{h} also induces a k-node-connected subgraph of G. As x T l belongs to F , it follows that b(h) = 0. Consequently b(e) = 0 for all e ∈ Γ.
Thus we obtain that b = ρa, which ends the proof of the theorem.

Corollary 4 If the graph G is complete, then the F -node-partition inequalities (5) are facet-defining for kNCSP(G) if |V i | ≥ k + 2, i = 0, 1, ..., p. Corollary 5 Suppose that |V i | = 1, for i = 1, ..., p, |[V 0 , V i ]| = k -|Z i | -1, |[V i , Z i ]| = |Z i |, V 1 , ..., V p induce an odd cycle C, and G[V 0 ] is (k +1)-node-connected and G[V 0 ∪Z] is complete. Then the inequality x(C) ≥ p 2 is valid for kNCSP(G)
, and defines a facet.

The k-node-connected subgraph problem

Z edges of δ G\Z (π) edges of δ(Z) v 1 v 2 v 3 v 4
≥ 2. Let Z ⊂ V , such that |Z| ≤ k -1 and k -|Z| is odd. Let π = (V 1 , ..., V p ) be a partition of V \Z such that (G \ Z) π is series-parallel.
The SP-node-partition inequality (2.10) associated with π defines a facet of kNCSP(G) if the following conditions hold.

i) p ≥ k + 1. ii) G[V i ] is (k + 1)-node-connected, for i = 1, ..., p. iii) G[Z] is complete. iv) For i = 1, ..., p, there exists a subset S i ⊂ δ(V i ), with |S i | = k + 1, S i is a matching and such that a) |S i ∩ [Z, V i ]| = |Z|, b) |S i ∩ [V i , V i-1 ]| = |S i ∩ [V i , V i+1 ]| = k -|Z| 2 ,
where the indices are taken modulo p.

Proof.

Let us denote the SP-node-partition inequality by ax ≥ α and let

F = {x ∈ kNCSP (G) | ax = α}.
Clearly, F is a proper face of kNCSP(G). Now suppose that there exists a facet defining inequality bx ≥ β of kNCSP(G) such that

F ⊆ F ′ = {x ∈ kNCSP (G) | bx = β}.
We will show that b = ρa for some scalar ρ ∈ R.

Let E 0 = p i=1 E(V i ).
And let F i be the edge set

S i ∩ [V i , V i+1 ] for i = 1, ..., p. Note that |F i | = k-|Z|+1 2 . Consider T 1 = ( p i=1 F i ) ∪ E 0 ∪ E(Z) ∪ δ(Z). Claim 2 The graph H induced by T 1 is (k + 1)-node-connected. Proof. Since G[V i ] is (k + 1)-node-connected, and hence |V i | ≥ k + 2, and |Z ′ | = k, we have that V i \Z ′ = ∅ and G[V i \Z ′ ] is connected for i = 1, ..., p. Suppose, on the contrary, that H \ Z ′ is not connected. Then there is W ⊂ V \ Z ′ such that δ H\Z ′ (W ) = ∅. As G[V i \Z ′ ] = H[V i \Z ′ ] is connected, it follows that either W ∩(V i \Z ′ ) = ∅ or V i \Z ′ ⊆ W . Also as G[Z] is complete, we have that either W ∩ (Z \ Z ′ ) = ∅ or Z \ Z ′ ⊆ W .
We will distinguish two cases.

Case 1. Z ⊂ Z ′ . Remark that any cut in H \ Z not intersecting E 0 contains a matching of k -|Z| + 1 edges. Hence H \ Z cannot be disconnected by removing k -|Z| nodes. Which contradicts the fact that δ H\Z ′ (W ) = ∅.

Case 2. Z \ Z ′ = ∅. Thus [Z \ Z ′ , V i ] = ∅, for i = 1, ..., p. This implies that δ H\Z ′ (W ) = ∅. Thus w.l.o.g. we may suppose W ∩ (Z \ Z ′ ) = ∅. Here, we can show along the same line as in Case 1 that H \ Z ′ cannot be disconnected. Which ends the proof.

As H is a subgraph of G, G is (k + 1)-node-connected, thus kNCSP(G) is full dimensional.

Clearly, the graph induced by T j = T 1 \ f j for some f j ∈ F j , j ∈ {1, ..., p}, is k-node-connected. Moreover x T j belongs to F . Similary, we can see that T j+1 = (F j \ {f j+1 }) ∪ {f j }, with f j+1 ∈ F j+1 , also induces a k-node-connected subgraph of G. As x T j and x T j+1 belong to F , we have that b(x T j ) = b(x T j+1 ) and hence b(f j ) = b(f j+1 ). As f j and f j+1 are arbitrary edges of F j and F j+1 , respectively, it follows that b(e) = b(e ′ ) for all e ∈ F j and e ′ ∈ F j+1 . Moreover, as F j and F j+1 are arbitrary subsets of [V j , V j+1 ] and [V j+1 , V j+2 ], respectively, we obtain that b(e) = b(e ′ ) for all e ∈ [V j , V j+1 ] and e ′ ∈ [V j+1 , V j+2 ], j = 1, ..., p. Consequently, by symmetry, we get b(e) = b(e ′ ) for all e, e ′ ∈ p i=1

[V i , V i+1 ]. Now let h ∈ [V i 0 , V j 0 ], i 0 , j 0 ∈ {1, ..., p} with |i 0 -j 0 | > 1.
Consider the edge sets T 2 = (T j \ {f i 0 -1 }) ∪ {h} and T 3 = (T 2 \ {h}) ∪ {f i 0 }. Similary, we can show that T 2 and T 3 induce k-node-connected subgraphs of G. As x T 2 and x T 3 belong to F , it follows that b(x T 2 ) = b(x T 3 ) and hence b(h) = b(f i 0 ). This yields b(e) = b(e ′ ) for all e, e ′ ∈ δ G\Z (π). Now, we will show that b(e) = 0 for all e ∈ E 0 ∪ E(Z) ∪ δ(Z). Consider the edge set T 4 = T j \ {e} for some e ∈ E 0 . As G[V i ] is (k + 1)-node-connected, for i = 1, ..., p, T 4 induces a k-node-connected subgraph of G. As x T j and x T 4 belong to F , we have that b(x T j ) = b(x T 4 ), and thus b(e) = 0 for all e ∈ E 0 . Now suppose that e ∈ E(Z). By Condition i) and iii) we can clearly see that T j \ {e} also induces a k-node-connected subgraph of G. Implying that b(e) = 0. Let g be an edge of δ(Z). We can show in a similar way that T 5 = T j \ {g} also induces a k-node-connected subgraph of G. As x T 5 belongs to F , it follows that b(e) = 0 for all g ∈ δ(Z). Thus b(e) = 0 for all e ∈ E 0 ∪ E(Z) ∪ δ(Z). Therefore we obtain that b = ρa and the proof is complete.

Corollary 6 If the graph G is complete, then the SP-node-partition inequalities (2.10) are facet-defining for kNCSP(G) if p ≥ k + 1 and |V i | ≥ k + 2, i = 1, ..., p.

Structural properties

In this section, we discuss some structural properties of the extreme points of the linear relaxation P (G, k) of the kNCSP polytope. Recall that P (G, k) is the polytope given by inequalities (2.1)-(2.4).

For this, we first give some notations and definitions. Let x ∈ P (G, k) be a solution. We say that an inequality ax ≥ α is tight for x if ax = α. We will denote by E 0 (x), E 1 (x) and E f (x), the following edge sets

• E 0 (x) = {e ∈ E | x(e) = 0}, • E 1 (x) = {e ∈ E | x(e) = 1}, • E f (x) = {e ∈ E | 0 < x(e) < 1}.
Also we let C P E (x) (resp. C P N (x)) be the set of cuts δ(W ) (resp. node-cuts δ G\Z (W )) that are tight for x. If x is an extreme point of P (G, k), then x is the unique solution of the linear system

S(x)           
x(e) = 0, for all e ∈ E 0 (x), x(e) = 1, for all e ∈ E 1 (x),

x(δ G (W )) = k, for all cuts δ G (W ) ∈ C * P E (x), x(δ G\Z (W )) = k -|Z|, for all node-cuts δ G\Z (W ) ∈ C * P N (x),
where

C * P E (x) (resp. C * P N (x)) is a subset of C P E (x) (resp. C P N (x)).
Lemma 1 Let x ∈ P (G, k) and W ⊆ V such that the cut induced by W is tight for x.

1) If for some R ⊂ V , x(δ(R)) = k, then x(δ(W ∩ R)) = k and x(δ(W ∪ R)) = k. 2) If for some Z ⊂ V such that |Z| ≤ k -1, and T ⊂ V \ Z, x(δ G\Z (T )) = k -|Z|, then x(δ G\(Z∩W ) (W ∩ T )) = k -|Z ∩ W | and x(δ G\(Z∩W ) (W ∪ T )) = k -|Z ∩ W |.
Proof.

1) The proof is similar to that of [START_REF] Cornuéjols | The traveling salesman problem on a graph and some related integer polyhedra[END_REF].

2) Suppose that

Z ∩ W = ∅ = Z ∩ W . Also suppose that T ∩ W = ∅ and T ⊂ W , W ⊂ T and T ∪ W = V \ Z.
If this is not the case, then we are done. Let

T 1 = T ∩ W , T 2 = T ∩ W , Z 1 = Z ∩ W , Z 2 = Z ∩ W , T 3 = W \ (T ∪ Z 1 ) and T 4 = W \ (T ∪ Z 2 ). Thus T i = ∅ for i = 1, ..., 4. As δ(W ) ∈ C P E(x), we have that k = x(δ(W )) = x(δ(T 1 , T 2 )) + x(δ(T 1 , T 4 )) + x(δ(T 3 , T 2 )) +x(δ(T 3 , T 4 )) + x(δ(T 1 , Z 2 )) + x(δ(T 3 , Z 2 )) +x(δ(T 2 , Z 1 )) + x(δ(T 4 , Z 1 )) + x(δ(Z 1 , Z 2 )).
(2.13)

And as δ G\Z (T ) ∈ C n (x), we have that

k -|Z| = x(δ G\Z (T )) = x(δ(T 1 , T 3 )) + x(δ(T 1 , T 4 )) +x(δ(T 2 , T 3 )) + x(δ(T 2 , T 4 )).
(2.14)

By considering the node-cuts δ G\Z 1 (T 1 ), δ G\Z 2 (T 2 ), δ G\Z 1 (T 3 ) and δ G\Z 2 (T 4 ), we have that

k -|Z 1 | ≤ x(δ G\Z 1 (T 1 )) = x(δ(T 1 , T 2 )) +x(δ(T 1 , T 3 )) + x(δ(T 1 , T 4 )) + x(δ(T 1 , Z 2 )), (2.15) k -|Z 2 | ≤ x(δ G\Z 2 (T 2 )) = x(δ(T 2 , T 1 )) + x(δ(T 2 , T 3 )) +x(δ(T 2 , T 4 )) + x(δ(T 2 , Z 1 )), (2.16
)

k -|Z 1 | ≤ x(δ G\Z 1 (T 3 )) = x(δ(T 3 , T 1 )) +x(δ(T 3 , T 2 )) + x(δ(T 3 , T 4 )) + x(δ(T 3 , Z 2 )), (2.17) k -|Z 2 | ≤ x(δ G\Z 2 (T 4 )) = x(δ(T 4 , T 1 )) + x(δ(T 4 , T 2 )) +x(δ(T 4 , T 3 )) + x(δ(T 4 , Z 1 )).
(2.18)

As x(e) ≥ 0 for all e ∈ E, by adding (2.13), (2.14) (2.17 From Lemma 1, we can show the following result. Its proof is omitted since it follows the same lines as a similar result in [START_REF] Cornuéjols | The traveling salesman problem on a graph and some related integer polyhedra[END_REF].

Lemma 2 Let x be an extreme point of P (G, k), and W ⊂ V such that x(δ(W )) = k. Then the system S(x) can be chosen so that

1) a cut δ(R) ∈ C * P E (x) is such that R ⊂ W or R ⊂ W ; 2) a node-cut δ G\Z (T ) ∈ C * P N (x) is such that (T ∪ Z) ⊂ W , (T ∪ Z) ⊂ W , T ⊂ W and Z ⊂ W , or T ⊂ W and Z ⊂ W .

Reduction operations

In this section we introduce some reduction operations defined with respect to a solution x of P (G, k). These operations will be considered in a preprocessing phase for separating violated inequalities in our Branch-and-Cut algorithm. Let θ 1 , θ 2 , θ 3 and θ 4 be the reduction operations defined as follows.

θ 1 : Delete an edge e ∈ E such that x(e) = 0. We have the following results.

θ 2 : Contract a node subset W ⊆ V such that G[W ] is k-edge connected, x(e) = 1 for all e ∈ E(W ) and x(δ(W )) = k. θ 3 : Contract a node subset W ⊆ V such that |W | ≥ k, |W | ≥ k, x(e) = 1
Lemma 3 Let G ′ = (V, E ′ ) be the graph obtained from G by the application of Operation θ 1 and let x ′ be the restriction of x to G ′ . Then x ′ is an extreme point of P (G ′ , k) if and only if x is an extreme point of P (G, k).

Proof. Easy.

Lemma 4 Let G ′ = (V ′ , E ′ ) and x ′ be the graph and the solution obtained from G and x by the application of Operation θ 2 . Suppose that

1) x ′ ∈ P (G ′ , k), 2) for all Z ⊂ W , |Z| ≤ k -1, δ G\Z (T ) / ∈ C P N (x) for all T ⊆ W . Then x ′ is an extreme point of P (G ′ , k) if x is an extreme point of P (G, k).
Proof. Let W be a node set of G contracted by Operation θ 2 . As δ(W ) ∈ C P E (x), by Lemma 2, the system S(x) can be chosen in such a way that for every δ(R)

∈ C * P E (x) (resp. δ G\Z T (T ) ∈ C * P N (x)) either R ⊆ W or R ⊆ W (resp. (T ∪ Z T ) ⊂ W , T ⊂ W and Z T ⊂ W , or T ⊂ W and Z T ⊂ W ). As x(e) = 1 for all e ∈ E(W ) and G[W ] is k-edge connected, this implies that C * P E (x) ⊆ C P E (x ′ ). Moreover by 2) it follows that if δ G\Z T (T ) is tight for x and Z T ⊆ W , then W ∩ T = ∅ and W \ (Z T ∪ T ) = ∅. Let T 1 = W ∩ T and T 2 = W \ (Z T ∪ T ). We have that k -|Z T | = x(δ G\Z T (T )) ≥ x(δ(T 1 , T 2 )) ≥ k, a contradiction.
The last inequality comes from the fact that G[W ] is k-edge connected and x(e) = 1 for all e ∈ E(W ). In consequence, all the node-cuts

δ G\Z T (T ) of C * P N (x) are such that Z T ⊂ W .
However these are at the same time tight for x ′ . Thus C * P N (x) ⊂ C P N (x ′ ). Let S ′ (x) be the system obtained from S(x) by deleting the equations x(e) = 1 for all e ∈ E(W ). Then x ′ is the unique solution of S ′ (x). As all the equations of S ′ (x) come from P (G ′ , k) and by 1)

x ′ ∈ P (G ′ , k), it follows that x ′ is an extreme point of P (G ′ , k). Lemma 5 Let G ′ = (V ′ , E ′
) and x ′ be the graph and the solution obtained from G and x, respectively, by the application of Operation θ 3 . Then x ′ is an extreme point of P (G ′ , k).

Proof. Let W ⊆ V be a node set satisfying the conditions of Operation θ 3 . First observe that as |δ(W )| = k, we have that x(e) = 1 for all e ∈ δ(W ) and x(δ(W )) = k. Thus, by Lemma 2, S(x) can be chosen so that for every node-cut δ G\Z (T ) ∈ C * P N , we have (T ∪ Z) ⊂ W , (T ∪ Z) ⊂ W , T ⊂ W and Z ∈ W , or T ⊂ W and Z ∈ W . We will show that any cut δ(R) ∈ C * P E (x) is such that R ⊂ W , and any node-cut δ G\Z (T ) ∈ C * P N (x) is such that (T ∪ Z) ⊂ W . Suppose the contrary and consider first that for some δ(R) ∈ C * P E (x), R W . As x(e) = 1, for all e ∈ E(W ) ∪ δ(W ), one can see that |δ(R)| = k, and hence x(δ(R)) = k can be obtained from x(e) = 1, for all e ∈ δ(R), contradicting the fact that δ(R) ∈ C * P E (x). Now suppose that for some node-cut δ G\Z (T ) ∈ C * P N (x) either (T ∪ Z) ⊂ W or T ⊆ W and Z ⊆ W . We can show similarily to the previous case that |δ G\Z (T )| = k -|Z| and that x(δ G\Z (T )) = k -|Z| can be obtained from x(e) = 1, for all e ∈ δ G\Z (T ), which yields a contradiction.

We consider now a node-cut δ G\Z (T )

∈ C * P N (x) such that T ⊆ W and Z ⊆ W . Notice that, as |W | ≥ k, we have that W \ Z = ∅. If T = W , then x(δ G\Z (T )) = x(δ(W \ Z, T )) = |δ(W \ Z, T )| = k -|Z|. Thus, x(δ G\Z (T )) = k -|Z|
can be obtained from the equations x(e) = 1, for all e ∈ δ G\Z (T ), contradicting the fact that δ G\Z (T ) ∈ C * P N (x). Thus, W \ T = ∅. For convenience, we let

T 1 = W \ Z and T 2 = W \ T . First, note that x(δ G\Z (T )) = x(δ(T, T 1 )) + x(δ(T, T 2 )) = k -|Z|.
(2.19)

Equation 2.19 together with the cut inequality induced by T yields

x(δ(T, Z)) ≥ |Z|.

(2.20) Also, as by the assumption |δ(W )| = k, we have that

x(δ(T, T 1 )) + x(δ(T, Z)) + x(δ(T 2 , T 1 )) + x(δ(T 2 , Z)) = k. (2.21)
This equation, together with the node-cut inequality induced by δ G\Z (T 2 ) implies that

x(δ(T, Z)) + x(δ(T 2 , Z)) ≤ |Z|. (2.22)
Thus, by inequalities (2.20) and (2.22), we have that x(δ(T, Z)) = |Z| and x(δ(T 2 , Z)) = 0, and hence

x(δ(T )) = x(δ(T, T 1 )) + x(δ(T, Z)) + x(δ(T, T 2 )) = k.
(2.23)

Moreover, as x(e) = 1, for all e ∈ δ(W ), we have that x(δ(T, Z)) = |Z| = |δ(T, Z)|. Therefore, x(δ G\Z (T )) = k -|Z| can be obtained from (2.23) and the x(e) = 1, for all e ∈ δ(T, Z), and hence, can be replaced in S(x) by equation (2.23). Consequently, the system S(x) can be chosen so that R ⊆ W for every cut δ(R) ∈ C * P E (x) and T ∪ Z ⊆ W for every node-cut δ G\Z (T ) ∈ C * P N (x). This also implies that

C * P E (x)∪C * P N (x) ⊆ C * P E (x ′ )∪C * P N (x ′
). Thus, x ′ is the unique solution of a subsystem of S(x). As all the equations of that subsystem correspond to constraints of P (G \ W, k), this implies that x ′ is an extreme point of P (G \ W, k).

Lemma 6

Let G ′ = (V ′ , E ′ ) be the graph obtained from G by the application of Operation θ 4 . Let E 0 be the set of parallel edges of G and e 0 the edge replacing E 0 in G ′ . Let x ′ be the solution given by x ′ (e) = x(e) if e ∈ E \ E 0 and x ′ (e) = 1 if e = e 0 . Then x ′ is an extreme point of P (G ′ , k).

Proof. Observe that for every cut

δ(W ) (node-cut δ G\Z (W )) either E 0 ⊆ δ(W ) (E 0 ⊂ δ G\Z (W )) or E 0 ∩ δ(W ) = ∅ (E 0 ∩ δ G\Z (W ) = ∅).
Moreover, E 0 cannot contain more than two edges with fractional value. Indeed, if e 1 , e 2 ∈ E 0 and 0 < x(e 1 ) < 1 and 0 < x(e 2 ) < 1, let x * be the solution given by x * (e) = x(e) if e ∈ E \ {e 1 , e 2 },

x * (e) = x(e)+ǫ if e = e 1 and x * (e) = x(e)-ǫ if e = e 2 , where ǫ is a positive scalar sufficiently small. We then have that x * is also a solution of S(x), which is a contradiction.

We claim that E 0 does not contain any edge with fractional value. Suppose, on the contrary that h is such an edge. Then x(E 0 ) > 1. Therefore there exists a cut or a node-cut of system S(x) containing h. Let v be an extremity of h. Let δ(S) be a cut of C * e (x) that contains h. Thus E 0 ⊂ δ(S). Suppose w.l.o.g., that v ∈ S. Consider the node-cut δ G\v (S). We have that x(δ G\v (S)) ≤ x(δ(S)\E 0 ) < k-1, a contradiction. Now consider a node-cut δ G\Z (T ) of C * n (x) that contains h and hence E 0 . As

x(E 0 ) > 1, one must have |Z| < k -1. So suppose that |Z| < k -1. Suppose w.l.o.g., that v ∈ V \ (T ∪ Z). Let Z ′ = Z ∪{v}. We have x(δ G\Z ′ (T )) ≤ x(δ G\Z (T ))-1-x(h) = k -(|Z|+1)-x(h) < k -|Z ′ |, a contradiction. Consequently, x(e) = 1
for all e ∈ E 0 . From the development above we also deduce that neither a cut of C * e (x) nor a node-cut of

C * n (x) intersects E 0 . Hence C * e (x) ∪ C * n (x) ⊂ C (x ′ )
. Moreover, we have that x ′ ∈ P (G ′ , k). Obviously, x ′ satisfies the trivial inequalities as well as the cut and node-cut inequalities that do not contain h. Let δ(W ) be a cut that contains h. Suppose v ∈ W . We have that

x ′ (δ(W )) = x ′ (h) + x ′ (δ(W ) \ {h}) = 1 + x(δ(W ) \ E 0 ) = 1 + x(δ G\v (W )) ≥ k. Consider now a node-cut δ G\Z (T ) containing h. If |Z| = k -1, as x ′ (h) = 1 and h ∈ δ G\Z (T ), we have that x ′ (δ G\Z (T )) ≥ 1. If |Z| < k -1, then let Z ′ = Z ∪ {v}. We have that x ′ (δ G\Z (T )) ≥ 1+x ′ (δ G\Z ′ (T )) ≥ 1+k -|Z ′ | = 1+k -|Z|-1 = k -|Z|.
As we will see later, the reduction operations θ 1 , ..., θ 4 can be used as a preprocessing for the separation procedures in our Branch-and-Cut algorithm.

Conclusion

We have studied in this chapter the k-node-connected subgraph problem with high connectivity requirement, that is, when k ≥ 3. We have investigated the dimension of the associated polytope, we have presented some classes of valid inequalities and described some conditions for these inequalities to be facet defining for the associated polytope. We have also investigated the structural properties of the extreme points of the linear relaxation of the problem and presented some reduction operations, which will be used as a preprocessing phase for the separation of the valid inequalities.

Branch-and-Cut algorithm

In this section, we present a Branch-and-Cut algorithm for the kNCSP. The algorithm is based on the theoretical results presented in the previous sections. We will first present the general framework of the algorithm, then we will address the main issues of our algorithm, that are the separation procedures for the various inequalities we will use, and a primal heuristic.

We will consider a graph G = (V, E) and a weight vector c ∈ R E associated with the edges of G. We let k ≥ 1 be the connectivity requirement.

General framework

To start the optimization we consider the following linear program consisting in the cut constraints induced by node sets {u}, for every u ∈ V together with the trivial inequalities, that is

min e∈E c(e)x(e) x(δ G (u)) ≥ k for all u ∈ V, 0 ≤ x(e) ≤ 1 for all e ∈ E.
If the optimal solution y ∈ R E of the above LP is feasible for the kNCSP, that is, it is integer and it satisfies all the cut and node-cut inequalities, then it is optimal for the problem. Usually, y is not feasible for the kNCSP. Thus, we need to generate further valid inequalities for the problem which are violated by y. This is done by addressing the separation problem associated with the cut and node-cut inequalities, respectively, and the other families of inequalities we consider in our algorithm. Recall that the separation problem associated with y and a family of inequalities F is to say if y satisfies or not all the inequalities of F, and if not, exhibit at least one inequality of F which is violated by y. An algorithm solving a separation problem is called a separation algorithm. In our algorithm, we use the inequalities that we described in the previous sections and perform their separation in the following order 1) cut inequalities, 2) node-cut inequalities, 3) SP-node-partition inequalities, 4) F -node-partition inequalities, 5) node-partition inequalities.

We move to a class of inequalities when the separation algorithm for the previous class of inequalities has not found any violated inequality. We may add several inequalities at the same time in the Branch-and-Cut algorithm. Moreover, all the inequalities are global, that is they are valid for all the nodes of the Branch-and-Cut tree.

Remark that the separations are done on the graph obtained after repeated applications of the reduction operations θ 1 , ..., θ 4 to the graph G and solution y. If G ′ is the reduced graph and y ′ is the restriction of y to G ′ , then by Lemmas 3-6, y ′ is an extreme point of P (G ′ , k) if y is an extreme point of P (G, k). Moreover, we have the following results which are easily seen to be true.

Lemma 7

Let a ′ x ≥ α be an F -node-partition inequality (respectively node-partition inequality) valid for kNCSP(G ′ ), induced by a partition

π ′ = (V ′ 0 , V ′ 1 , ..., V ′ p ), p ≥ 2 and an edge set F (respectively π ′ = (V ′ 1 , ..., V ′ p ), p ≥ 3) of V ′ \ Z, with Z ⊂ V . Let π = (V 0 , V 1 , ..., V p ), p ≥ 2 (respectively π = (V 1 , ..., V p ), p ≥ 3
) be the partition of V obtained by expanding the elements of π ′ . Let ax ≥ α be the inequality such that

a(e) =        a ′ (e) f or all e ∈ E ′ , 1 f or all e ∈ (E \ E ′ ) ∩ δ G (π), 0 otherwise.
Then ax ≥ α is valid for kNCSP(G). Moreover, if a ′ x ≥ α is violated by y ′ , then ax ≥ α is violated by y.

Lemma 8 Let a ′ x ≥ α be an SP-node-partition inequality valid for kNCSP(G ′ ), induced by a partition

π ′ = (V ′ 1 , ..., V ′ p ), p ≥ 3 of V ′ \Z, with Z ⊂ V such that |Z| ≤ k -1. Let π = (V 1 , ..., V p ), p ≥ 3 be the partition of V \ Z obtained by expanding the subsets V ′ i of π ′ .
Let ax ≥ α be the lifted SP-node-partition inequality obtained from a ′ x ≥ α by application of the lifting procedure described in Section 2.2 for the edges of E \ E ′ . Then ax ≥ α is violated by y, if a ′ x ≥ α is violated by y ′ .

Lemmas 7 and 8 show that the separation of F -node-partition, SP-node-partition and node-partition inequalities can be done in the reduced graph associated with any fractional solution of P (G, k).

Separation algorithms

Now we describe the separation algorithms we have devised for the cut, node-cut, SP-node-partition, F -node-partition and node-partition inequalities.

We start by the separation of the cut inequalities (2.3). It is well known that the separation of the cut inequalities (2.3) reduces to computing a minimum weight cut in G with respect to weight vector y. Indeed, there is a violated cut inequality (2.3) if and only if the minimum weight of a cut, w.r.t. weight vector y, is < k. One can compute a minimum weight cut in polynomial time by using any minimum cut algorithm, and especially by using the Gomory-Hu algorithm [START_REF] Gomory | Multi-terminal network flows[END_REF] which computes the so-called Gomory-Hu cut tree. This algorithm consists in |V | -1 maximum flow computations. Now we discuss the separation of the node-cut inequalities (2.4). In what follows, we show that these inequalities can be separated in polynomial time. In fact, Grötschel et al. [START_REF] Grötschel | Polyhedral and computational investigations for designing communication networks with high survivability requirements[END_REF] present a separation algorithm for inequalities (2.4) based on a transformation of the graph G into a directed graph G = ( V , A). This transformation is presented as follows. For each node u ∈ V , we add in V two copies u -and u + of u. The arc set is built in the following way. First, for each edge uv ∈ E, we add two arcs (v + , u -) and (u + , v -). Finally, for every node u ∈ V , we add an arc of the form (u -, u + ). We also let y ∈ R A be a weight vector given by

y(a) = y(uv) for a = (u + , v -) and a = (v + , u -), 1 if a = (u -, u + ) for all nodes u ∈ V.
One can see that a cut δ(W ) in G corresponds to a dicut which does not contain an arc of the form (u -, u + ). Conversely, a dicut δ + G ( W ) of G which does not contain any arc of the form (u -, u + ) corresponds to a cut of G. Also, a node-cut δ G\Z (W ) of G corresponds to a dicut of G which contains |Z| arcs of the form (u -, u + ). Conversely, a dicut of G which contains at least one arc of the form (u -, u + ) corresponds to a node-cut of G. The corresponding node set Z is given by the nodes u ∈ V such that (u -, u + ) ∈ δ + G ( W ), and the edges of δ G\Z (W ) are given by the arcs of δ + G ( W ) of the form (u + , v -) with u + ∈ W , v -∈ Ṽ \ W . Thus, cuts and node-cuts of G corresponds to dicuts of G which does not contain arcs of the form (u -, u + ), and vice-versa. Moreover, we have that

• if δ(W ) in G and δ + G ( W ) in G are corresponding cuts, then y(δ(W )) = y(δ + G ( W )); • if δ G\Z (W ) in G and δ + G ( W ) in G are corresponding cuts, then y(δ G\Z (W ))+|Z| = y(δ + G ( W )).
Thus, there is a cut or node-cut inequality violated by y if and only if there exists a dicut δ + G ( W ) in G whose weight with respect to y is < k. Notice that, if we assume the cut inequalities to be all satisfied by y, finding violated node-cut inequalities then reduces to compute a minimum weight cut in G w.r.t. weight vector y.

Consequently, our separation algorithm for node-cut inequalities is as follows. First, we assume that the cut inequalities are all satisfied by y. We build the graph G and compute a minimum weight cut, say δ + G ( W * ), w.r.t. y. If y(δ + G ( W * )) ≥ k, then every node-cut inequality is satisfied by y, and the algorithm stops. If y(δ + G ( W * )) < k, then there is a violated node-cut inequality induced by a node-cut δ G\Z (W ) with Z ⊆ V , |Z| ≤ k -1, and W ⊆ V \ Z. The node sets Z and W are given by

Z = { u ∈ V such that (u -, u + ) ∈ δ + G ( W * )}, W = {u ∈ V such that u -, u + ∈ W or u + ∈ W and u -∈ V \ W }.
Finally, computing a minimum weight cut in G can be done in polynomial time by computing, for every pair of nodes (s, t) ∈ V ×V , with s = t, a maximum flow in G from source node s + to destination t -. This, hence, reduces our algorithm to |V |(|V | -1)/2 maximum flow computations in W , which is polynomial.

Finally, we consider the separation problems for node-partition, SP-node-partition and F -node-partition inequalities. First notice that the separation problem of nodepartition inequalities is NP-Hard even when Z = ∅. For our purpose, we consider these inequalities in the case where Z = ∅. Thus, the corresponding node-partition, SP-node-partition and F -node-partition inequalities also correspond to partition, SPpartition and F -partition inequalities, which are valid for the kECSP on G. Therefore, to separate these inequalities, we use the separation heuristics developed in Bendali et al. [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF] for these latter inequalities. These algorithms are applied on the graph G ′ and solution y ′ obtained by the application of the reduction operations to G and y. As mentioned before, by Lemmas 7 and 8, any violated node-partition, SP-node-partition and F -node-partition inequality found in G ′ by the separation procedure is valid for kNCSP(G) and is also violated by y.

Primal heuristic

Next, we discuss a primal heuristic for the problem. The aim of this heuristic is to produce, for a given instance, good upper bounds of the optimal solution of the problem. Such upper bounds are used by the Branch-and-Cut algorithm to prune unrelevant branches of the Branch-and-Cut tree. This also ensures that Branch-and-Cut algorithm produces a feasible solution, even if it reaches the maximum CPU time.

The primal heuristic we have developed for our purpose consider a fractional solution y obtained at the end of the cutting plane phase, at the root node of the Branch-and-Cut tree. The aim of the heuristic is to transform y into a feasible solution for the problem. To do this, we first build the graph G = (V, E) obtained by removing from G every edge e ∈ E with y(e) = 0. Then, we iteratively remove from G all the edges uv such that u and v are both incident in G to at least k + 1 edges. We denote by G ′ = (V, E ′ ) the resulting graph, and by z the incidence vector of G ′ . Next, we check if

G ′ is k-node-connected.
We do this by calling the separation algorithms for the cut and node-cut inequalities described in the previous section on z and G ′ . If there is a cut

(resp. node-cut) inequality induced by a cut δ G ′ (W ) (resp. node-cut δ G ′ \Z (W )), which is violated by z, then we add in G ′ an edge e ∈ δ G (W ) \ E ′ (resp. e ∈ δ G\Z (W ) \ E ′ )
whose weight c(e) is minimum. If there is no cut and node-cut inequality violated by z, then G ′ is feasible for the kNCSP. We repeat this procedure until the graph G ′ is k-node-connected.

Finally, the algorithm computes and returns the weight of the graph G ′ obtained at the end of the previous step. The whole procedure is summarized by Algorithm 3 below.

Computational Results

Now we present the computational results we have obtained with our Branch-and-Cut algorithm for the kNCSP. The algorithm has been implemented in C++ using CPLEX 12.5 [3] and Concert Technology library. All the experiments have been done on a computer equiped with a 2.10 GHz x4 Intel Core(TM) i7-4600U processor and running under linux with 16 GB of RAM. We have set the maximum CPU time to five hours.

We have tested our algorithm on several instances composed of graphs taken from SNDLIB [1] and TSPLIB [2]. These are complete graphs where each node is given coordinates in the plane. The weight of each edge uv is the rounded euclidian distance between the vertices u and v. The graphs we have considered have up to 65 nodes for SNDLIB graphs and up to 150 nodes for TSPLIB graphs.

The tests have been performed for k = 3, 4, 5, and in all the experiments, we have used the reduction operations described in the previous sections, unless specified.

For each instance, we have run the algorithm three times. The first run (Run 1) is performed with all the inequalities presented before and the reduction operations included in the algorithm. The second run (Run 2) is performed without the reduction operations. The third run (Run 3) is performed with the reduction operations and with only the cut and node-cut inequalities. The results are given in Tables 3.2-3.8. Each instance is given by its name followed by the number of nodes of the graph. The other entries of the tables are: #EC the number of generated cut inequalities #NC the number of generated node-cut inequalities #SPC the number of generated SP-node-partition inequalities #NFPC the number of generated F -node-partition inequalities #NPC the number of generated node-partition inequalities COpt the value of the optimal solution Gap1 the relative error between the best upper bound and the lower bound obtained at the root node of the Branch-and-Cut tree during Run 1 Gap2 the relative error between the best upper bound and the lower bound obtained at the root node of the Branch-and-Cut tree during Run 2 Gap3 the relative error between the best upper bound and the lower bound obtained at the root node of the Branch-and-Cut tree during Run 3 NSub1 the number of nodes in the Branch-and-Cut tree obtained at Run NSub2 the number of nodes in the Branch-and-Cut tree obtained at Run NSub3 the number of nodes in the Branch-and-Cut tree obtained at Run CPU1 the total CPU time in hh:mn:sec achieved at Run 1 CPU2 the total CPU time in hh:mn:sec achived at Run 2 CPU3 the total CPU time in hh:mn:sec achived at Run 3

The gaps are all given in percentage. The instances indicated with "*" are those for which the maximum CPU time has been reached by the Branch-and-Cut algorithm.

We start our experiments by running the algorithm with k = 3, for both SNDLIB and TSPLIB graphs, and using all the inequalities and the reduction operations, that is Run 1. The results are given in Tables 3.1 and 3.2.

We first observe that all the SNDLIB instances of Table 3.1 have been solved to optimality within the CPU time limit. For TSPLIB graphs, all the instances have been solved to optimality, except one, u_159. The CPU time for the instances solved to optimality is less than 45min for SNDLIB instances and less than 2h50min for TSPLIB instances. We also observe that the gap between the optimal solution and the lower bound achieved at the root node of the Branch-and-Cut tree is less than 1% for all the SNDLIB instances except one, geant_22, for which the gap is 1.07%. For TSPLIB graphs, the gap is less than 1%, except for 6 instances for which the gap is less than 7.1%. We can also notice that the number of nodes in the Branch-and-Cut tree is quite small, less than 60 nodes, for all the instances. Our separation procedures have also detected several inequalities of each type (cut, node-cut, F -node-partition, SP-node-partition and node-partition inequalities), especially the cut and node-cut inequalities. Moreover, a large number of F -node-partition and SP-node-partition inequalities are generated while few node-partition inequalities have been generated. From these observations, we conclude that our Branch-and-Cut algorithm is efficient for solving the kNCSP with k = 3.

We have also run the algorithm, during Run 1, with k = 4 and k = 5. The results for k = 4 are given by Table 3.3, for SNDLIB instances, and by Table 3.4 for TSPLIB instances. Note that when k is even, the SP-node-partition and partition inequalities we have considered in our algorithm are redundant with respect to the cut inequalities. Thus, they are not used in the Branch-and-Cut algorithm for k = and do not appear in Tables 3.3 and3 We can first observe that for k = 4 all the SNDLIB instances are solved to optimality, in less than 2min, and this, at the root node of the Branch-and-Cut tree. For TSPLIB instances, the problem is solved in less than 2h30 for all the instances with few nodes (less than 23) in the Branch-and-Cut tree. For these latter instances, 11 of them over 17 instances are solved at the root node of the Branch-and-Cut tree. As for k = 3, several cut and node-cut inequalities have been generated, and few F -node-partition inequalities are generated. The comparison with k = 3 shows that the problem seems easier when k = 4, since the optimal solutions are obtained faster when k = 4 for all the instances. For example, ta_65 is solved in 43min55sec with 9 nodes in the Branch-and-Cut tree when k = 3, while it is solved in 2min at the root node of the Branch-and-Cut tree when k = 4. Moreover, instance u_159 is solved to optimality in 4h38min14sec when k = 4, whereas it is not solved to optimality within 5h when k = 3.

We have also run our algorithm for k = 5. The results are given in Tables 3. [START_REF]Two-edge Connected spanning subgraphs A. R. Mahjoub and polyhedral. Twoedge connected spanning subgraphs and polyhedra[END_REF] Here also, we can see that several instances are solved to optimality at the root node of the Branch-and-Cut tree for both SNDLIB and TSPLIB instances. The comparison with k = 3 also shows that the problem seems easier when k = 5. Indeed, for SNDLIB graphs, 8 instances over 11 have been solved at the root node of the Branch-and-Cut tree when k = 5 whereas only one instance has been solved at the root node for k = 3. The observation is the same for TSPLIB instances. Here, 5 instances have been solved at the root node when k = 5 whereas no instance has been solved at the root node when k = 3. Also the CPU time is, in general, better when k = 5. For example, instance gr_120 is solved in 2h26min57sec when k = 3 and in 1h09min03sec when k = 5. All these observations suggest that the kNCSP becomes easier when k increases.

A comparison between the case k = 4 and k = 5 shows that the problem seems easier when k = 4. Indeed, the CPU time is in general better when k = 4 and fewer nodes are generated in the Branch-and-Cut tree when k = 4. We can say from this that the problem is harder when k is odd than when k is even. The remarks made here are similar to those made by Bendali et al. [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF] for the kECSP. They also concluded from their experiments that the kECSP is harder when k is odd, and that the kECSP becomes easier when k increases with the same parity.

The next series of experiments concerns the efficiency of the reduction operations θ 1 , ..., θ 4 . For this, we have run the Branch-and-Cut algorithm with k = 3 and without the reduction operations (Run 2).The results are given by Table 3 We can observe from Table 3.7 that, for the considered instances, the performances of the Branch-and-Cut algorithm are decreased when the reduction operations are not used. One can see that both the CPU time and the number of nodes in the Branch-and-Cut tree are increased when the reduction operations are not used in the algorithm. Also, the gap increases for all the instances, which indicates that a fewer number of inequalities or less efficient inequalities are generated during the separation phases. Moreover, one instance, eil_76 which is solved to optimality at Run 1 is not solved to optimality within 5h without the reduction operations. This clearly proves the efficiency of the reduction operations on the resolution process.

Our last series of experiments aims to check the efficiency of the F -node-partition, SP-node-partition and node-partition inequalities in solving the kNCSP. For this, we have run the Branch-and-Cut algorithm in Run 3 with only the cut and node-cut inequalities. The results are presented in Table 3 Here also, the comparison between Run 1 and Run 3 shows that the performances are decreased when F -node-partition, SP-node-partition and node-partition inequalities are not used in the algorithm. The CPU time, the number of nodes in the Branchand-Cut tree and the gap are increased for all the instances of Table 3.8. Also, instance gr_96 is not solved to optimality within 5h when F -node-partition, SP-node-partition and node-partition inequalities are not used, while it is in Run 1. This also shows the efficiency of the above inequalities in solving the kNCSP.

We conclude this computational study by comparing the optimal solutions obtained here for the kNCSP with those of the kECSP obtained by Bendali et al. [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF]. The aim is to know how often optimal solutions of the kECSP and kNCSP are equal. The next table, Table 3.9, presents, for some TSPLIB instances, the optimal solutions of the kECSP, those of the kNCSP for k = 3 and the gap between the two solutions, given by Table 3.9: Comparison between of the best solutions of kECSP and the kNCSP for k = 3.

Gap = COpt_3NCSP -COpt_3ECSP COpt_3ECSP .
From Table 3.9, we can see that the optimal solutions of the two problems are different for all the considered instances. However, we can see that the gap between the two solutions is relatively small for most of them. This let us conclude that the best solutions obtained by Bendali et al. [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF] for the 3ECSP are good upper bounds of the optimal solutions of the 3NCSP. Clearly, this remark cannot be generalized since we may find graphs for which the gap between the optimal solutions of the kNCSP and the kECSP is more important, but solving the kECSP could produce a good approximation of the kNCSP.

Conclusion

We have studied the k-node-connected subgraph problem with high connectivity requirement, that is, when k ≥ 3. We have presented some classes of valid inequalities and described some conditions for these inequalities to be facet defining for the associated polytope. We have also investigated the structural properties of the extreme points of the linear relaxation of the problem and presented some reduction operations. Using these results, we have devised a Branch-and-Cut algorithm for the problem. The computational results we have obtained have shown that the F -node-partition, SPnode-partition and partition inequalities are effective for solving the problem. Also, the reduction operations we have used are shown to be efficient in the separation phase of the Branch-and-Cut algorithm. The experiments also show that, as for the kECSP, the kNCSP becomes easier when k increases, and is harder when k is odd than when k is even.

The study presented in this chapter shows the efficiency of some valid inequalities, namely F -node-partition, SP-node-partition and partition inequalities, in solving the kNCSP. It would be interesting to investigate the polytope of the problem in a deeper way and identify cases in which these inequalities completely define the polytope of the problem. In this chapter we present a Branch-and-Cut-and-Price algorithm we have devised to solve the 2NCSP. In Section 4.1 we will present an extended formulation for the problem. In sections 4.2.1 and 4.2 we will describe the framework of the column generation algorithm. In Section 4.3, we will present some computational results and Section 4.4 will be devoted to some concluding remarks.

Extended formulation

We give a cycle-based integer programming formulation for the 2-node-connected subgraph problem. We consider an undirected graph G = (V, E), and let w(e) be the weight of the edge e, for all e ∈ E. We suppose that w(e) > 0, for all e ∈ E.

First, we observe that in a solution of the problem, each two nodes of the graph belong to a cycle. Thus any solution of the problem is composed of a collection of cycles.

Let θ uv be the set of simple cycles of G going through nodes u and v, for all u, v ∈ V , and let θ = for all e ∈ E. Now let y(C) be a 0 -1 variable whose value is 1 if the cycle C ∈ θ is taken in the solution and 0 otherwise, and x ∈ {0, 1} E such that x(e) = 1 if edge e is taken in the solution and 0 otherwise. Consider the following inequalities which are satisfied by every solution of the 2NCSP. Here M is an upper bound on the number of cycles going through an edge in a solution and can be chosen to be M = (|V | -2)!.

Inequalities (4.1) ensure that between each two nodes u and v in V there exists a cycle going through u and v, and inequalities (4.2) ensure that if an edge is not taken in the solution, all the cycles containing the edge are not considered.

Moreover, the following is easily seen.

Theorem 12

The 2NCSP is equivalent to the following integer program min{wx | x satisfies (4.1) -(4.3) and x ∈ Z E + }. (4.4) Formulation (4.4) uses an exponential number of variables but a polynomial number of contraints. We will use a column generation algorithm to solve its linear relaxation.

Branch-and-Cut-and-Price algorithm

Column generation algorithm

A column generation algorithm for the linear relaxation of (4.4) starts by solving a linear program obtained from (4.4) by considering a subset of variables (columns) which induce a feasible basis for the initial problem. For our purpose, we consider first sets of hamiltonian cycles C H ⊂ θ. Note that the subgraph induced by the cycles of C H contains 2 node-disjoint paths between every pair of nodes of V . Thus, the edge set corresponding to the cycles induces a solution of the 2NCSP, and, together with the sets C H , induces a feasible solution for the linear relaxation of Formulation (4.4). Hence, we consider as initial set of variables those induced by the edge set corresponding to the cycles C H and the sets C H . The first linear program solved in the column generation algorithm is, therefore, the one obtained from the linear relaxation of Formulation (4.4) and these variables. This linear program is

Min e∈E w(e)x(e) C∈C H a C (u, v)y(C) ≥ 1 for all u, v ∈ V, (4.5) C∈C H b C (e)y(C) ≤ Mx(e)
for all e ∈ E, (4.6)

y(C) ≥ 0 for every C ∈ C H , (4.7)
x(e) ≤ 1 for all e ∈ E. (4.8)

At each iteration, if the current solution is not optimal, the algorithm tries to generate new columns, that is to add to C H , cycles C ∈ θ \ C H such that the variable y(C) has a negative reduced cost. This is done by solving the so-called pricing problem which consists here in finding, a cycle C * such that C r (C * ) = min{c r (C) | C ∈ θ} and c r (C * ) < 0, where c r (C) is the reduced cost of the variable y(C).

The reduced cost c r (C) is computed using the dual optimal solution. Let α uv , u, v ∈ V , be the dual variables associated with inequalities (4.5), β e the dual variable associated with each inequality (4.6), for all e ∈ E, and γ e the dual variables associated with inequalities (4.8). The longest cycle between each two nodes u and v in V is computed using the compact formulation of Dixon and Goodman [START_REF] Dixon | An algorithm for the longest cycle problem[END_REF]. The formulation is an integer linear program in bounded variables. The ILP model will find the longest cycle through a given node, say node 1, and application to each of the |V | nodes in the graph will get the longest among all the cycles. The variables are j) is used in the longest cycle, 0 otherwise.

The dual problem is

X ij = 1 if edge (i,
F i = 1 if node i is used in the longest cycle, 0 otherwise.
The integer programming model is then

max z = i,j∈V α ij F i F j - (i,j)∈E β (i,j) X ij subject to the constraints |V |+1 i=1 X ik = F k k = 2, 3, ..., |V | (4.14) |V |+1 j=1 X kj = F k k = 2, 3, ..., |V | (4.15) |V | j=2 X 1j = |V | i=1 X i|V |+1 (4.16
)

Y i -Y j + (|V | + 1)X ij ≤ |V | i, j = 1, 2, ..., |V | + 1 (4.17) 0 ≤ Y i ≤ |V | + 1 Y i integer (4.18)
The node |V | + 1 is introduced by splitting node 1 into nodes 1 and N + 1, each with the same adjacencies. The constraints (4.14)-(4.18) specify a simple path from node 1 to node |V | + 1. Constraints (4.17) and (4.18) introduce dummy integer variables, one Y i for each node i ∈ V , which do not permit the development of disjoint side cycles. This assures us that all feasible solutions will contain exactly one path from 1 to |V |+1. Now if c r (C) ≥ 0 for all C ∈ θ, then the optimal solution of the current linear program is optimal for the linear relaxation of Formulation (4.4).

The optimal solution of the linear relaxation of Formulation (4.4) is feasible for Formulation (4.4) if it is integral. If this is not the case, then we add further valid inequalities for 2NCSP(G) that are violated by this solution. The inequalities that are considered are the cut inequalities (2.3), and the F -partition inequalities (2.12).

To obtain initial interesting feasible solutions we have implemented several heuristics that generate hamiltonian cycles. The first heuristic is quite simple. We initialize the cycle by randomly choosing a node. Then we add a minimum weight edge, not selected before, among its incidence edge list. We continue adding the edges in the same way until we complete the cycle.

The second is a Greedy heuristic. It gradually constructs a cycle by repeatedly selecting an edge having the smallest weight, and adding it to the cycle as long as it doesn't create a cycle with less than |V | edges, or increases the degree of any node to more than 2. We must not add the same edge twice of course. The steps are: 1. Sort all edges. 2. Select an edge with the smallest weight and add it to the cycle if it doesn't violate any of the above constraints. 3. If we do not have |V | edges in the cycle, repeat step 2.

Pricing heuristics

The problem of finding the longest simple cycle or path in an edge-weighted network is NP-complete. And the exact pricing in our problem requires |V | calls to the compact formulation in [START_REF] Dixon | An algorithm for the longest cycle problem[END_REF]. Therefore we also needed pricing heuristics we used before calling the exact pricing.

In the first pricing heuristic we first add a maximum weight edge. We then construct the cycle by adding the edge that maximizes the cycle weight, among the remaining edges. Once we obtain a cycle, we remove all the isolated branches.

The second heuristic is based on a Tabu Search. The fundamental concept in any neighborhood search is the notion of a neighborhood. The neighborhood N of a solution s (noted N(s)) is a set of solutions where each s * ∈ N(p) is reachable by a simple move from s. The definition of the move is arbitrary, in our heuristic a move scheme is either a swap of two adjacent nodes in the path, deleting a node from the path, or adding a node to the path. The move is chosen randomly with equal probabilities. In a naive neighborhood search, the algorithm starts with a solution s and then evaluates all solutions in N(s). Then it chooses the best s b ∈ N(s), sets s = s b , and iterates. The problem with a naive neighborhood search is that it can ascend to local maxima and returns a suboptimal solution. The main idea is that certain moves within the neighborhood are classified as tabu under certain circumstances. If a move is tabu, the solution generated by that move cannot usually be considered the best in the neighborhood. The exception to the rule is that if a tabu move would result in a solution which is better than any of the solutions that have been seen to that point. If such a solution exists, the algorithm will then choose that solution even though it is tabu. Finally, we define stopping conditions for the main loop. We set the maximum number of iterations at max_It=1000. The algorithm will terminate if this number of iterations is reached. The algorithm also stops if there is no improvement in max_It/5 iterations. The whole pricing procedure is summarized in Algorithm 4 below. The entries of the following tables are:

|V | : the number of nodes of the graph, COpt_BC : value of the best upper bound obtained by the Branch-and-Cut, COpt_BCP : value of the best upper bound obtained by the Branch-and-Cut-and-Price, Gap_BC : the gap for the Branch-and-Cut, Gap_BCP : the gap for the Branch-and-Cut-and-Price, NSub_BC : the number of nodes in the tree for the Branch-and-Cut, NSub_BCP : the number of nodes in the tree for the Branch-and-Cut-and-Price, CPU_BC : total CPU time for the Branch-and-Cut, CPU_BCP : total CPU time for the Branch-and-Cut-and-Price.

First, in Table 4.3 we compare the two formulations for the SNDLIB instances. We observe that for these instances the CPU time for the column generation algorithm is greater than for the Branch-and-Cut algorithm. We also observe that the number of instances solved to optimality is quite the same for the two formulations, and the gaps are generally close. We can also see that most of the instances required more branching in the column generation algorithm than in the Branch-and-Cut algorithm. Then, in Table 4.4 we compare the two formulations for the TSPLIB graphs. We observe that the efficiency of the different algorithms for solving the problem is not the same. For the instances solved to optimality, the total CPU time for the Branchand-Cut algorithm is better than for the column generation algorithm, except for the instance kroC100, it was solved in 3h 49mn 24s for the column generation algorithm and in 2h 45mn 27s for the Branch-and-Cut algorithm. The important CPU time for the column generation algorithm can be explained by the fact that the pricing problem used to solve the linear relaxation of the extended formulation, computes a longest cycle formulation, which contains a quadratic objective function. Thus, the difference of CPU time mainly is the time spent by the algorithm for the pricing. However, the gap obtained by the column generation algorithm is in general better than the gap obtained by the Branch-and-Cut algorithm.

Conclusion

In this chapter, we presented an extended formulation for the k-node-connected subgraph problem. We studied a column generation algorithm and efficient heuristics for the resolution of the problem. And using these results we devised a Branch-and-Cutand-Price algorithm to solve the problem. The computational results have shown that the column generation algorithm is effective in solving the problem and producing good upper bound for the problem. Also, it has been shown that the Branch-and-Cut algorithm is more efficient in solving the problem to optimality. We also observed that for the column generation algorithm when approaching a near optimal LP value, the algorithm struggles to find the optimal LP value even though it is close. This phenomenon is known as the tailing off effect. As described in [START_REF] Desrosiers | A Primer in Column Generation[END_REF], a main explanation for the tailing off effect is that the dual variables converge slowly towards their respective optimal value, and, from one iteration to another, take unrelated and random values. As a future work, we can aim at decreasing this effect, which will improve the efficiency of the resolution by introducing an algorithm that stabilizes and accelerates the solution process while remaining within the linear programming framework. The stabilized algorithm can be used to improve the solution times for difficult instances and to solve larger ones.

One can also try to extend the approach developed in this chapter to study the problem for k ≥ 3 with an extended formulation using path variables, and devise efficient Branch-and-Price and Branch-and-Cut-and-Price algorithms for the problem in this case.

Chapter 5

The k node-disjoint hop-constrained survivable network problem Given a graph with weights on the edges, a set of origin and destination pairs of nodes, and two integers L ≥ 2 and k ≥ 2, the k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph of G such that between every origin and destination there exist at least k node-disjoint paths of length at most L.

In this chapter we consider this problem from a polyhedral point of view. We propose an integer linear programming formulation for the problem for L = 2, 3 and investigate the associated polytope. We introduce new valid inequalities for the problem, and give necessary and sufficient conditions for these inequalities to be facet defining. We also devise separation algorithms for these inequalities. Using these results, we propose a Branch-and-Cut algorithm for solving the problem for k ≥ 0 and L = 3, and for k = 2 and L = 4, along with some computational results.

Integer Programming Formulation

Let G = (V, E) be a graph, and F ⊆ E an edge set which induces a solution of the kNDHP. As F is a solution of the problem, the subgraph induced by F , say G F , contains k edge-disjoint st-paths for every (s, t) ∈ D. Thus, by Menger's theorem [START_REF] Menger | Zur allgemeinen kurventhorie[END_REF], every st-cut of G F contains at least k edges. Consequently, the incidence vector of F satisfies the following inequalities

x(δ G (W )) ≥ k,
for all st-cut δ(W ) and (s, t) ∈ D.

(

Inequalities (5.1) are called st-cut inequalities.

Dahl [START_REF] Dahl | Notes on polyhedra associated with hop-constrained paths[END_REF] introduces a class of valid inequalities as follows.

Let (V 0 , ..., V L+1 ) be a partition of V with s ∈ V 0 , t ∈ V L+1 , and V i = ∅ for all i ∈ {1, ...L}. Let T be the set of edges uv ∈ E such that u ∈ V i , v ∈ V j and |i -j| > 1, that is,

T = δ(V 0 , ..., V L+1 ) \ L i=0 [V i , V i+1 ].
The set T is called an L-st-path cut. Then the inequality x(T ) ≥ 1 is valid for the L-st-path polyhedron. Using similar type of partitions, we can generalize these inequalities to the kNDHP as

x(T ) ≥ k, for every L-st-path-cut T of G, ( 5.2)
for any (s, t) ∈ D.

Inequalities of type (5.2) are called L-st-path-cut inequalities. Figure 5.1 shows an L-st-path-cut.

V 2 V 3 V 4 t s V 1 V 0 Figure 5
.1: Support graph of an L-st-path-cut with L = 3 and T formed by the solid edges Inequalities (5.1) and (5.2) can be easily adapted in order to ensure the existance of k node-disjoint paths of length at most L. Given node subsets Z ⊂ V \ {s, t} for (s, t) ∈ D, and

W ⊂ V \ Z, the st-node cut δ G\Z (W ) of G is the st-cut induced by W in G \ Z. Any L-st-path cut in G \ Z is called an L-st-node path-cut of G.
A solution x ∈ R E of the kNDHP also satisfies the following inequalities

x(δ G\Z (W )) ≥ k -|Z|, for all st-node-cut δ G\Z (W ), Z ⊂ V \ {s, t} (5.3) such that 1 ≤ |Z| ≤ k -1, and (s, t) ∈ D, x(T G\Z ) ≥ k -|Z|, for all L-st-node-path-cut T G\Z of G \ Z, (5.4) Z ⊂ V \ {s, t}such that 1 ≤ |Z| ≤ k -1,
and (s, t) ∈ D.

Inequalities (5.3) and (5.4) are called respectively st-node-cut and L-st-node-path-cut inequalities. Moreover, the incidence vector of an edge set F inducing a solution of the kNDHP satisfies

x(e) ≥ 0, for all e ∈ E, (

x(e) ≤ 1, for all e ∈ E.

(5.6)

In the following we show that the st-cut, st-node-cut, L-st-path-cut, L-st-node-pathcut, and trivial inequalities, together with integrality constraints, suffice to formulate the kNDHP as a 0 -1 linear program when L ∈ {2, 3}.

For this, we consider, for each demand (s, t) the directed G st = ( V st , A st ) obtained as follows (see also [START_REF] Bendali | The k edge-disjoint 3-hop-constrained paths polytope[END_REF] and [START_REF] Diarrassouba | Survivable network design problems with high connectivity requirements[END_REF]). The node set V st is formed by the nodes s, t, the Bendali et al. [START_REF] Bendali | The k edge-disjoint 3-hop-constrained paths polytope[END_REF] show that every st-cut and 3-st-path-cut C ⊆ E can be associated with a directed st-cut C ⊆ A st which does not contain an arc of the form (u, u ′ ), with u ∈ V \ {s, t}, and vice-versa. Moreover, they show that a solution x ∈ R E can be associated with a solution y ∈ R Ast such that x(C) = y( C). Now we give the following theorem.

s u u ′ v w w ′ t v s w t u v ′
Theorem 13 Let x ∈ {0, 1} E be an integral solution, which satisfies all the cut and 3-st-path-cut inequalities (5.1) and (5.2). Then, x induces a solution of the kNHDP if and only if it satisfies all the st-node-cut and 3-st-node-path-cut inequalities.

Proof. As the st-node-cut and the 3-st-node-cut inequalities are valid for the kNDHP, if x is a solution of the kNDHP, then it satisfies these inequalities. Now suppose that x does not induce a feasible solution of the kNHDP, that is the subgraph of G induced by x, denoted by G(x) = (V, E(x)) does not contain k nodedisjoint 3-st-paths for some demand (s, t) ∈ D. We are going to show that there exists an st-node-cut or a 3-st-node-path-cut inequality which is violated by x. Let G st be the directed graph associated with (s, t) as described above, and let y ∈ R Ast be a weight vector such that

y(a) =        1
if a corresponds to edge e and e ∈ E(x), 0 if a corresponds to edge e and e / ∈ E(x), +∞ if a = (u, u ′ ) for all u ∈ V \ {s, t}.

Remark that, as G is simple, that it is does not contain parallel edges, if two 3-stpaths P 1 and P 2 are not node-disjoint, then they are of the form P 1 = (s, u, v, t) and P 2 = (s, v, z, t) with u, v, z ∈ V \ {s, t} and u = v = z. These two paths correspond in G st to paths (s, u, v ′ , t) and (s, v, z ′ , t). Conversely, two paths (s, u, v ′ , t) and (s, v, z ′ , t) of G st correspond to two paths (s, u, v, t) and (s, v, z, t) which are not node-disjoint. Consequently, when x is not feasible for the kNHDP, any maximum set of disjoint stdipaths of the graph G st , will contain two paths of the form (s, u, v ′ , t) and (s, v, z ′ , t), with u, v, z ∈ V \ {s, t} and u = v = z = u. Now we introduce the following procedure, that we call Procedure BuildZ, which aims to build a node set Z ⊆ V , from which we will obtain the violated st-node-cut or 3-stnode-path-cut inequalities. Let Z ⊆ V be a node set of G and denote by Z the nodes of G st corresponding to those of Z, that is Z = {u, u ′ such that u ∈ Z}. At the begining of the procedure Z = ∅. Now compute a maximum flow from s to t in G st \ Z, with each arc a ∈ A st having the capacity y(a). This gives a maximum set P of node-disjoint st-dipaths in G st \ Z. This is because the flow going in or out of a node v ∈ W \ {s ′ , t ′ } is either 0 or 1, for each node v ∈ W \{s ′ , t ′ } has at most one arc going in from s ′ and at most one arc goint out to t ′ . Remark that some of these paths may correspond to non node-disjoint 3-st-paths of G, that is they are of the form (s, u, v ′ , t) and (s, v, z ′ , t). Let P ′ be the set of these paths. Also let P ′ be the set of paths of G corresponding to those of P ′ and U ⊆ V the set of nodes of G which are shared by two paths of P ′ . Now, add to Z the nodes of U and repeat this procedure until |Z| ≥ k or U = ∅. It should be noticed that when U = ∅, the arc-disjoint st-dipaths obtained by the computation of the maximum flow in G st \ Z correspond to node-disjoint 3-st-paths of G\Z.

The identification of the nodes of U can be easily done by simply considering, for each node u ∈ V \ Z, the arcs entering and leaving nodes u and u ′ with flow value 1. Namely, consider a node v ∈ U. This means that after the maximum flow computation, there are two paths (s, u, v ′ , t) and (s, v, z ′ , t). Since the arc capacities are either 0 or 1, this means that • the flow value on arc (s, v) is 1,

• the flow value on arc (v, v ′ ) is 0,

• the flow value on arc (v ′ , t) is 1. Figure 6.2 illustrates the above remark. The solid lines represent arcs having flow value 1 and dashed lines represent arcs with flow value 0. The flow value of the arcs represented by dotted lines may be 0 or 1.

s t u v z u ′ v ′ z ′ Figure 5.3: Two st-dipaths of G st \ Z inducing non node-disjoint 3-st-paths in G \ Z.
Thus, let Z ⊆ V \ {s, t} be the node set obtained by the application of procedure BuildZ. It is not hard to see that by the construction of Z, the graph G(x) contains |Z| st-paths of the form (s, u, t), for all u ∈ Z. Clearly, these paths are node-disjoint. This also implies that |Z| ≤ k -1, for otherwise, G(x) would contain at least k nodedisjoint 3-st-paths, which is not possible. Now compute a maximum flow from s to t in G st \ Z, and let f be the value of that flow. By the construction of Z, this later flow corresponds to a set of f disjoint 3-st-paths of G which are node-disjoint. Moreover, these paths are node-disjoint from those induced by Z. Thus, together with the paths induced by Z, we obtain |Z| + f node-disjoint 3-st-paths in G(x). As by assumption, G(x) does not contain k node-disjoint 3-st-paths, we have that

|Z| + f < k, that is f < k -|Z|. Now, as f is the value of the maximum flow of G st \ Z, the weight of a minimum cut C of G st \ Z is y( C) = f < k -|Z|.
Finally, as shown by Bendali et al. [START_REF] Bendali | The k edge-disjoint 3-hop-constrained paths polytope[END_REF], C corresponds to to an edge set C which is either an st-cut or a 3-st-path-cut of G \ Z, that is C corresponds to an st-node-cut or a 3-st-node-path-cut of G whose weight is

x(C) = y( C) = f < k -|Z|.
Consequently, the st-node-cut or 3-st-node-cut induced by C is violated by x. (5.7)

We will call inequalities (5.1)-(5.6) basic inequalities. Here basic means that they are necessary in the basic formulation of the problem. We will denote by kNDHP(G, L) the convex hull of all the integer solutions of (5.1)-(5.6), and call kNDHP(G, L) the k-Node-Disjoint Hop-Constrained Problem polytope. Formulation (5.7) is no longer valid for L ≥ 5. Consider for example the graph shown in Figure 5.4. For k = 2 its incidence vector satisfies inequalities (5.1)-(5.6) but the graph does not contain two node-disjoint st-paths of length at most L = 5. This example is borrowed from [START_REF] Huygens | Integer programming formulations for the two 4-hop-constrained paths problem[END_REF].

Polytope and valid inequalities

In this section, we present several classes of valid inequalities inspired from the kEDHP that have been introduced in the literature. Since any solution of the kNDHP is also solution of the kEDHP, any valid inequality for the kEDHP polytope on G is also valid for kNDHP(G, L). Also note that if S ⊆ E is a solution of kNDHP in G and

Z ⊂ V , such that |Z| ≤ k -1, then the restriction of S on G \ Z is a solution of the (k -|Z|)NDHP on G \ Z with respect to origin-destination pairs contained in G \ Z. Lemma 9 Let Z ⊂ V , and let D ′ ⊆ D be a subset of origin-destination pairs in G \ Z. Suppose that D ′ = ∅. If an inequality ax ≥ α(k) is valid for kNDHP(G, L) in G with respect to D then the inequality a ′ x ≥ α(k -|Z|) is valid for kNDHP(G \ Z, L), with respect to D ′ , where a ′ is the restriction of a on G \ Z.
Note that in Lemma 9 we consider α(k) as a right hand side in the inequality ax ≥ α(k) just to express the fact that the right hand side of a valid inequality of the kNDHP may depend of k.

Generalized L-st-path-cut inequalities

Dahl and Gouveia [START_REF] Dahl | On the directed hop-constrained shortest path problem[END_REF] introduce the so-called generalized L-st-path-cut inequalities for the problem of finding an L-st-path between two nodes s and t. They are defined as follows. Let (s, t) ∈ D and π = (V 0 , ..., V L+r ), r ≥ 1, be a partition of V such that s ∈ V 0 and t ∈ V L+r . Then the generalized L-st-path-cut inequality induced by (s, t) and π is

e∈[V i ,V j ],i =j min(|i -j| -1, r)x(e) ≥ r.
(

These inequalities can be easily extended to the kNDHP by replacing the right-handside of inequality (5.8)

by (k -|Z|)r, with Z ⊂ V , |Z| ≤ k -1, yielding e∈[V i ,V j ],i =j min(|i -j| -1, r)x(e) ≥ (k -|Z|)r.
(5.9) Inequality (5.9) is valid for kNDHP(G, L). A jump is an edge between two nonconsecutive sets of π. Inequality (5.9) gives the minimum number of jumps in a partition π = (V 0 , ..., V L+r ) needed in a solution of the problem. Inequalities of type (5.9) will also be called generalized L-st-path-cut inequalities.

Double cut inequalities

Huygens et al. [START_REF] Huygens | The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut[END_REF] introduce the so-called double cut inequalities for the 2EDHP for L = 3. They are defined as follows. Consider the partition π

= (V 1 0 , V 2 0 , V 1 , ..., V 4 ) of V such that (V 1 0 , V 2 0 ∪ V 1 , V 2 , V 3 , V 4 ) induces a 3-st-path-cut, and V 1 induces a valid st-cut in G. If F ⊆ [V 2 0 ∪ V 1 ∪ V 4 , V 2
] is chosen such that |F | is odd, then the double cut inequality can be written as

x([V 1 0 , V 1 ∪ V 2 ∪ V 3 ∪ V 4 ]) + x([V 2 0 , V 1 ∪ V 3 ∪ V 4 ])+ x([V 1 , V 3 ∪ V 4 ]) + x([V 2 0 ∪ V 1 ∪ V 4 , V 2 ]) ≥ 3 - |F | 2 (5.10)

Polytope and valid inequalities 87

s t s1 V 1 0 V 2 0 V1 V2 V3 V4
edges of the double cut not in F edges not in the double cut possible edges of F We now generalize these inequalities for the kNDHP for L ≥ 2. Let Z ⊂ V \ {s, t}, for (s, t) ∈ D, and V 0 , ...,

V i 0 -1 , V 1 i 0 , V 2 i 0 , V i 0 +1 , ..., V L+1 be a family of node subsets of V \ Z such that π = (V 0 , ..., V i 0 -1 , V 1 i 0 , V 2 i 0 ∪ V i 0 +1 , ..., V L+1 ) induces a partition of G \ Z. Suppose that 1. there exists an (s, t) ∈ D such that V 1 i 0 ∪ V 2 i 0 induces an st-node-cut in G \ Z and s ∈ V 1 i 0 or t ∈ V 1 i 0 ,
2. there exists an (s, t) ∈ D such that V i 0 +1 induces an st-node-cut in G \ Z, 3. there exists an (s, t) ∈ D such that π induces an

L-st-node-path-cut in G \ Z with s ∈ V 0 (resp. t ∈ V 0 ) and t ∈ V L+1 (resp. s ∈ V L+1 ). Let E = [V i 0 -1 , V 1 i 0 ] ∪ [V i 0 +2 , V 2 i 0 ∪ V i 0 +1 ] ∪ k,l / ∈{i 0 ,i 0 +1},|k-l|>1 [V k , V l ] and F ⊆ E such that |F | and k -|Z| have different parities. Let also Ê = ( i 0 -2 i=0 [V i , V i+1 ]) ∪ ( L i=i 0 +2 [V i , V i+1 ]) ∪ F .
Then we have the following inequality.

x(δ(π) \ Ê) ≥ 3(k -|Z|) -|F | 2 (5.11)
Theorem 14 Inequalities (5.11) are valid for kNDHP(G, L).

Proof. Let T G\Z be the L-st-node-path-cut of G \ Z induced by the partition π and Z. Thus, the following inequalities are valid for kNDHP(G, L),

x G\Z (T ) ≥ k -|Z|, x(δ G\Z (V 1 i 0 ∪ V 2 i 0 )) ≥ k -|Z|, x(δ G\Z (V i 0 +1 )) ≥ k -|Z|, -x(e) ≥ -1 for all e ∈ F,
x(e) ≥ 0 for all e ∈ E \ F.

(5.12)

By summing these inequalities, divinding by 2 and rouding up the right hand side, we obtain inequality (5.11). These inequalities will also be called double-cut inequalities.

If L = 3 and i 0 = 0, inequality (5.11) can be written as

x([V 1 0 , V 1 ∪ V 2 ∪ V 3 ∪ V 4 ]) + x([V 2 0 , V 1 ∪ V 3 ∪ V 4 ]) + x([V 1 , V 3 ∪ V 4 ])+ x([V 2 0 ∪ V 1 ∪ V 4 , V 2 ] \ F ) ≥ 3(k -|Z|) -|F | 2 .
(5.13)

Here π = (V 1 0 , V 2 0 ∪ V 1 , V 2 , V 3 , V 4 ) and F ⊆ [V 2 0 ∪ V 1 ∪ V 4 , V 2 ] such that |F | and k -|Z| have different parities.

Triple path-cut inequalities

Huygens et al. [START_REF] Huygens | The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut[END_REF] introduce the so-called triple path-cut inequalities for the 2EDHP for L = 3. They are defined for a partition

(V 0 , V 1 , ..., V 5 ) of V with s 1 , s 2 ∈ V 0 , t 1 ∈ V 4 and t 2 ∈ V 5 . Then the triple path-cut inequality 2x([V 0 , V 2 ]) + 2x([V 0 , V 3 ]) + 2x([V 1 , V 3 ])+ x([V 0 ∪ V 1 ∪ V 2 ∪ V 3 , V 4 ∪ V 5 ] \ {e}) + x([V 4 , V 5 ]) ≥ 3 (5.14) where e ∈ [V 2 ∪ V 3 , V 4 ] ∪ [V 3 , V 5 ]
, is valid for 2EDHP(G, 3).

We now generalize these inequalities for the kNDHP for L = 3. {s, t} ∈ D such that V i induces an st-cut of G. We can see that V 0 may be empty.

The partition (V 0 , V 1 , ..., V p ) is called a Steiner-partition. And we have the following inequality

x(δ G\Z (V 0 , ..., V p )) ≥ (k -|Z|)p 2 . ( 5.17)
Inequalities of type (5.17) will be called Steiner-partition inequalities.

Theorem 16 Inequalities (5.17) are valid for kNDHP(G, L).

Proof. The following inequalities are valid for kNDHP(G, L).

x G\Z (V i ) ≥ k -|Z|, for i = 1, ..., p,

x(e) ≥ 0, for all e ∈ δ(V 0 ).

(

By adding them we obtain

2x(δ G\Z (V 0 , ...., V p )) ≥ (k -|Z|)p.
By dividing by 2 and rounding up the right hand side, we get inequality (5.17).

Steiner SP-partition inequalities

Diarrassouba et al. [START_REF] Diarrassouba | Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem[END_REF] introduced the so-called Steiner SP-partition inequalities for the kEDHP. In what follows we extend these inequalities to the kNDHP. They are defined as follows.

Let Z ⊂ V \R D , where R D is the set of terminal nodes of G. Consider a partition π = (V 1 , ..., V p ), p ≥ 3, of V \ Z, such that the graph G π = (V π , E π ) is series- parallel (G π is the graph obtained by contracting the sets V i , i = 1, ...p). Suppose that V π = {v 1 , ..., v p }
where v i is the node of G π obtained after the contraction of the set V i , i = 1, ..., p. The partition π is called a Steiner-SP-partition if and only if π is a Steiner-partition and either 1. p = 3 or 2. p ≥ 4 and there exists a node v i 0 ∈ V π incident to exactly two nodes v i 0 -1 and v i 0 +1 such that after the contraction of the sets V i 0 , V i 0 -1 and V i 0 , V i 0 +1 , the partitions π 1 and π 2 obtained from π are also Steiner-SP-partitions.

Theorem 17 [START_REF] Diarrassouba | Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem[END_REF]

Let π = (V 1 , ..., V p ), p ≥ 3, be a partition of V such that G π is series- parallel.

The partition π is a Steiner-SP-partition of G if and only if the subgraph of G D induced by π is connected.

From Theorem 17, note that if the demand graph is connected, then every Steinerpartition of V \ Z inducing a series-parallel subgraph of G \ Z is a Steiner-SP -partition of V \ Z. With a Steiner-SP-partition (V 1 , ..., V p ), p ≥ 3, we associate the following inequality Proof. Let π = (V 1 , ..., V p ) be a Steiner-SP-partition. The proof is by induction on p. If p = 3, as π is a Steiner-partition then we associate with π the inequality

x(δ G\Z (V 1 , ..., V p )) ≥ k -|Z| 2 p -1. ( 5
x(δ G\Z (V 1 , V 2 , V 3 )) ≥ 3(k -|Z|) 2 = 3 (k -|Z|) 2 -1. (5.20)
Now suppose that every inequality (5.19) induced by a Steiner-SP-partition of p elements, p ≥ 3, is valid for kNDHP(G, 3) and let π = (V 1 , ..., V p , V p+1 ) be a Steiner-SP-partition. Since G π is series-parallel, then there exists a node set V i 0 of π such that it is incident to exactly two elements of π, V i 0 -1 and

V i 0 +1 . Let T 1 = [V i 0 , V i 0 +1 ] and T 2 = [V i 0 , V i 0 -1 ].
As π is a Steiner-SP-partition, it is also a Steiner-partition. As V i 0 and Z ⊂ V \ {s, t} induce a valid st-node-cut inequality, for some {s, t} ∈ D. Thus x(T 1 ) + x(T 2 ) ≥ k -|Z|. W.l.o.g., we suppose that

x(T 1 ) ≥ (k -|Z|) 2 . (5.21) Let π ′ = (V 1 , ..., V i 0 -2 , V i 0 -1 ∪ V i 0 , V i 0 +1 , ..., V p+1
) be a partition. As π is a Steiner-SPpartition which contains more than three elements, π ′ is also a Steiner-SP-partition with p elements. Then, by the induction hypothesis, we have the following valid Steiner-SPpartition inequality induced by π ′ .

x(δ G\Z (V 1 , ..., V i 0 -2 , V i 0 -1 ∪ V i 0 , V i 0 +1 , ..., V p+1 )) ≥ k -|Z| 2 p -1. (5.22)
By summing the inequalities (5.21) and (5.22), we get

x(δ G\Z (V 1 , ..., V p , V p+1 )) ≥ k -|Z| 2 (p + 1) -1. (5.23)
Hence, we have the result.

The rooted partition inequalities

A further class of valid inequalities is the rooted partition inequalities. We consider p demands, |D| ≥ p ≥ 2, of the form (s, t i ), i = 1, ...p, for s ∈ V and t i ∈ V \ {s}. Let (V 0 , V 1 , ..., V p ) be a partition of V such that s ∈ V 0 and t i ∈ V i , for all i ∈ {1, ..., p}. This partition is called a rooted partition. Huygens et al. [START_REF] Huygens | The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut[END_REF] showed that, for any L ≥ 2, the following inequality is valid for the 2EDHP polytope.

x(δ(V 0 , V 1 , ..., V p )) ≥ (L + 1)p L .

(5.24)

For a subset Z ⊂ V with |Z| = k-2, the following inequality is valid for kNDHP(G, L).

x(δ G\Z (V 0 , V 1 , ..., V p )) ≥ (L + 1)p L .

(5.25)

st-jump inequalities

Theorem [START_REF] Chopra | The k-edge connected spanning subgraph polyhedron[END_REF] Suppose that |V | ≥ 5 and L = 3. Let (s, t) ∈ D, Z ⊂ V , and consider the partition

π = (V 0 , V 1 , ..., V 4 ) of V \ Z such that s ∈ V 0 and t ∈ V 4 . Let U i be a set of nodes of V i , i = 1, 2, 3, such that |U i | = k -1. Then the st-jump inequality 2 i=0 x([V i , V i+2 ]) + 1 i=0 4 j≥i+3 2x([V i , V j ]) + 1 i=0 x([V i , V i+1 \ U i+1 ]) + 3 i=2 x([V i \ U i , V i+1 ]) ≥ 4k + 3 5 (5.26)
is valid for the kNDHP(G, 3).

Proof. Let U 1 ⊂ V 1 , U 2 ⊂ V 2 and U 3 ⊂ V 3 and let T 1 , T 2 , T 3 and T 4 , be the L-st-path-cuts induced by (V 0 , U 1 , V 2 ∪ V 1 \ U 1 , V 3 , V 4 ), (V 0 , V 1 , U 2 , V 3 ∪ V 2 \ U 2 , V 4 ), (V 0 , V 1 ∪ V 2 \ U 2 , U 2 , V 3 , V 4 ) and (V 0 , V 1 , V 2 ∪ V 3 \ U 3 , U 3 , V 4
), respectively. Then by summing the L-st-path-cut inequalities induced by T i , i = 1, ..., 4, and the following st-node-cut inequalities induced by V 0 and U 1 , V 0 ∪ V 1 and U 2 , and V 4 and U 3 ,

x(δ G\{U 1 } (V 0 )) ≥k -1, x(δ G\{U 2 } (V 0 ∪ V 1 ))≥k -1, x(δ G\{U 3 } (V 4 )) ≥k -1,
we obtain the inequality

4 i=1 x(T i ) + x(δ G\{U 1 } (V 0 )) + x(δ G\{U 2 } (V 0 ∪ V 1 )) + x(δ G\{U 3 } (V 4 ))≥4k + 3.

This together with

x(e) ≥ 0, for all e ∈ δ(

V 1 \ U 1 , V 3 ) ∪ δ(V 2 \ U 2 , V 4 ) ∪ δ(V 1 , V 3 \ U 3 ), 3x(e) ≥ 0, for all e ∈ δ(V 0 , V 1 \ U 1 ∪ V 4 ) ∪ δ(V 1 , V 2 \ U 2 ) ∪ δ(V 3 \ U 3 , V 4 ), 4x(e) ≥ 0, for all e ∈ δ(V 0 ∪ V 2 \ U 2 ∪ V 3 ) ∪ δ(V 1 , V 4 ),
gives the inequality

2 i=0 5x([V i , V i+2 ]) + 1 i=0 4 j≥i+3 10x([V i , V j ]) + 1 i=0 5x([V i , V i+1 \ U i+1 ]) + 3 i=2 5x([V i \ {u i }, V i+1 ]) ≥ 4k + 3.
Dividing the resulting inequality by 5, and rounding up the right-hand side, we obtain inequality (5.26).

Facets of the kNDHP polytope

In this section, we investigate the conditions under which the inequalities presented in the previous section define facets of kNDHP(G, L). First, we discuss the dimension of kNDHP(G, L).

An edge e ∈ E is said to be essential if there is no solution of the kNDHP on the graph obtained by deleting the edge e from G. Therefore e is essential if and only if it belongs to either an st-cut or an L-st-path-cut of cardinality k, or, to an st-node-cut or an L-st-path-node-cut of cardinality k -|Z|. Then we have the following theorem.

Corollary 7 kNDHP(G, L) is full dimensional if G = (V, E) is complete and |V | ≥ k + 2.
In the following we assume that G is complete and has at least k + 2 nodes. By Corollary 7, kNDHP(G, L) is then full dimensional. Now we investigate the conditions under which the trivial and basic inequalities define facets.

Theorem 21 Inequality x(e) ≤ 1 defines a facet of kNDHP(G, L) for every e ∈ E.

Proof. For all f ∈ E \ {e}, consider the edge sets E f = E \ {f }. Hence, E and the edge sets E f constitute a set of |E| solutions of the kNDHP. Furthermore, their incidence vectors satisfy x(e) = 1 and are affinely independent. In what follows, we investigate the conditions under which the st-cut and the stnode-cut inequalities define facets of kNDHP(G, L).

Theorem 23

The st-cut inequalities x(δ(W )) ≥ k define facets of kNDHP(G, L) when |D| = 1.

Proof. We denote by ax ≥ α the st-cut inequality induced by W , and let F = {x ∈ kNDHP(G, L) | ax = α}. Suppose there exists a defining facet inequality bx ≥ β such that F ⊆ F ′ = {x ∈ kNDHP(G, L) | bx = β}. We will prove that there is a scalar ρ such that b = ρa. As |V | ≥ k + 2, there exists

W 1 ⊆ W \ {s} and W 2 ⊆ W \ {t} such that |W 1 | + |W 2 | = k. Let E 1 = {sv, v ∈ W 2 } ∪ {ut, u ∈ W 1 } and T 1 = E 1 ∪ E 0 where E 0 = E(W ) ∪ E(W ).
Clearly, T 1 is a solution of the kNDHP, and its incidence vector satisfies ax ≥ α with equality. Consider an edge e ∈ E 1 . It is not hard to see that T 2 = (T 1 \ {e}) ∪ {st} is a solution of the kNDHP and its incidence vector also satisfies ax ≥ α with equality. Thus bx (5.27)

T 1 = bx T 2 . Since bx T 2 = bx
Now consider an edge f = uv ∈ δ(W ) \ E 1 , with u ∈ W \ {s} and v ∈ W \ {t}. We distinguish two cases.

Case 1. u ∈ W 1 , v ∈ W 2 .
Consider T 3 = (T 1 \ {sv, ut}) ∪ {f, st}. Clearly, T 3 is a solution of the kNDHP and its incidence vector satisfies ax = α. Hence, we have that bx T 3 = bx T 1 . This implies that b(sv) + b(ut) = b(f ) + b(st). From (5.27), it follows that b(f

) = ρ. Case 2.u ∈ W 1 (resp. u ∈ W \ (W 1 ∪ {s})), v ∈ W \ (W 2 ∪ {t}) (resp. v ∈ W 2 ).
Consider the edge set T 4 = (T 1 \ {tu}) ∪ {f }. It is easy to see that T 4 is a solution of kNDHP such that ax T 4 = α. Hence bx T 4 = β. As bx

T 1 = β, it follows that b(f ) = b(tu) = ρ.
If u ∈ W \ (W 1 ∪ {s}) and v ∈ W 2 we also obtain by symmetry that b(f ) = ρ.

Thus, together with (5.27) we obtain that b(e) = ρ for all e ∈ δ(W ). Now consider an edge e ∈ E 0 , and suppose, w.l.o.g., that e ∈ E(W ). If e does not belong to an L-st-path of T 1 , then the edge set T 5 = T 1 \ {e} also induces a solution of the kNDHP and satisfies ax T 5 = α. Hence we have that bx T 5 = bx T 1 implying b(e) = 0. If e belongs to an L-st-path of T 1 , say (su, ut) where e = su, then the edge set T 6 = (T 1 \{su, ut})∪{st} induces a solution of the kNDHP, and its incidence vector satisfies ax T 6 = α. Consequently bx T 7 = bx

The edge sets T

i = T ′ i ∪ δ(Z) ∪ E(Z)
, for all i ∈ {1, ..., m ′ }, induce solutions of the kNDHP. Indeed, since G is complete, the paths (s, z, t), z ∈ Z, form a set of |Z| st-paths of length 2 in G. As these st-paths are node-disjoint and do not intersect V \ (Z ∪ {s, t}), they form with the s-paths of T ′ i a set at least k node-disjoint st-paths in G, for i = 1, ..., m ′ . Which implies that T i , i = 1, ..., m ′ are solutions of kNDHP. Furthermore, their incidence vectors satisfy x(δ G\Z (W )) = k -|Z| and are affinely independant.

Let a ′ and b ′ be the restriction on E \ (δ(Z) ∪ E(Z)) of a and b, respectively. Thus, we have a ′ x T i = α, for i = 1, ..., m ′ . Therefore, b ′ x T i = β, for i = 1, ..., m ′ . As x T i , i = 1, ..., m ′ , are affinely independent and α = 0, it follows that x T i , i = 1, ..., m ′ , are linearly independent. Consequently, a is the unique solution of the system a ′ x T i = α, for i = 1, ..., m ′ . Let ρ be such that β = ρα. It then follows that b ′ = ρa ′ . This implies that b(e) = 0 for all e ∈ E(W ) ∪ E(W ). Now we will show that b(e) = 0 for all e ∈ δ(Z) ∪ E(Z). Let us denote the edges of

E(Z) ∪ δ(Z) \
ax T m ′ = ax Γ m ′ +j = α, it follows that bx T m ′ = bx Γ m ′ +j = β. Hence, b(e j ) = 0 for j = 1, ..., |δ(Z)| + |E(Z)| -2|Z|.
Let T 1 be the set among T 1 , ..., T m ′ containing the edge st. Such a set exists since the inequality defines a facet of kNDHP(G\, L) on G \ Z different from a trivial inequality.

As W \{s} = ∅ = V \((W ∪Z)\{t}). Let u 1 ∈ W \{s}, u 2 ∈ (V \(W ∪Z))\{t} and z ∈ Z.
Consider the edge sets T 0 = (T 1 \ {sz}) ∪ {su 1 , u 1 z} and T ′ 0 = (T 1 \ {zt}) ∪ {sz, zu 2 }. T 0 and T 1 are solutions of the kNDHP (Recall that the path (sz, zt) belongs to T i ). Moreover we have ax In what follows we describe conditions under which the L-st-path and L-node-st-path cut inequalities define facets when L = 3.

T 0 = ax T 1 = α. Thus bx T 1 = bx T 0 = bx T ′ 0 = β. As b(su 1 ) = b(u 1 z) = b(zu 2 ) = b(u 2 t) = 0,
Theorem 25 If |D| = 1, a 3-st-path inequality (5.2) induced by a partition π = (V 0 , ...V 4 ) with s ∈ V 0 and t ∈ V 4 , defines a facet of kNDHP(G, 3) if and only if

(1) |V 0 | = |V 4 | = 1, (2) |[s, V 1 ]| + |[V 3 , t]| ≥ k.
Proof. Let T be the 3-path-cut induced by π = (V 0 , ..., V 4 ) such that s ∈ V 0 and t ∈ V 4 . Let us denote by ax ≥ α the L-st-path inequality induced by T , and let

F = {x ∈ kNDHP(G, 3) | ax = α}.
Necessity. (1) We will show that if |V 0 | ≥ 2, inequality x(T ) ≥ k does not define a facet. The case where |V 4 | ≥ 2 follows by symmetry. Suppose that |V 0 | ≥ 2 and consider the partition π ′ = (V ′ 0 , ..., V ′ 4 ) given by

V ′ 0 = {s}, V ′ 1 = V 1 ∪ (V 0 \ {s}), V ′ i = V i , i = 2, 3, 4.
The partition π ′ produces a 3-path-cut inequality x(T ′ ) ≥ k, where

T ′ = T \ [V 0 \ {s}, V 2 ]. Since G is complete, [V 0 \ {s}, V 2 ] = ∅ and T ′ is strictly contained in T . Thus, x(T ) ≥ k is redundant with respect to the inequalities x(T ′ ) ≥ k, x(e) ≥ 0 for all e ∈ [V 0 \ {s}, V 2 ],
and cannot define a facet.

(2) Suppose that Condition 1) holds, and that F is a facet of kNDHP(G, 3) different from a trivial inequality. Thus there exists a solution F of the kNDHP such that

x F ∈ F and F ∩ [V 1 , V 3 ] = ∅.
If this is not the case, then F would be equivalent to a facet defined by any of the inequalities x(e) ≥ 0, e ∈ [V 1 , V 3 ]. Note that, since each 3-st-path of F intersects T at least once and |F ∩T | = k, F necessarily contains exactly k node-disjoint 3-st-paths. Moreover, each of these paths intersects T only once. If u i is a node of V i , i = 1, ..., 3, this implies that every 3-st-path of F is of the form (i) (su 1 , u 1 u 2 , u 2 t), (su 2 , u 2 u 3 , u 3 t), (su 1 , u 1 t), (su 3 , u 3 t), (st) or (ii) (su 1 , u 1 u 3 , u 3 t).

If P is one of these st-paths, then |P ∩ A| = 1 (resp. |P ∩ A| = 2) if P is of type (i) (resp. (ii)), where A = [s, V 1 ] ∪ [V 3 , t] ∪ {st}. As F ∩ [V 1 , V 3 ] = ∅, it follows that F contains at least one path of type (ii) and therefore |F ∩ A| ≥ k + 1. Hence |[s, V 1 ]| + |[V 3 , t]| ≥ k.
Sufficiency. Suppose that Conditions (1) and (2) hold. Now suppose that there exist a facet defining inequality bx ≥ β such that F ⊆ {x ∈ kNDHP(G, 3) | bx = β}. As before, we will show that there exists a scalar ρ = 0 such that b = ρa.

As |[s, V 1 ]| + |[V 3 , t]| ≥ k, there exist two node sets U 1 ⊆ V 1 and U 3 ⊆ V 3 such that |U 1 |+|U 3 | = k.
Consider the edge subset S 1 formed by the st-paths (su, ut), u ∈ U 1 ∪U 3 .

Clearly these st-paths form a set of k node-disjoint 3-st-paths. Moreover, each of these paths intersects T only once. Thus S 1 induces a solution of kNDHP and its incidence vector belongs to F . Let e ∈ S 1 ∩T . Let S 2 = (S 1 \ {e}) ∪{st}. Since S 2 is a solution of the kNDHP whose incidence vector belongs to F , we have bs S 2 = bx S 1 = β, implying that b(e) = b(st). As e is an arbitrary edge, we obtain that b(e) = ρ for all e ∈ (S 1 ∩ T ) ∪ {st}, for some ρ ∈ R.

(5.28)

Consider now e ∈ E \ T . If e / ∈ S 1 , clearly S 3 = S 1 ∪ {e} is a solution of kNDHP. Moreover, its incidence vector belongs to F . Hence, b(e) = bx S 3bx S 1 = 0. If e ∈ S 1 \ T , then e is either of the form su, u ∈ U 1 , or vt, v ∈ U 3 . Suppose, w.l.o.g., that e = su, the case where e = vt is similar. Note that, by the definition of S 1 , ut also belongs to S 1 . Let S 4 = (S 1 \ {su, ut}) ∪ {st}. We have that S 4 induces a solution of the kNDHP and x S 4 ∈ F . Hence, bx S 4 = bx (

Now let e ∈ T \ S 1 . Suppose that e = sv with v ∈ V 2 . The case where e ∈ [V 2 , t] is similar. By construction S 1 contains an st-path of the form (su 3 , u 3 t) where u 3 is a node of V 3 . Then the edge set S 5 = (S 1 \ {su 3 }) ∪ {e, vu 3 } is a solution of the kNDHP whose incidence vector belongs to F . Thus, b S 5b S 1 = b(e) + b(vu 3 )b(su 3 ) = 0. From (5.28) and (5.29), we then get b(e) = ρ.

Let e = sv with v ∈ V 3 . The case where e ∈ [V 1 , t] is similar. Consider the edge set S 6 = (S 1 \ {su 3 }) ∪ {e, vt}, where u 3 is a node of U 3 , which induces a solution of the kNDHP. Moreover, its incidence vector belongs to F . Hence bx Therefore, b = ρa, and the proof is complete.

Theorem 26 If |D| = 1, a 3-st-node-path-cut inequality (5.4) induced by a node subset Z ⊂ V , such that |Z| ≤ k -1, and a partition π = (V 0 , ...V 4 ) of V \ Z, with s ∈ V 0 and t ∈ V 4 , defines a facet of kNDHP(G, 3) if and only if

(1) |V 0 | = |V 4 | = 1, (2) |[s, V 1 ]| + |[V 3 , t]| ≥ k -|Z|.
Proof. The idea of the proof is the same as that used in proving Theorem 24. We can also use the fact that a 3-st-node-path-cut inequality, x(T G\Z ) ≥ k -|Z|, for some 3-stpath-cut T and some node set We will denote them by H l , l = 1, ..., k-|Z|. Moreover, as G is complete, the edges sz and zt, for all z ∈ Z, are in G, and the sets (s, z, t), z ∈ Z, form |Z| st-paths of length 2 in G. Hence the paths H l , l = 1, ..., k -|Z| and (s, z, t), z ∈ Z, are node-disjoint. Thus, the sets S i , i = 1, ..., n ′ induce n ′ solutions of the kNDHP on G. Furthermore, their incidence vectors satisfy x(T G\Z ) = k -|Z|.

Z ⊂ V \{s,
Let a ′ and b ′ be the restriction on E \ (δ(Z) ∪ E(Z)) of a and b, respectively. Thus, we have a ′ x S i = α, for i = 1, ..., n ′ . Therefore, b ′ x S i = β, for i = 1, ..., n ′ . As x S i , i = 1, ..., n ′ , are affinely independent and α = 0, it follows that x S i = 0, i = 1, ...n ′ , and hence, x S i , i = 1, ..., n ′ , are linearly independent. Consequently, a is the unique solution of the system a ′ x S i = α, for i = 1, ..., n ′ . Let ρ be such that β = ρα. Let S 1 be the set among S 1 , ..., S n ′ containing the edge st. Such a set exists since, as noted before,

x S i = 0 for i = 1, ..., n ′ . Let u 1 ∈ V 1 , u 2 ∈ V L and z ∈ Z.

Lemma 10 The double cut inequality induced by the node sets

V 1 0 , V 2 0 ∪ V 1 , V 2 , ..., V L+1 of V \ Z, F ⊆ E and {s, t} ∈ D with s ∈ V 1
0 and t ∈ V L+1 , can be written as

x(T G\Z ) + x(δ G\Z (V 1 0 ∪ V 2 0 )) + x(δ G\Z (V 1 )) + x(E \ F ) -x(F ) + |F | ≥ 3(k -|Z|) + 1 (5.31)
where T G\Z is the L-st-node-path-cut induced by the partition (V 1 0 , V 2 0 ∪V 1 , V 2 , ..., V L+1 ). Moreover, the double cut inequality (5.13) is tight for a solution x ∈ R E if and only if one of the following conditions holds.

i) x(E \ F ) -x(F ) + |F | = 1 and x(T G\Z ) = x(δ G\Z (V 1 0 ∪ V 2 0 )) = x(δ G\Z (V 1 )) = k -|Z|; ii) x(E \ F ) -x(F ) + |F | = 0 and a) x(T G\Z ) = k -|Z| + 1, x(δ G\Z (V 1 0 ∪ V 2 0 )) = k -|Z| and x(δ G\Z (V 1 )) = k -|Z|; b) x(T G\Z ) = k -|Z|, x(δ G\Z (V 1 0 ∪ V 2 0 )) = k -|Z| + 1 and x(δ G\Z (V 1 )) = k -|Z|; c) x(T G\Z ) = k -|Z|, x(δ G\Z (V 1 0 ∪ V 2 0 )) = k -|Z| and x(δ G\Z (V 1 )) = k -|Z| + 1;
Proof. Let C be the double cut inducing inequality (5.13). Then inequality (5.13) can be written as

x(C \ E) + x(E \ F ) ≥ 3(k -|Z|) -|F | + 1 2 . Thus we have 2x(C \ E) + 2x(E) -2x(F ) ≥ 3(k -|Z|) -|F | + 1. (5.32)
By summing the left hand side of the L-st-node-path-cut inequality induced by T G\Z and the node-cut inequalities induced by δ G\Z (V 1 0 ∪ V 2 0 ) and δ G\Z (V 1 ), we obtain

x(T G\Z ) + x(δ G\Z (V 1 0 ∪ V 2 0 )) + x(δ G\Z (V 1 )) = 2x(C \ E) + x(E).
(5.33)

By combining (5.32) and (5.33), we get

x(T G\Z ) + x(δ G\Z (V 1 0 ∪ V 2 0 )) + x(δ G\Z (V 1 )) + x(E) -2x(F ) ≥ 3(k -|Z|) -|F | + 1. Therefore x(T G\Z ) + x(δ G\Z (V 1 0 ∪ V 2 0 )) + x(δ G\Z (V 1 )) + x(E \ F ) -x(F ) + |F | ≥ 3(k -|Z|) + 1.
Hence, the double cut inequality (5.13) is equivalent to (5.31).

Suppose that the double cut inequality is tight for a solution x, that is In this section, we present a Branch-and-Cut algorithm for the kNDHP when L = 3. First, we present the general framework of the algorithm and then present the separation procedures we have devised for the inequalities involved in the algorithm.

x(T G\Z ) + x(δ G\Z (V 1 0 ∪ V 2 0 )) + x(δ G\Z (V 1 )) + x(E \ F ) -x(F ) + |F | = 3(k -|Z|) + 1

The general framework

Our algorithm starts by solving the linear relaxation of Formulation (5.7), that is, min{cx | x ∈ R E + satisfies (5.1) -(5.6)}. (6.1)

Since inequalities (5.1), (5.2), (5.3) and (5.4) are exponential in number in (6.1), we solve this linear relaxation using the so-called cutting plane method. We recall that the cutting plane method finds an optimal solution of a linear program by solving a series of LPs, each of them containing a subset of the constraints of the original LP. For our purpose, the algorithm starts with an LP containing the cut constraints (5.1) induced by terminal nodes and the trivial inequalities (5.5) and (5.6)

Min e∈E c(e)x(e) s.t. x(δ(u)) ≥ k, for all u ∈ R D ,
x(e) ≥ 0, for all e ∈ E,

x(e) ≤ 1, for all e ∈ E.

Then, it iteratively adds the inequalities (5.1)-(5.4) that are violated by the solution x * of the current LP. The cutting plane algorithm stops when all the inequalities (5.1)-(5.4) are satisfied by x * . In this case, x * is optimal for (6.1). For finding inequalities (5.1)-(5.4) that are violated by x * , if there is any, we solve the so-called separation problem associated with these inequalities. Recall that the separation problem associated with a family of inequalities F and a solution x is to verify if x satisfies all the inequalities of F, and if not, to exhibit at least one of them which is violated by x. An algorithm solving a separation problem is called a separation algorithm.

At the end of the cutting plane algorithm, if x * is integral, then it is optimal for the problem (5.7). If x * is fractional, then we reinforce the linear relaxation of the problem by adding, if possible, further valid inequalities. For this, we also add the Steiner SPpartition inequalities (5.19), the double cut inequalities (5.11) and the Steiner partition inequalities (5.17) in the cutting plane algorithm. The separation of the inequalities used in the Branch-and-Cut algorithm are performed in the following order 1) st-cut and L-st-path-cut inequalities, Notice that the st-node-cut and L-st-node-path-cut inequalities are separated only for integral solutions. Indeed, as we will see in the next subsection, these two families of inequalities can be efficiently separated when the solution x * is integral.

All the inequalities that are added during the Branch-and-Cut algorithm are considered as global (i.e., valid at every node of the Branch-and-Cut tree) and we may add several inequalities at each iteration. Furthermore, we proceed to the separation of a class of inequalities only when the separation of the previous class of inequalities has not found any violated inequalities.

In the following, we describe the separation algorithms we have devised for the inequalities (5.1)-(5.4), the Steiner SP-partition inequalities (5.19), the double cut inequalities (5.11) and the Steiner partition inequalities (5.17).

Separation procedures

Separation of st-cut and 3-st-path-cut inequalities

We discuss first the separation of the st-cut and 3-st-path-cut inequalities (5.1) and (5.2). We give the theorem below which shows that the separation problem of these inequalities reduces to computing a maximum flow in a special graph, and hence can be solved in polynomial time.

Theorem 28

The separation problem of st-cut and 3-st-path-cut inequalities (5.1) and (5.2) reduces to computing maximum flows in a special graph and can be solved in

O(|D||E| 2 |V |) time. Graph Gs 1 ,t 1 Graph Gs 1 ,t 2 Graph Gs 3 ,t 3 s 1 t 1 t 2 s 3 u t 3 Graph G t 3 s 3 t 2 u u ′ t ′ 2 s ′ 3 t ′ 3 t 1 s 1 t 1 t 3 u s 3 t ′ 1 u ′ t ′ 3 s ′ 3 s 1 t 2 s 1 t 1 u t 2 t ′ 1 s ′ 1 u ′ t ′ 2 s 3 t 3 Figure 6
.1: Construction of graphs G st with D = {(s 1 , t 1 ), (s 1 , t 2 ), (s 3 , t 3 )}.

Proof. Let x ∈ R E be the solution for which we are separating the natural inequalities (5.1) and (5.2). To separate them, we consider the following graph transformation from [START_REF] Bendali | The k edge-disjoint 3-hop-constrained paths polytope[END_REF] (see also [START_REF] Diarrassouba | Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem[END_REF]). Let (s, t) ∈ D and let V st = V \ {s, t}, V ′ st be a copy of V st and

V st = V st ∪ V ′ st ∪ {s, t}.
The copy in V ′ st of a node u ∈ V st will be denoted by u ′ . From G and (s, t), we build the directed graph G st = ( V st , A st ). Its arc set A st is obtained as follows. For an edge of the form st ∈ E, we add an arc (s, t) in A st . For each edge su ∈ E, u = t, (resp. vt ∈ E, v = s), we add in A st an arc (s, u), u ∈ V st (resp. (v ′ , t), v ′ ∈ V ′ st ). For each edge uv ∈ E, with u, v / ∈ {s, t}, we add two arcs (u, v ′ ) and (v, u ′ ) in A st , with u, v ∈ V st and u ′ , v ′ ∈ V ′ st . Finally, for each node u ∈ V \ {s, t}, we add an arc (u, u ′ ) in A st (see Figure 6.1 for an illustration).

Notice that for each (s, t)

∈ D, | V st | = 2|V |-2 and | A st | = 2|E|-|δ(s)|-|δ(t)|+|[s, t]|.
Bendali et al. [START_REF] Bendali | The k edge-disjoint 3-hop-constrained paths polytope[END_REF] showed that there is a one-to-one correspondence between the st-cuts and the 3-st-path-cuts in G and the st-dicuts in G st which do not contain arcs of the form (u, u ′ ), for all u ∈ V \ {s, t}. Moreover, if each arc a ∈ A st , corresponding to an edge e ∈ E, is assigned the capacity c(a) = x(e) and each arc of the form (u, u ′ ) is assigned an infinite capacity, then the weight of an st-cut or 3-st-path-cut in G with respect to x is the same as that of the corresponding st-dicut in G st with respect to capacity vector c. Thus, for a given (s, t) ∈ D, there is an st-cut or 3-st-path-cut inequality violated by x if and only if there is an st-dicut in G st whose capacity is < k. Moreover, if there is a violated st-cut or 3-st-path-cut inequality induced by an edge set C ⊆ E, that is there is an st-dicut C ⊆ A st whose weight is < k, then the edges of C are those corresponding to the arcs of C. Therefore, the separation problem of the st-cut and the 3-st-path-cut inequalities reduces to computing a minimum st-dicut in G st with respect to the capacity vector c. By the Max Flow-Min Cut Theorem, this can be done by computing a maximum flow from s to t in G st .

Finally, the maximum flow computation in G st can be handled by the Edmonds-Karp algorithm [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF]

which runs in O(| A st | 2 | V st |) = O(|E| 2 |V |) time.
Since this procedure is performed |D| times (one for each demand), the whole separation algorithm can be implemented to run in O(|D||E| 2 |V |) time, and hence is polynomial.

Our separation algorithm for st-cut and 3-st-path-cut inequalities is based on Theorem 28. It starts, for each demand (s, t) ∈ D, by building the graph G st and then, computing a minimum weight st-dicut, say C, w.r.t. weight vector c. If the weight of such a st-dicut is < k, then the edge set C of G corresponding to the arcs of C corresponds to either a st-cut or a 3-st-path-cut which induces a violated inequality. The separation algorithm stops when it finds, for a given demand, a violated inequality or when all the demands have been considered without finding any violated inequality. From Theorem 28, this algorithm solves the separation problem of inequalities (5.1) and (5.2) in polynomial time.

Separation of st-node-cut and 3-st-node-path-cut inequalities

Now, we discuss the separation problem of st-node-cut and 3-st-node-path-cut inequalities (5.3) and (5.4). As mentionned before, we consider the separation problem of these inequalities only in the case where the considered solution x ∈ R E is integral. We restrict to this case because first, in order to guarantee that the B&C algorithm is correct, it is enough to separate the st-node-cut and 3-st-node-path-cut inequalities for integral solutions, only. Also, as we will see below, inequalities (5.3) and (5.4) can be separated in polynomial time when x is integral. Thus, suppose that x is integral, and w.l.o.g., satifies all the st-cut and 3-st-path-cut inequalities (5.1) and (5.2). Under these assumptions, solving the separation problem of inequalities (5.3) and (5.4) consists in saying if x is feasible for the kNDHP or not. Indeed, on one hand, if x is feasible, then it satisfies all the st-node-cut and 3-st-node-path-cut inequalities. On the other hand, if x is not feasible for the kNDHP, then for some demand (s, t) ∈ D, there exists a node set Z ⊆ V such that |Z| ≤ k -1, and an st-node-cut or a 3-st-node-path-cut C of G w.r.t. Z such that x(C) < k -|Z|. Thus, the aim of our separation algorithm is to say if the subgraph of G induced by x contains, for each (s, t) ∈ D, k node-disjoint 3-st-paths, and if not, find node set Z and an st-node-cut or a 3-st-node-path-cut w.r.t. induces a st-node-cut or 3-st-node-path-cut inequality violated by x. Now suppose that |Z| ≥ k. By the construction procedure of Z, the subgraph of G induced by x contains edges of the form su and ut, for every node u ∈ Z, which form |Z| paths (s, u, t). Clearly, these paths are node-disjoint, and hence, the subgraph of G induced by x contains |Z| ≥ k node-disjoint 3-st-paths. Consequently, x satisfies all the st-node-cut and 3-st-node-path-cut inequalities.

Finally, suppose that |Z| ≤ k -1 and f = c(δ + Gst\ Z ( W )) ≥ k -|Z|, where W induces a minimum weight st-dicut of G st \ Z, w.r.t. to weight vector c. As before, by the construction procedure of Z, the subgraph of G induced by x contains |Z| node-disjoint 3-st-paths. Also, the construction of Z implies the graph G st \ Z contains f arc-disjoint st-dipaths which correspond to f node-disjoint 3-st-paths of G. Moreover, these later node-disjoint 3-st-paths are node-disjoint from those induced by Z. Consequently, the subgraph of G induced by x contains f + |Z| ≥ k -|Z| + |Z| = k node-disjoint 3-st-paths, which implies that x satisfies all the st-node-cut and 3-st-node-path-cut inequalities. Now we describe our separation algorithm for st-node-cut and 3-st-node-path-cut inequalities when x is integral and satisfies all the st-cut and 3-st-path-cut inequalities. For each demand (s, t) ∈ D, we build the graph G st and let c be the associated weight vector. Then we build, using Procedure BuildZ, the node set Z and let f be the weight of a minimum weight cut of G st \ Z, w.r.t. weight vector c. If |Z| ≤ k -1 and f < k -|Z|, then, by Theorem 29, there is an st-node-cut or a 3-st-node-pathcut C ⊆ E which induces an inequality (5.3) or (5.4) violated by x. If |Z| ≥ k or f ≥ k -|Z|, then we move to another demand. The algorithm stops when it has found a violated inequality (5.3) or (5.4) for some demand (s, t) ∈ D or when all the demands have been explored without finding any violated inequality.

The separation algorithm can be implemented to run in O(|D|k|E| 2 |V |) time, which is polynomial.

Separation of double cut, Steiner SP-partition and partition inequalities

Now we consider the separation of Inequalities (5.11), (5.19) and (5.17). For our purpose, we look for those inequalities (5.11), (5.19) and (5.17) defined with a node set Z = ∅. To separate them, we use the separation heuristics developed in [START_REF] Diarrassouba | Survivable network design problems with high connectivity requirements[END_REF].

The heuristic developed for the double cut inequalities is implemented to run in

O |V | 3 log |V | (2|V |+|Dsource|+|D dest |) 2 (|V |-1)(|V |+|Dsource|+|D dest |) time.
Here D source and D dest denote the sets of nodes which are, respectively, the source and destination in a demand, which is polynomial.

For SP-partition inequalities (5.19), the heuristic proposed by [START_REF] Diarrassouba | Survivable network design problems with high connectivity requirements[END_REF] is implemented to run in O(|V ||E| + |D|), while the separation heuristic for partition inequalities (5.17) proposed by [START_REF] Diarrassouba | Survivable network design problems with high connectivity requirements[END_REF] is implemented to run in O(|V ||E| + |R| 2 (|E| + |D|)), where R is the set of terminal nodes.

Clearly, the three heuristics run in polynomial time.

Computational Results

We have implemented our Branch-and-Cut algorithm in C++, using CPLEX 12.5 and Concert Technology [3]. It was tested on a Xeon Quad-Core E5507 machine with a 2.27 GHz processor and 8GB RAM, running under Linux. The maximum CPU time has been fixed to 5 hours. Each instance is composed of a graph from TSPLIB [2] and a set of demands. TSPLIB graphs are complete Euclidean graphs, that is each node is assigned coordinates in the plane, and the weight of each edge is given by the Euclidean distance between its endnodes. The demands used in the instances are randomly generated. Each set of demands is either rooted, that is, of the form {(s, t i ) : i = 1, ..., d} (s is the root node of the demands), or arbitrary. The computational results are given in Tables 6.1-6.6. Each instance is described by the number of nodes of the graph and the number of demands. The number of nodes is preceded either by "r" if the demands are rooted or "a" if they are not rooted. The entries of the various tables presented below are: Note that for some instances, the algorithm spends all the CPU time (5 hours) without finding any feasible solution. In this case, the best upper bound (COpt) and the error with the lower bound achieved at the root node of the Branch-and-Cut tree (Gap) are indicated with "-".

Our first series of experiments concerns the kNDHP with k = 3 and L = 3. The results are given in Tables 6.1 and 6.2. We can see that for the rooted instances (Table 6.1), the algorithm has solved to optimality 4 instances out of 13, with graphs having up to 30 nodes and with 15 demands, and the CPU time varying from 4 minutes to 18 minutes. The gap achieved between the best upper bound (that is, the optimal solution) and the lower bound at the root node of the Branch-and-Cut tree (Gap) is relatively small (less than 10%) for these instances. For the instances that have not been solved to optimality, the value of the gap are also relatively small: less than 10% for 5 of them and less 31% for the 4 other instances. Table 6.1 also shows that a very large number of st-cut and 3-st-path-cut inequalities have been generated during the resolution. Also, a large number of st-node-cut and 3-st-node-path-cut inequalities have been generated for all the instances. We can also see that several Steiner SP-partition have been generated but no double cut and Steiner partition inequalities have been generated.

For the arbitrary demands, the algorithm has solved to optimality only one instance (d-21-11) over nine and has spent all the CPU for the other instances. Also, it has not found even a feasible solution for 5 instances. For the instances r-21-10, d-30-10 and d-30-15, that have not been solved to optimality, the gap between the lower bound at the root node of the Branch-and-Cut tree and the best upper bound is less than 12%. We can also see, as for the rooted instances, that a very large number of st-cut and 3-stpath-cut inequalities have been generated, but less st-node-cut and 3-st-node-path-cut inequalities have been generated. We can also notice that some Steiner SP-partition and a quite large number of double cut inequalities have been generated in the resolution.

Our next series of experiments concerns the kNDHP with k = 4 and L = 3. The results are given in Tables 6.3 and 6.4. Notice that in this case, the Steiner SP-partition and Steiner partition inequalities are not included in the Branch-and-Cut algorithm as they are redundant w.r.t. st-cut inequalities. Thus, the corresponding columns in Tables 6.3 and 6.4 are omitted. The results of Table 6.3 show that for the rooted instances, 4 instances over 13 have been solved to optimality. For the other instances, the gap is less than 9% for three instances and less than 22% for six instances. The results also show that a very large number of st-cut and 3-st-path-cut inequalities are generated while a large number of st-node-cut and 3-st-node-path-cut inequalities are generated for all the instances. Also, no double cut inequalities are generated for all the instances we have considered.

For arbitrary demands (Tables 6.4), all the instances have not been solved to optimality within the CPU time limit. Also, for five instances (from d-48-15 to d-52-26) over nine, the algorithm has not found a feasible solution. For the others, the gap is less than 13%. Contrarily to rooted demands, a quite large number of double cut inequalities have been generated. Now we turn out attention to the resolution of the kNDHP with k = 5 and L = 3. The results are given in Tables 6.5 and 6.6 below. We can see from Table 6.5, that for the rooted instances, the algorithm has solved to optimality three instances over 13. For the other ten instances, the gaps is less than 10%, for only three of them. For the remaining instances, the gaps are between 10% and 35%. Also, we notice that a large number of st-cut, 3-st-path-cut, st-node-cut and 3-st-node-path-cut inequalities are generated. However, no Steiner SP-partition, double cut and Steiner partition inequalities are generated. For the arbitrary demands (Table 6.6), all the instances have not been solved to optimality, and, for four instances, the algorithm has not found a feasible solution. We also notice that few Steiner SPpartition and Steiner partition inequalities and a quite large number of double cut inequalities have been generated.

In these experiments, we have also tried to check the impact of the different classes of inequalities we have considered in our algorithm. As we can see in the various tables, Steiner SP-partition and double cut inequalities are generated in quite large number, and very few Steiner partition inequalities are found. We also observe that in the three cases k = 3, 4, 5, the double cut inequalities are not generated when the demands are rooted, and several of them are generated when the demands are arbitrary. In contrast with double cut inequalities, Steiner SP-partition inequalities are mainly generated when the demands are rooted, and few of them are generated for arbitrary demands. This observation can be compared with those of Diarrassouba et al. [START_REF] Diarrassouba | Two node-disjoint hopconstrained survivable network design and polyhedra[END_REF] who devised a Branch-and-Cut algorithm for the kNDHP with k = 2. In their experiments, they showed that the double cut inequalities were mainly generated when the demands are arbitrary. This suggests that the double cut inequalities (5.11) are mainly involved in the resolution of the problem when the demands are arbitrary, and when the demands are rooted, Steiner SP-partition inequalities may play an important role in solving the problem.

To conclude this experimental study, we have checked the impact of the connectivity on the resolution of the problem. Such a comparison has been made by Bendali et al. [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF], for the k-edge-connected subgraph problem, and by Diarrassouba et al. [START_REF] Diarrassouba | Integer programming formulations for the k-edge-connected 3-hop-constrained network design problem[END_REF], for the kEHDP, that is the hop-constrained survivable network design problem in which the L-st-paths are required to be edge-disjoint, for each demand (s, t) ∈ D. In both studies, the computational results suggest that the problem becomes easier to solve when the connectivity increases. However, for the kNDHP, our computational results do not allow to make the same conclusion. Indeed, by comparing Tables 6.1, 6.3 and 6.5, we can see that most of the instances that have not been solved to optimality for k = 3 have also not been solved to optimality for k = 4 and k = 5. Also, the number of nodes in the Branch-and-Cut tree is quite large in the three cases. Also, the different gaps achieved do not allow to see if the problem becomes easier when k increases. In fact, for some instances, like r-21-20, the gap decreases as k increases, while for some other instances, like r-30-15, the gap is better when k = 4 than when k = 3 and k = 5. Even, for some instances, like r-48-20, the gaps increase as k increases. The observations are the same for the arbitrary demands, that is, we cannot conclude from Tables 6.2, 6.4 and 6.6 that the resolution of the kNDHP becomes easier when the connectivity k increases. for all z ∈ V \ {s, t}) with respect to weight vector y. Indeed, there is a violated cut inequality (5.1) (resp. st-node-cut inequality (5.3)) if and only if the minimum weight of a cut, w.r.t. weight vector y, is < 2 (resp. < 1). One can compute a minimum weight cut in polynomial time by using any minimum cut algorithm, and especially by using the Gomory-Hu algorithm [START_REF] Gomory | Multi-terminal network flows[END_REF] which computes the so-called Gomory-Hu cut tree. This algorithm consists in |V | -1 maximum flow computations.

6.2.2.2

Separation of 4-st-path-cut and 4-st-node-path-cut inequalities Now, we discuss the separation problem of 4-st-path-cut and 4-st-node-path-cut inequalities (5.2) and (5.4). As mentionned before, we consider the separation problem of these inequalities only in the case where the considered solution x ∈ R E , is integral. The idea is similar to the one presented in the proof of the formulation in [START_REF] Huygens | Integer programming formulations for the two 4-hop-constrained paths problem[END_REF]. Consider an edge subset F ⊆ E, and let G F be the graph induced by F . First we compute a Dijkstra algorithm to obtain a shortest st-path (in number of hops), say P 0 , in G. If |P 0 | > 4, then we detect a violated 4-path-cut inequality. We define V i , i = 0, ..., 4, as the subset of nodes at distance i from s in G, and V 5 = V \ ( 4 i=0 V i ). We add the corresponding 4-path-cut inequality induced by the partition (V 1 , ..., V 5 ) to the LP. If |P 0 | ≤ 4, then we look for a second shortest path in G \ {st}, say P 1 , such that P 0 and P 1 are node-disjoint. If |P 1 | ≤ 4, then F induces a solution for the 2NDHP. If |P 1 | > 4, there are two cases. The first case is when |P 0 | = 1, that is P 0 = (st), we define a 4-path-cut inequality in the same way as in the previous case, and we add the violated inequality to the LP. The second case is when |P 0 | > 1, in that case we remove the nodes of P 0 , say v P 0 i , i = 1, ..., |P 0 |, one by one, then we define the corresponding 4-node-path-cuts in G \ v P 0 i in the same way, and add them to the LP.

Separation of rooted partition inequalities

To separate inequalities (5.25), we use the separation heuristic presented in [START_REF] Huygens | The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut[END_REF]. This heuristic has been implemented to run in polynomial time.

Computational results

The same computational environment presented in the previous section is used for these experiments. Note that the rooted partition inequalities (5.25) are only used for the instances with rooted demands.

The computational results are given in Tables 6.7 and 6.8. The entries of these two tables are the same as those of Section 6.1.3, except for Table 6.8, for which we add the entry RP : the number of generated rooted partition inequalities. We can see that for the rooted demands (Table 6.8), the algorithm has solved to optimality 7 instances out of 19 within the time limit. We can observe that the gaps obtained are quite large for most of the instances, but it is less than 30% for the relatively small instances. Table 6.8 also shows that a very large number of st-cut and 3-st-path-cut inequalities have been generated during the resolution, and a large number of st-node-cut and 3-st-node-path-cut inequalities have been generated for all the instances. We can also see that several rooted partition inequalities have been generated for some instances. For the arbitrary demands, the algorithm has solved to optimality 6 instances, with graphs having up to 14 nodes and with 7 demands, and has spent all the CPU for the other instances. We can also see, as for the rooted demands, that a very large number of st-cut and 3-st-path-cut inequalities have been generated, and as much st-node-cut and 3-st-node-path-cut inequalities have been generated. We also note that the number of nodes in the Branch-and-Cut tree is quite large for the two types of demands. Also, the different gaps achieved are important for the big instances. Finally, we notice that for the arbitrary demands, the algorithm ran out of memory for 4 instances, and did not find a feasible solution.

Conclusion

In this chapter, we have studied the k-Node-Disjoint Hop-Constrained Network Design Problem (kNDHP) when L ∈ {2, 3, 4}. We have introduced an integer programming formulation for the problem when L ∈ {2, 3} and investigated the associated polytope.

Conclusion 123

We have presented several classes of valid inequalities and presented conditions under which these inequalities define facets. Then, we have devised a Branch-and-Cut algorithm for solving the problem based on the inequalities we have presented before. In particular, we have discussed the separation problem of the st-cut, 3-st-path-cut, st-node-cut, 3-st-node-path-cut inequalities, as well as that of the Steiner SP-partition, Steiner partition and double cut inequalities. Finally, we have presented Branch-and-Cut and computational results for the problem when L = 3 and k = 3, 4, 5 on one hand, and when L = 4 and k = 2 on the other hand.

The experiments we have done in this chapter have shown that the Branch-and-Cut algorithm is quite efficient for solving the kNDHP when L = 3 and k = 3, 4, 5, and this, for both rooted and arbitrary sets of demands. They also pointed out that the large size instances are still difficult to solve within 5 hours of CPU time, but the gaps achieved, are in most cases quite interesting. Moreover, the experiments have shown the importance of Steiner SP-partition and double cut inequalities (5.17) and (5.11) are important in solving the problem, and that Steiner partition inequalities (5.19) seems to be less effective.

It should also be noticed that, contrarily to the survivable network design problem without hop constraints (or the kNCSP with L ≥ |V | -1), our experiments cannot permit to conclude on the impact of an increasing of the connectivity k on the resolution of the problem. In fact, previous experiments done for the survivable network design problem (see [START_REF] Bendali | A branch-and-cut algorithm for the k-edge-connected subgraph problem[END_REF] and [START_REF] Diarrassouba | The k-node connected subgraph problem: Polyhedral analysis and branch-and-cut[END_REF], for example) have concluded that the problem without considering hop constraints seems to become easier when k increases. In our case (the kNDHP with L < |V | -1), the impact of the connectivity on the resolution is less clear. It even seems, when comparing the results for L = 3 and L = 4, that the kNDHP becomes more difficult to solve when L increases.

The computational study pointed out that a very large number of st-cut and 3-stpath-cut inequalities are generated during the resolution of the problem. This can be an issue since it yields the Branch-and-Cut algorithm to manage a huge pool of constraints and can imply an execessive CPU time consumption for constraints management. This can even yield the Branch-and-Cut algorithm to solve linear programs with a large number, but still polynomial, number of constraints. Finally, all this may prevent the algorithm from a good exploration of the Branch-and-Cut tree.

The above observations suggests that an efficient algorithm for the kNDHP requires a tighter formulation for the problem, which may efficiently include simultaneously both the disjoint paths and the hop contraints. Also, it may require a deeper investigation of the polytope of the problem in order to provide more facet-defining inequalities and yield an efficient Branch-and-Cut algorithm.

For theoretical purposes, it should be interesting to study the polyope of the kNDHP in some special cases, like for example when the graph is series-parallel. Also, one could investigate the problem with respect to the distribution of the demands, since it may influence the polyhedral description of the solutions of the problem, and probably the efficiency of resolution algorithms.

Another question which would be of interest is to see whether one can use directed models for the kNDHP. This may provide stronger integer linear programming formulations. This is one of our research lines in the future.

Conclusion

In this thesis, we have studied, within a polyhedral context, two survivable network design problems, the k-node-connected subgraph (kNCSP) and the k node-disjoint hop-constrained survivable network (kNDHP) problems. In particular, we have considered these problems in the case where a high level of connectivity is required, that is when k ≥ 3. These two problems are NP-hard when k ≥ 2.

In the first part, we considered the k-node-connected subgraph problem (kNCSP). We focused our attention on the polyhedron associated with this problem. We derived new classes of valid inequalities. We then described necessary and sufficient conditions for theses inequalities to define facets. Moreover, we have studied some reduction operations inspired from the ones introduced by Didi Biha and Mahjoub [START_REF] Biha | The k-edge connected subgraph problem i: Polytopes and critical extreme points[END_REF] (see also [START_REF] Biha | Graphes k-arêtes connexes et polyèdres[END_REF]). These allow to perform the separation of the valid inequalities in a reduced graph. Using these results, we have devised a Branch-and-Cut algorithm for the problem and given computational results for k = 3, 4, 5. The later was implemented to solve instances from SNDlib and TSPlib with realistic topologies. The experiments show in particular the efficiency of the separation procedure used in the Branch-and-Cut algorithm and the significant improvement enabled by the introduced inequalities on strengthening the linear relaxation of the problem.

We studied afterwards a hop-constrained version of the problem that is kNDHP, taking into account the length of the paths between every origin and destination of the demands. We introduced a new integer linear programming formulation for the problem. We studied the polyhedron associated with the formulation, in an attempt to describe strong valid inequalities for the problem. We investigated the properties of this polyhedron as well as the facial structure of the basic inequalities. This led us to define several classes of valid inequalities, that are facets of polyhedron under certain necessary and sufficient conditions, that we described. These valid inequalities were incorporated within a Branch-and-Cut framework. The obtained algorithm allowed to solve the problem for arbitrary and realistic instances from the TSPlib.

Conclusion

There are many directions in which the research in this thesis can be continued for both considered problems.

The experiments we have performed for the kNDHP for k = 3, 4, 5 and L = 3 have relatively high CPU time. It would be interesting to pursue the approach used here for the kNDHP when L = 3. One may lead a deeper investigation of the polytope of the problem by using the appropriate directed graphs and exploiting the known results on arc-disjoint paths problems in directed graphs. This may help to provide new facet defining inequalities. It would also be interesting, from an algorithmic point of view, to improve the separation procedures provided for the various inequalities we have introduced in this work. We need to develop more efficient separation heuristics for the Branch-and-Cut algorithm. It will be also interesting to focus on more sophisticated preprocessing methods in order facilitate the problem resolution. It will also be interesting to perform the experimentations for the kNDHP for L = 4.

The same kind of study can be used for the kNDHP when L ≥ 5. If possible, this may provide an integer programming formulation for the problem as well as a Branch-and-Cut algorithm for all k ≥ 2 and L = 5.

  Notions . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Combinatorial optimization . . . . . . . . . . . . . . . . . . . 1.1.2 Computational complexity . . . . . . . . . . . . . . . . . . . . 1.1.3 Polyhedral approach and Branch-and-Cut . . . . . . . . . . . 1.1.4 Elements of polyhedral theory . . . . . . . . . . . . . . . . . . 1.1.5 Cutting plane method . . . . . . . . . . . . . . . . . . . . . . 1.1.6 Branch-and-Cut algorithm . . . . . . . . . . . . . . . . . . . . 1.2 Column generation and Branch-and-Price . . . . . . . . . 1.2.1 Column generation procedure . . . . . . . . . . . . . . . . . . 1.2.2 Branch-and-Price algorithm . . . . . . . . . . . . . . . . . . . 1.2.3 Graph theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 State-of-the-art on network design problems . . . . . . . . 1.3.1 The general survivable network design problem . . . . . . . . 1.3.2 The k-edge(node)-connected subgraph problem . . . . . . . . 1.3.3 The k-edge(node)-connected hop-constrained network design problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 2 :

 12 Figure 1.2: Valid inequality, facet and extreme points

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Dimension and Valid inequalities . . . . . . . . . . . . . . . 2.2.1 Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Node-partition inequalities . . . . . . . . . . . . . . . . . . . 2.2.3 SP-node-partition inequalities . . . . . . . . . . . . . . . . . . 2.2.4 F-node-partition inequalities . . . . . . . . . . . . . . . . . . 2.3 Facial aspect . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Structural properties . . . . . . . . . . . . . . . . . . . . . . 2.5 Reduction operations . . . . . . . . . . . . . . . . . . . . . . 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Proof.

  Let e ∈ E * . Then, x(e) = 1 for every solution x of kNCSP(G). Then dim(kNCSP(G)) ≤ |E|-|E * |. Now, observe that the edge sets S e = E\{e}, e ∈ E\E * , and E form |E| -|E * | + 1 solutions of the kNCSP. Moreover, the incidence vectors of these solutions are affinely independent. Therefore, dim(kNCSP(G)) ≥ |E| -|E * |.

  This implies that b e 1 = b e k+1 = ρ for some ρ ∈ R. By symmetry, it follows that b e i = ρ for all i = 1, ..., p. As M has a maximum cardinality, any edge e

  T 4 ∈ F ⊆ F . Which implies that b e i + b e j = b h + b e k+1 . As b e i = b e j = b e k+1 = ρ, it follows that b h = ρ. Thus we obtain that b e = ρ for all e ∈ δ G (W ). We will now show that b e = 0 for all e ∈ E\δ G (W ). As G[W ] and G[W ] are (k + 1)node-connected, we have that T 5 = T 1 \{e} induces a k-node-connected graph for all edge e ∈ E(W ) ∪ E(W ). Moreover x T 5 ∈ F ⊆ F . Hence b e = 0. Consequently, we have that b e = ρ for all e ∈ δ G (W ), and b e = 0 for all e ∈ E\δ G (W ). Thus b = ρa.

  and hence T 5 is a solution of kNCSP. Thus x T 5 ∈ F ⊆ F , and bx T 1 = bx T 5 = bx T 1b e . Which implies that b e = 0. Therefore b e = 0 for all e ∈ E(W ). Similarly, we have that b e = 0 for all e ∈ E(W ). Now let e ∈ [W, Z]. Let T 6 = T 1 \{e}. By ii), T 6 contains a matching of at least k edges in δ(W ). Hence T 6 is a solution of kNCSP, which implies that b e = 0. Consequently, we obtain that b e = ρ for all e ∈ δ G\Z (W ) and b e = 0 for all e ∈ E \ δ G\Z (W ). Thus, b = ρa. Which ends the proof of the theorem. Corollary 3 If the graph G is complete, then the node-cut inequalities (2.4) are facetdefining for kNCSP(G) if |W | ≥ k + 2 and |W | ≥ k + 2. Now, we discuss sufficient conditions for the F -node-partition and SP-node-partition inequalities to define facets of kNCSP(G).

  p, and let F = p i=1 F i . Then the F -nodepartition inequality (2.12), induced by π and F , defines a facet of kNCSP(G).

  Now we show that b(e) = ρa(e) for all e ∈ E\Γ, for some ρ ∈ R.As x T 1 , ..., x Tp belong to F , it follows that bx T 1 = ... = bx Tp = β. Hence b(e 1 ) = ... = b(e p ). As e 1 and e p are arbitrary edges of

Figure 2

 2 Figure 2.3: An SP-node-partition configuration for k = 5 and |Z| = 2

  ) and (2.[START_REF] Chimani | Orientationbased models for {0,1,2}-survivable network design: theory and practice[END_REF], and combining the resulting equations with (2.15) and (2.16), we get x(δ G\Z 1 (T 1 )) = k -|Z 1 | and x(δ G\Z 2 (T 4 )) = k -|Z 2 |, which ends the proof.

  for all e ∈ E(W ), and |δ G (W )| = k. θ 4 : Replace a set of parallel edges by only one edge.

  -and-Cut algorithm . . . . . . . . . . . . . . . . . . . 51 3.1.1 General framework . . . . . . . . . . . . . . . . . . . . . . . . 52 3.1.2 Separation algorithms . . . . . . . . . . . . . . . . . . . . . . 53 3.1.3 Primal heuristic . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Computational Results . . . . . . . . . . . . . . . . . . . . . 58 3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

  Extended formulation . . . . . . . . . . . . . . . . . . . . . . 67 4.2 Branch-and-Cut-and-Price algorithm . . . . . . . . . . . . 69 4.2.1 Column generation algorithm . . . . . . . . . . . . . . . . . . 69 4.2.2 Pricing heuristics . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.3 Computational results . . . . . . . . . . . . . . . . . . . . . 73 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

  u,v∈V,u =v θ u,v . Also for a cycle C and two nodes u, v ∈ V , let a C (u, v) = 1 if the cycle C goes through the nodes u and v, 0 otherwise. for all u, v ∈ V , and b C (e) = 1 if the cycle C uses edge e 0 otherwise.

  C∈θ a C (u, v)y(C) ≥ 1 for all u, v ∈ V, (4.1) C∈θ b C (e)y(C) ≤ Mx(e) for all e ∈ E, (4.2) y(C), x(e) ∈ {0, 1} for all e ∈ E and c ∈ θ. (4.3)

. 9 )

 9 a C (u, v)α uv -e∈E b C (e)β e ≤ 0 for all C ∈ θ, (4Mβ eγ e ≤ w(e) for all e ∈ E, (4.10) α uv ≥ 0, β e ≥ 0 for all u, v ∈ V and e ∈ E. (4.11) Then, given a cycle C ∈ θ, the reduced cost of the variable y(C) is given by c r (C) = u,v∈V a C (u, v)α uv -e∈E b C (e)β e . (4.12) If c r (C) < 0 then u,v∈V (C) α uv -e∈E(C) β e > 0. (4.13) where V (C) and E(C) denotes respectively the set of nodes and set of edges of the cycle C. Thus, the pricing problem reduces to find a longest cycle in the graph G, with respect to lengths α uv , on the pairs (u, v) ∈ V × V and -β e on the edges e ∈ E. If a longest cycle of G, say C * , is such that u,v∈V (C) α uv < e∈E(C) β e , then c r (C * ) < 0. If not, then c r (C) ≥ 0 for every cycle C ∈ θ.

Contents 5 . 1

 51 Integer Programming Formulation . . . . . . . . . . . . . . 80 5.2 Polytope and valid inequalities . . . . . . . . . . . . . . . . 85 5.2.1 Generalized L-st-path-cut inequalities . . . . . . . . . . . . . 86 5.2.2 Double cut inequalities . . . . . . . . . . . . . . . . . . . . . . 86 5.2.3 Triple path-cut inequalities . . . . . . . . . . . . . . . . . . . 88 5.2.4 Steiner-partition inequalities . . . . . . . . . . . . . . . . . . 89 5.2.5 Steiner SP-partition inequalities . . . . . . . . . . . . . . . . 91 5.2.6 The rooted partition inequalities . . . . . . . . . . . . . . . . 92 5.2.7 st-jump inequalities . . . . . . . . . . . . . . . . . . . . . . . 93 5.3 Facets of the kNDHP polytope . . . . . . . . . . . . . . . . 94 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Figure 5 . 2 :

 52 Figure 5.2: Construction of the graph H for L = 3.

Figure 5 . 4 :

 54 Figure 5.4: Infeasible solution of the 2NDHP with L = 5 and D = {(s, t)}.

Figure 5 . 5 :

 55 Figure 5.5: A double cut with L = 3 and t 1 = t.

Figure 5 . 6 :

 56 Figure 5.6: A triple-path cut with k = 2, L = 3 and s 1 = s 2 .

Theorem 20

 20 dim(kNDHP(G, L)) = |E|-|E * |, where |E * | is the set of essential edges. Proof. We have that the edges of E * belong to every solution of the problem, meaning that, x F (e) = 1, for all e ∈ E * , and every solution F ⊆ E of the problem. Then we have dim(kNDHP(G, L)) ≤ |E|-|E * |. By considering the edge sets E and E f = E \{f }, for every f ∈ E \ E * , we can clearly see that they form |E| -|E * | + 1 solutions, and their incidence vectors are affinely independent. Therefore dim(kNDHP(G, L)) ≥ |E| -|E * |, and the result follows.

Theorem 22

 22 Inequality x(e) ≥ 0, with e = uv ∈ E, defines a facet of kNDHP(G, L) if one of the following conditions hold. 1)|V | ≥ k + 3, 2) |V | = k + 2, |D| ≤ k -1 and (u, v) / ∈ D. Proof. Suppose that |V | = k + 2, |D| ≤ k -1, and (u, v) / ∈ D.Then, the edge sets E \ {e} and E f = E \ {e, f }, for all f ∈ E \ {e}, are solutions of kNDHP whose incidence vectors satisfy x(e) = 0 and are affinely independent. Now, suppose that |V | ≥ k + 3. Then for all the demands (s, t) ∈ D, the graph G contains k + 2 node-disjoint st-paths (edge st and the k + 1 paths of the form (s, u, t), u ∈ V \ {s, t}). Thus the sets E \ {e} and E f = E \ {e, f }, for all f ∈ E \ {e}, form a set of |E| solutions of the kNDHP. Moreover, their incidence vectors satisfy x(e) = 0 and are affinely independent. Hence x(e) ≥ 0 defines a facet of kNDHP(G, L).

  T 1b(e) + b(st), we obtain that b(e) = b(st). As e is an arbitrary edge in E 1 , this implies that b(e) = b(st) = ρ for some ρ ∈ R for all e ∈ E 1 .

  T 1 and therefore, b(st) = b(su) + b(ut). As (5.27), b(ut) = b(st), it follows that b(su) = 0. Hence b(e) = 0 for all e ∈ E 0 . Finally, we have that b(e) = ρ for all e ∈ δ(W ), 0 if not. Consequently, b = ρa with ρ ∈ R, which finishes the proof. Theorem 24 If |V | ≥ 2k + 1 and |D| = 1 with D = {(s, t)}, then every st-node-cut inequality x(δ G\Z (W )) ≥ k -|Z| where Z ⊂ V \ {s, t}, and such that s ∈ W , t / ∈ W and W \ {s} = ∅ = V \ ((W ∪ Z) \ {t}), defines a facet of kNDHP(G, L). Proof. Let us denote by ax ≥ α the inequality (5.3) induced by W and Z, and let bx ≥ β be a facet defining inequality of kNDHP(G, L) such that {x ∈ kNDHP(G, L) : ax = α} ⊆ {x ∈ kNDHP(G, L) : bx = β}. As before we will show that there exists a scalar ρ ∈ R such that b = ρa. The idea of the proof is to use the fact that x(δ G\Z (W )) ≥ k -|Z| is a valid cut inequality for (k -|Z|)NDHP(G \ Z, L), and hence, by Theorem 23, defines a facet of (k -|Z|)NDHP(G \ Z, L). Thus there exist dim((k -|Z|)NDHP(G \ Z, L)) solutions of the (k -|Z|)NDHP on G \ Z whose incidence vectors satisfy x(δ G\Z (W )) ≥ k -|Z| with equality and are affinely independent. In what follows, we will use these solutions to build |E| solutions of the kNDHP on G satisfying x(δ G\Z (W )) ≥ k -|Z| with equality and which are affinely independent. Notice that as G is complete, |Z| ≤ k -1 and |V | ≥ 2k + 1, G \ Z is also complete with |V \ Z| ≥ k + 2. Thus, by Corollary 7, the polytope (k -|Z|)NDHP(G \ Z, L) is full dimensional, and hence dim((k -|Z|)NDHP(G \ Z, L)) = |E| -|δ(Z)| -|E(Z)|. As x(δ G\Z (W )) ≥ k -|Z| defines a facet of (k -|Z|)NDHP(G \ Z, L), there must exist m ′ = |E| -|δ(Z)| -|E(Z)| solutions of the (k -|Z|)NDHP on G \ Z, denoted by T ′ i , i = 1, ..., m ′ , whose incidence vectors are affinely independent and satisfy x(δ G\Z (W )) = k -|Z|.

  z∈Z {sz, zt} by e j , j = 1, ..., |δ(Z)| + |E(Z)| -2|Z|. Consider the edge setsΓ m ′ +j = T m ′ \{e j }, for j = 1, ..., |δ(Z)|+|E(Z)|-2|Z|.We can see that these sets induce solutions of the kNDHP, and their incidence vectors satsify x(δ G\Z (W )) = k -|Z|. As

  it follows that b(sz) = b(zt) = 0. Therefore b = ρa, which ends the proof of the theorem.

  S 1 = β and, in consequence, b(su) + b(ut) = b(st). As, by (5.28), b(ut) = b(st), we have that b(su) = 0. Thus, we obtain that b(e) = 0 for all e ∈ E \ T.

S 6 -

 6 bx S 1 + b(vt) = b(e)b(su 3 ) + b(vt) = 0. By (5.28) and (5.29), we get b(e) = ρ.Now suppose that e = uv ∈ [V 1 , V 3 ]. If u ∈ U 1 and v ∈ U 3 ,then by considering the edge set S 8 = (S 1 \ {ut, sv}) ∪ {e, st}, which is a solution of kNDHP with x T 8 ∈ F , we get b(e)+b(st) = b(sv)+b(ut). From (5.28) and (5.29), we have that b(e) = ρ. If u / ∈ U 1 and v ∈ U 3 , then by considering the edge set S 9 = (S 1 \ {sv}) ∪ {su, e}, we obtain along the same line that b(e) = ρ. If u ∈ U 1 and v / ∈ U 3 , it follows by symmetry that b(e) = ρ. If u / ∈ U 1 and v / ∈ U 3 , since the edge set S 10 = (S 1 \ {su 1 , u 1 t}) ∪ {su, e, vt} is a solution of kNDHP with x T 10 ∈ F , we get as before b(e) = ρ. Thus, we obtain b(e) = ρ for all e ∈ T \ (S 1 ∪ {st}). (5.30) From (5.28)-(5.30), we have b(e) = ρ for all e ∈ T, 0 if not.

  t}, is valid for (k -|Z|)NDHP(G\Z, 3) (recall that (k -|Z|)NDHP(G \ Z, 3) is the polytope associated with the 3-hop-constrained st-path problem on the graph G \ Z). Note as before that G is complete, |Z| ≤ k -1 and|V | ≥ 2k + 1, then G \ Z is complete with |V \ Z| ≥ k + 2. By Corollary 7 the polytope (k -Z)NDHP(G \ Z, 3) is full dimensional. Thus dim((k -|Z|)NDHP(G \ Z, 3))= |E| -|δ(Z)| -|E(Z)|. As x(T G\Z ) ≥ k -|Z| defines a facet of (k -|Z|)NDHP(G \ Z, 3), there exist n ′ = |E| -|δ(Z)| -|E(Z)| solutions of the (k -|Z|)NDHP on G \ Z.We will denote them by S ′ i , i = 1, ..., n ′ , their incidence vectors are affinely independent and satisfy x(T G\Z ) = k -|Z|. The st-paths of S ′ i , i = 1, ..., m, are node-disjoint, hence they are solutions of the polytope (k -|Z|)NDHP(G \ Z, 3). The edge sets S i = S ′ i ∪ δ(Z) ∪ E(Z), for all i ∈ {1, ..., n ′ }, induce solutions of the kNDHP. Since S ′ i , i ∈ {1, ..., n ′ } is a solution of the (k -|Z|)NDHP on G \ Z, there exist (k -|Z|) st-paths of length at most 3, in the subgraph of G \ Z induced by S ′ i .

  It then follows that b ′ = ρa ′ . This implies that b(e) = 0 for all e ∈ E \ T . Now we will show that b(e) = 0 for all e ∈ δ(Z) ∪ E(Z). Let us denote the edges of E(Z) ∪ δ(Z) \ z∈Z {sz, zt} by e j , j = 1, ..., |δ(Z)| + |E(Z)| -2|Z|. Consider the edge set Ω n ′ +j = S n ′ \ {e j }, for j = 1, ..., |δ(Z)| + |E(Z)| -2|Z|. These sets clearly induce solutions of the kNDHP, and their incidence vectors satsify x(T G\Z ) = k -|Z|. As ax S n ′ = ax Ω n ′ +j = α, it follows that bx S n ′ = bx Ω n ′ +j = β. Hence, b(e j ) = 0 for j = 1, ..., |δ(Z)| + |E(Z)| -2|Z|.

  Consider the edge set S 0 = (S 1 \{sz})∪{su 1 , u 1 z} and S ′ 0 = (S 1 \{zt})∪{sz, zu 2 }. It clearly induces a solution of the kNDHP. Moreover we have x(T G\Z ) = k -|Z|. Thus, bx T 1 = bx T 0 = bx T ′ 0 = β. As b(su 1 ) = b(u 1 z) = b(zu 2 ) = b(u 2 t) = 0, it follows that b(sz) = b(zt) = 0. Therefore b = ρa, which ends the proof of the theorem. Note that Theorem 21, 22, 23 and 24 are valid for L ≥ 4.

6. 1

 1 Branch-and-Cut Algorithm for the kNDHP with L = 3 and k ≥ 3 107 2) st-node-cut and L-st-node-path-cut inequalities (only for integral solutions), 3) Steiner SP-partition inequalities, 4) double cut inequalities, 5) Steiner partition inequalities.

  of nodes of the graph, |D| : the number of demands, C-LPC : the number of generated st-cut and 3-st-path-cut inequalities, NC-NLPC : the number of generated st-node-cut and 3-st-node-path-cut inequalities, SP : the number of generated Steiner SP-partition inequalities, DC : the number of generated double cut inequalities, DC : the number of generated Steiner partition inequalities, COpt : value of the best upper bound obtained, Gap : the relative error between the best upper bound and the lower bound obtained at the root node of the Branch-and-Cut tree, NSub : the number of nodes in the Branch-and-Cut tree, CPU : total CPU time of the first run in hours:min.sec.

Table 1 :

 1 Résultats pour les instances de la SNDLIB avec k = 3.

	Instance	#EC	#NC	#SPC #FNPC #NPC	COpt	Gap1	NSub1	CPU1
	bays_29	74	3709	11	39	8	14815	1.01	19	0:01:10
	dantzig_42	137	9156	12	32	16	1232	0.03	42	0:14:14
	att_48	138	13995	14	47	10	17527	0.02	48	0:42:11
	eil_51	55	4680	7	30	1	745	0.02	4	0:06:41
	berlin_52	133	9518	26	95	10	12644	0.22	30	0:27:05
	eil_76	80	15321	8	84	4	947	0.11	8	0:48:05
	gr_96	174	330	19	6	0	915	0.6	2	2:03:11
	rat_99	112	294	9	19	0	2105	0.3	32	2:02:26
	kroA_100	169	305	24	13	1	36492	0.21	2	2:04:35
	rd_100	186	303	21	3	0	13391	0.13	21	2:01:03
	kroB_100	145	300	12	52	1	37341	1.6	12	2:03:58
	lin_105	214	317	15	6	6	24870	2.4	35	2:01:44
	gr_120	90	332	10	0	0	11562	0.6	2	2:26:57
	bier_127	136	364	16	2	0	199863	3.2	23	2:42:41
	pr_124	179	403	12	0	0	99696	0.29	3	2:28:01
	ch_130	122	371	10	0	0	10571	7.1	12	2:48:25
	kroA_150	130	415	1	2	0	44952	2.6	23	2:49:56
	*u_159	112	429	3	7	0	71772	8.9	59	5:00:00

Table 2 :

 2 Résultats pour les instances de la TSPLIB avec k = 3.

Table 3 :

 3 Résultats pour les instances de la SNDLIB.

	Instance	|V | Gen_Cuts	Gen_Cols	COpt Gap	NSub	CPU
	diyuan	11	2	0	989	0.00	1	0:00:02
	pdh_12	11	19	0	18	0.00	1	0:00:03
	abilene	12	19	24	121	0.04	15	0:00:18
	atlanta	12	17	28	115	0.00	1	0:00:03
	polska	12	26	4	27	0.05	11	0:00:01
	nobel-us	14	32	0	117	0.00	5	0:00:02
	newyork	16	24	56	2335	0.00	1	0:00:04
	geant	22	58	80	226	0.02	15	0:00:20
	ta1	24	45	27	1859	0.02	27	0:00:31
	france	25	52	43	1985	0.01	7	0:00:48
	janos-us	26	64	626	178	0.06	25	0:00:21
	sun	27	50	22	2849	0.00	1	0:00:08
	norway	27	91	1068	3847	0.08	139	0:01:19
	janos-us-ca	37	85	14	201	0.06	27	0:00:24
	cost266	37	118	7876	173	0.07	103	0:12:59
	giul39	39	149	6576	3949	0.05	147	0:09:46
	pioro	40	81	2168	3625	0.03	11	0:01:44
	germany	50	67	4948	56	0.1	33	0:52:34
	ta2	65	148	2439	3455	0.04	3	1:06:10

Table 5 :

 5 Résultats pour k = 3, L = 3 et des demandes routées.

	Résumé long

Table 6 :

 6 Résultats pour k = 3, L = 3 et des demandes arbitraires.

	|V | |D| C-LPC NC-NLPC SP	DC	P	COpt	Gap	NSub	CPU
	a 21	10	56593	2	0	483	0	6680	8.66	9191	05:00:00
	a 21	11	29325	2	0	375	1	6770	6.8	2614	00:57:32
	a 30	10	44057	25	18	38	0	10354	6.64	13274	05:00:00
	a 30	15	53545	86	0	462	0	13936	11.69	6399	05:00:00
	a 48	15	34047	0	0	20	0	-	-	1119	05:00:00
	a 48	20	28329	0	2	10	0	-	-	229	05:00:00
	a 48	24	23975	0	0	11	0	-	-	103	05:00:00
	a 52	20	30157	108	6	41	0	-	-	1735	05:00:00
	a 52	26	24217	0	0	96	0	-	-	307	05:00:00

  Table 1.2: Models of survivable networks with node versus edge connectivity.

	Connectivity	Bound	Edge case results	Node case results
	k = 2	L = ∞	ILP formulation, valid inequalities,	ILP formulation, valid
			separation, Branch & Cut, polytope	inequalities, separation,
			characterization [7, 54, 45, 46, 47, 5]	Branch & Cut [54, 57, 45, 46, 47]
	k ≥ 3	L = ∞	ILP formulation, valid inequalities,	ILP formulation, separation
			separation, Branch & Cut, polytope	valid inequalities,
			characterization [7, 54, 45, 47, 5]	Branch & Cut [9, 22, 45, 47]
	k = 2	L = 2, 3	ILP formulation, valid inequalities,	ILP formulation, valid inequalities
			separation, Branch & Cut [49, 51]	polyhedral study,
				Branch & Cut [10, 22, 45, 47]
	k = 2	L = 4	ILP formulation, valid inequalities,	ILP formulation, valid inequalities
			separation, Branch & Cut [50, 49]	Branch & Cut [50]
	k ≥ 3	L = 2, 3	ILP formulation, valid inequalities,	Considered in this thesis
			separation, Branch & Cut, extended
			formulation [10, 15, 14, 21, 22, 23, 27]

Table 3

 3

	Instance	#EC	#NC	#SPC #FNPC #NPC	COpt	Gap1	NSub1	CPU1
	bays_29	74	3709	11	39	8	14815	1.01	19	0:01:10
	dantzig_42	137	9156	12	32	16	1232	0.03	42	0:14:14
	att_48	138	13995	14	47	10	17527	0.02	48	0:42:11
	eil_51	55	4680	7	30	1	745	0.02	4	0:06:41
	berlin_52	133	9518	26	95	10	12644	0.22	30	0:27:05
	eil_76	80	15321	8	84	4	947	0.11	8	0:48:05
	gr_96	174	330	19	6	0	915	0.6	2	2:03:11
	rat_99	112	294	9	19	0	2105	0.3	32	2:02:26
	kroA_100	169	305	24	13	1	36492	0.21	2	2:04:35
	rd_100	186	303	21	3	0	13391	0.13	21	2:01:03
	kroB_100	145	300	12	52	1	37341	1.6	12	2:03:58
	lin_105	214	317	15	6	6	24870	2.4	35	2:01:44
	gr_120	90	332	10	0	0	11562	0.6	2	2:26:57
	bier_127	136	364	16	2	0	199863	3.2	23	2:42:41
	pr_124	179	403	12	0	0	99696	0.29	3	2:28:01
	ch_130	122	371	10	0	0	10571	7.1	12	2:48:25
	kroA_150	130	415	1	2	0	44952	2.6	23	2:49:56
	*u_159	112	429	3	7	0	71772	8.9	59	5:00:00

.1: Results for SNDLIB instances with k = 3.

Table 3

 3

.2: Results for TSPLIB instances with k = 3.

  .4.

	Instance	#EC	#NC #FNPC COpt Gap1	NSub1	CPU1
	atlanta_15	0	246	2	4615	0.00		0:00:01
	geant_22	0	912	0	521	0.00		0:00:01
	france_25	0	594	0	4692	0.00		0:00:01
	norway_27	0	793	4	8257	0.00		0:00:03
	sun_27	0	696	0	6867	0.00		0:00:01
	india_35	4	1324	2	640	0.00		0:00:08
	cost266_37	0	1326	0	392	0.00		0:00:03
	giul_39	0	1602	2	8314	0.00		0:00:07
	pioro_40	0	1711	3	8137	0.00		0:00:15
	germany_50	0	2610	0	156	0.00		0:00:12
	ta2_65	0	4417	4	7631	0.00		0:02:01

Table 3

 3

	Instance	#EC	#NC	#FNPC	COpt	Gap1	NSub1	CPU1
	bays_29	4	897	0	20945	0.00		0:00:01
	dantzig_42	10	1858	9	1776	0.00		0:00:11
	att_48	20	2458	5	17380	0.00		0:01:15
	eil_51	0	2544	0	1051	0.00		0:00:12
	berlin_52	6	2860	2	18351	0.00		0:00:54
	eil_76	0	5981	2	1350	0.00		0:03:24
	gr_96	62	438	76	1314	1.6		2:00:03
	rat_99	29	10135	14	3045	0.00		0:49:33
	kroA_100	22	15223	6	53111	0.00		0:32:25
	rd_100	81	451	32	20341	1.9		2:02:38
	kroB_100	95	5012	31	55182	2.5		0:45:09
	lin_105	33	11339	4	36430	0.00		0:36:58
	gr_120	6	14765	6	18714	0.00		0:48:40
	pr_124	69	7553	16	144715	3.5		2:12:59
	bier_127	30	16447	0	283154	0.00		0:34:22
	ch_130	26	532	10	15123	2.3	23	2:06:45
	kroA_150	19	595	4	68281	5.3	22	2:24:45
	u_159	13	630	6	104664	7.2	15	4:38:14

.3: Results for SNDLIB instances with k = 4.

Table 3

 3

	.4: Results for TSPLIB instances with k = 4.

  and 3.6.

	Instance	#EC	#NC #SPC	#FNPC #NPC	COpt	Gap1	NSub1	CPU1
	atlanta_15	14	326	0	12	0	6239	0.00	1	0:00:01
	geant_22	2	1193	0	0	2	717	0.35	12	0:00:04
	france_25	25	832	0	40	1	6478	0.00	1	0:00:20
	norway_27	27	944	0	47	0	11217	0.00	1	0:00:51
	india_35	30	2023	0	21	0	864	0.17	1	0:00:51
	sun_27	27	1296	0	46	0	9383	0.34	4	0:00:32
	cost266_37	37	1677	0	149	1	527	0.19	4	0:04:38
	giul_39	39	1838	0	75	0	11264	0.00	1	0:03:41
	pioro_40	0	1728	0	4	0	10952	0.00	1	0:00:12
	germany_50	9	2651	0	4	0	206	0.00	1	0:00:31
	ta2_65	67	4723	0	103	0	10276	0.00	1	0:45:20

Table 3 .

 3

5: Results for SNDLIB instances with k = 5

Table 3 .

 3

6: Results for TSPLIB instances with k = 5

  .7.

	Instance	Gap1	Gap2	NSub1	NSub2	CPU1	CPU2
	atlanta_15	0.01	0.02	3	15	00:00:01	00:00:32
	geant_22	1.07	1.94	60	77	00:00:26	00:01:21
	france_25	0.08	0.09	37	57	00:00:32	00:01:48
	norway_27	0.76	1.78	15	34	00:00:43	00:02:05
	india_35	0.33	2.05	8	24	00:00:53	00:02:08
	giul_39	0.03	1.4	5	11	00:02:19	00:15:34
	ta2_65	0.07	1.7	9	35	00:43:55	02:42:37
	dantzig_42	0.03	0.79	42	74	00:14:14	01:37:37
	att_48	0.02	2.4	48	68	00:42:11	02:39:38
	eil_76	0.11	3.4	8	53	00:48:05	05:00:00
	gr_96	0.6	7.8	2	41	02:03:11	03:24:57

Table 3 .

 3

7: Comparison of results for k = 3 with and without the reduction operations.

  .8.

	Instance	Gap1	Gap3	NSub1	NSub3	CPU1	CPU3
	atlanta_15	0.01	0.03	3	9	00:00:01	00:00:45
	geant_22	1.07	2.1	60	84	00:00:26	00:02:09
	france_25	0.08	0.17	37	43	00:00:32	00:02:33
	norway_27	0.76	1.97	15	60	00:00:43	00:02:51
	india_35	0.33	1.71	8	17	00:00:53	00:04:14
	giul_39	0.03	1.8	5	14	00:02:19	00:17:57
	ta2_65	0.07	1.2	9	21	00:43:55	01:18:37
	dantzig_42	0.03	1.64	42	57	00:14:14	00:45:52
	att_48	0.02	1.9	48	71	00:42:11	01:34:59
	eil_76	0.11	6.5	8	64	00:48:05	02:54:35
	gr_96	0.6	13.2	2	34	02:03:11	05:00:00

Table 3 .

 3

8: Comparison of results for k = 3 with and without the F -node-partition, SP-node-partition and node-partition inequalities.

Table 4 .

 4 1: Results for the SNDLIB instances.

	Instance	|V | Gen_Cuts	Gen_Cols	COpt Gap	NSub	CPU
	diyuan		2	0	989	0.00	1	0:00:02
	pdh_12		19	0	18	0.00	1	0:00:03
	abilene		19	24	121	0.04	15	0:00:18
	atlanta		17	28	115	0.00	1	0:00:03
	polska		26	4	27	0.05	11	0:00:01
	nobel-us		32	0	117	0.00	5	0:00:02
	newyork		24	56	2335	0.00	1	0:00:04
	geant		58	80	226	0.02	15	0:00:20
	ta1		45	27	1859	0.02	27	0:00:31
	france		52	43	1985	0.01	7	0:00:48
	janos-us		64	626	178	0.06	25	0:00:21
	sun		50	22	2849	0.00	1	0:00:08
	norway		91	1068	3847	0.08	139	0:01:19
	janos-us-ca		85	14	201	0.06	27	0:00:24
	cost266		118	7876	173	0.07	103	0:12:59
	giul39		149	6576	3949	0.05	147	0:09:46
	pioro		81	2168	3625	0.03	11	0:01:44
	germany		67	4948	56	0.1	33	0:52:34
	ta2		148	2439	3455	0.04	3	1:06:10
			Table 4.2: Results for the TSPLIB instances.
	Instance	|V |	Gen_Cuts	Gen_Cols	COpt	Gap	NSub	CPU
	burma14	14	38	124	3841	0.06	29	0:00:08
	ulysses22	22	56	868	8180	0.07	47	0:00:31
	fri26	26	67	65	965	0.01	23	0:01:33
	bays	29	84	1498	9884	0.05	55	0:03:41
	dantzig42	42	82	1	699	0.00	1	0:00:20
	eil51	51	114	6847	482	0.06	19	4:59:01
	berlin52	52	141	127	8181	0.04	7	0:05:48
	st70	70	191	2970	750	0.05	3	4:51:05
	pr76	76	240	2595	130921	0.1	5	4:53:32
	kroC100	100	376	2135	23295	0.05	46	2:45:27
	lin105	105	420	8771	16766	0.07	36	4:41:23
	ch130	130	331	3722	7129	0.07	48	4:55:44
	gr137	137	363	5579	79460	0.06	25	5:00:00

Table 4 .

 4 3: Branch-and-Cut and Branch-and-Cut-and-Price comparison for SNDLIB instances.

	Instance	|V | COpt_BC	COpt_BCP	Gap_BC	Gap_BCP	NSub_BC	NSub_BCP	CPU_BC CPU_BCP
	atlanta	12	120	121	0.00	0.4	12	15	0:00:01	0:00:18
	polska	12	27	27	4.17	0.05	12	11	0:00:01	0:00:01
	nobel-us	14	117	117	0.00	0.00	14	5	0:00:01	0:00:02
	newyork	16		2543	0.00	0.04	16	17	0:00:01	0:00:12
	geant	22	222	226	0.00	0.02	22	15	0:00:02	0:00:20
	ta1	24		1859	0.00	0.02	24	27	0:00:01	0:00:31
	france	25		1985	0.00	0.01	25	7	0:00:13	0:00:48
	janos-us	26	178	178	0.00	0.06	26	25	0:00:02	0:00:21
	norway	27		3847	0.00	0.04	27	25	0:00:02	0:01:02
	sun	27		2849	0.88	0.00	27	1	0:00:01	0:00:08
	india	35	270	184	0.00	0.06	35	117	0:00:21	0:09:35
	cost266	37	165	173	0.00	0.07	37	103	0:00:04	0:12:59
	janos-us-ca	37	201	201	0.00	0.06	37	27	0:00:06	0:00:24
	giul39	39		3949	0.6	0.05	39	147	0:00:34	0:09:46
	pioro	40		3625	0.00	0.03	40	11	0:01:19	0:01:44
	ta2	65		3455	0.09	0.04	65	3	0:12:35	1:06:10

Table 4 .

 4 4: Branch-and-Cut and Branch-and-Cut-and-Price comparison for TSPLIB instances.

	Instance	|V |	COpt_BC COpt_BCP	Gap_BC	Gap_BCP	NSub_BC	NSub_BCP	CPU_BC CPU_BCP
	burma14	14	3323	3841	0.00	0.06	1	29	0:00:01	0:00:08
	ulysses22	22	7013	8180	0.00	0.07	1	47	0:00:01	0:00:31
	fri26	26	937	965	0.05	0.01	12	23	0:00:54	0:01:33
	bays29	29	2020	9884	0.02	0.05	6	55	0:00:15	0:03:41
	dantzig42	42	699	699	0.4	0.00	11	1	0:00:20	0:01:42
	eil51	51	426	482	0.00	0.06	1	19	0:02:01	4:59:01
	berlin52	52	7542	8181	0.00	0.04	1	7	0:00:16	0:05:48
	s70	70	675	750	0.15	0.05	5	3	0:12:12	4:51:05
	pr76	76	108159	130921	0.01	0.1	8	5	0:41:30	4:53:32
	kroC100	100	20749	23295	4.57	0.05	78	46	3:49:24	2:45:27
	lin105	105	14379	16766	0.39	0.07	63	36	2:15:24	4:41:23
	ch130	130	6110	7129	0.12	0.07	57	48	2:45:25	4:55:44
	gr137	137	69853	79460	7.38	0.06	42	25	5:00:00	5:00:00

  .19) Inequalities of type (5.19) are called Steiner-SP-partition inequalities.

	Theorem 18 Inequalities (5.19) are valid for kNDHP(G, L).

Chapter 6 Branch-and-Cut Algorithm for the kNDHP Contents 6

.1 Branch-and-Cut Algorithm for the kNDHP with L = 3 and k ≥ 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 6.1.1 The general framework . . . . . . . . . . . . . . . . . . . . . . 106 6.1.2 Separation procedures . . . . . . . . . . . . . . . . . . . . . . 107 6.1.3 Computational Results . . . . . . . . . . . . . . . . . . . . . . 113 6.2 Branch-and-Cut Algorithm for the kNDHP with L = 4 and k = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.2.1 The general framework . . . . . . . . . . . . . . . . . . . . . . 119 6.2.2 Separation procedures . . . . . . . . . . . . . . . . . . . . . . 119 6.2.3 Computational results . . . . . . . . . . . . . . . . . . . . . . 120 6.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.1 Branch-and-Cut Algorithm for the kNDHP with L = 3 and k ≥ 3

Table 6 .

 6 1: Results for k = 3, L = 3 and rooted demands.

	|V | |D| C-LPC NC-NLPC SP	DC P	COpt	Gap	NSub	CPU
	r 21	11775	74	10	0	0	5526	9.23	2265	00:04:46
	r 21	22356	228	0	0	0	5939	9.4	4518	00:18:24
	r 21	71354	116	0	0	0	6466	9.54	17673	03:10:39
	r 30	15599	264	14	0	0	10109	6.87	1521	00:12:06
	r 30	58659	1516	12	0	0	11376	8.41	15280	05:00:00
	r 30	80999	615	18	0	0	12661	12.33	14281	05:00:00
	r 48	51038	1632	26	0	0	18337	18.1	6133	05:00:00
	r 48	66277	898	10	0	0	25437	28.68	5305	05:00:00
	r 48	69242	257	2	0	0	31693	30.17	5628	05:00:00
	r 52	49717	1674	22	0	0	11170	9.15	5707	05:00:00
	r 52	62698	1692	18	0	0	14626	17.11	3845	05:00:00
	r 52	68794	1024	16	0	0	17920	21.86	4953	05:00:00
	r 52	77808	142	0	0	0	20873	24.49	4397	05:00:00

Table 6 .

 6 2: Results for k = 3, L = 3 and arbitrary demands.

	|V | |D| C-LPC NC-NLPC SP	DC	P	COpt	Gap	NSub	CPU
	a 21	10	56593	2	0	483	0	6680	8.66	9191	05:00:00
	a 21	11	29325	2	0	375	1	6770	6.8	2614	00:57:32
	a 30	10	44057	25	18	38	0	10354	6.64	13274	05:00:00
	a 30	15	53545	86	0	462	0	13936	11.69	6399	05:00:00
	a 48	15	34047	0	0	20	0	-	-	1119	05:00:00
	a 48	20	28329	0	2	10	0	-	-	229	05:00:00
	a 48	24	23975	0	0	11	0	-	-	103	05:00:00
	a 52	20	30157	108	6	41	0	-	-	1735	05:00:00
	a 52	26	24217	0	0	96	0	-	-	307	05:00:00

Table 6 .

 6 3: Results for k = 4, L = 3 and rooted demands.

	|V | |D| C-LPC NC-NLPC DC	COpt	Gap	NSub	CPU
	r	15	4923	52	0	7322	4.57	1078	00:00:50
	r	17	5732	24	0	7826	4.56	1186	00:01:06
	r	20	35317	9	0	8556	5.32	17991	01:11:08
	r	15	48473	2266	0	14315	6.66	10718	05:00:00
	r	20	23784	0	0	15041	4.19	5664	00:35:22
	r	25	54445	595	0	16379	5.93	11631	05:00:00
	r	20	40090	1784	0	26131	20.86	6929	05:00:00
	r	30	43988	621	0	29806	16.86	4140	05:00:00
	r	40	51107	232	0	40037	24.77	4302	05:00:00
	r	20	39125	1346	0	15480	8.72	5106	05:00:00
	r	30	42750	2760	0	20976	20.28	5192	05:00:00
	r	40	49499	831	0	24343	21.52	4865	05:00:00
	r	50	56313	282	0	26541	17.92	4472	05:00:00

Table 6 .

 6 4: Results for k = 4, L = 3 and arbitrary demands.

	|V |	|D| C-LPC NC-NLPC	DC	COpt	Gap	NSub	CPU
	a	10	50711	108	858	9339	10.37	9674	05:00:00
	a	11	55432	127	703	9864	12.52	10221	05:00:00
	a	10	36595	116	152	14582	6.3	9817	05:00:00
	a	15	39442	37	319	18961	10.19	4593	05:00:00
	a	15	24750	0	20	-	-	589	05:00:00
	a	20	20007	0	4	-	-	137	05:00:00
	a	24	16095	0	2	-	-	47	05:00:00
	a	20	21556	0	54	-	-	867	05:00:00
	a	26	14635	0	35	-	-	215	05:00:00

Table 6 .

 6 5: Results for k = 5, L = 3 and rooted demands.

	|V | |D| C-LPC NC-NLPC SP	DC P	COpt	Gap	NSub	CPU
	r 21	15	8854	173	0	0	0	9560	3.24	3283	00:03:45
	r 21	17	23490	804	0	0	0	10235	3.93	19537	00:54:09
	r 21	20	31742	958	0	0	0	11095	4.1	59210	03:18:34
	r 30	15	80055	6007	0	0	0	19624	10.01	25045	05:00:00
	r 30	20	87973	838	0	0	0	20444	5.78	19283	05:00:00
	r 30	25	77565	670	0	0	0	21604	5.31	23220	05:00:00
	r 48	20	55964	4334	0	0	0	32753	18.53	11308	05:00:00
	r 48	30	59897	1414	0	0	0	41200	22.3	9979	05:00:00
	r 48	40	68991	319	0	0	0	48194	20.02	7758	05:00:00
	r 52	20	55456	5330	0	0	0	28222	34.95	10387	05:00:00
	r 52	30	56528	3283	0	0	0	31443	31.67	9388	05:00:00
	r 52	40	61465	1330	0	0	0	30645	20.24	7997	05:00:00
	r 52	50	77724	275	0	0	0	33994	17.27	8225	05:00:00

Table 6 .

 6 6: Results for k = 5, L = 3 and arbitrary demands.

	|V | |D| C-LPC	NC-NLPC SP	DC	P	COpt	Gap	NSub	CPU
	a 21	10	71158	279	0	645	0	11703	7.8	23196	05:00:00
	a 21	11	74831	516	0	1097	1	12533	11.58	24980	05:00:00
	a 30	10	49032	305	4	0	0	18613	2.94	20559	05:00:00
	a 30	15	56285	242	0	589	0	24043	8.29	9227	05:00:00
	a 48	15	37209	91	0	8	0	-	-	2479	05:00:00
	a 48	20	28574	0	0	2	0	-	-	303	05:00:00
	a 48	24	24246	0	0	0	0	-	-	113	05:00:00
	a 52	20	33492	29	0	0	0	30754	17.31	2065	05:00:00
	a 52	26	25465	0	0	20	0	-	-	347	05:00:00

Table 6 .

 6 7: Results for k = 2, L = 4 and arbitrary demands.

	|V |	|D| C-NC LPC-NLPC	COpt	Gap	NSub	CPU
	a 5	2	1	0	2314	0	1	0:00:01
	a 10	3	17	15	2358	1.64	23	0:00:01
	a 10	4	30	175	2773	10.1	186	0:00:01
	a 10	5	15	326	3219	11.14	615	0:00:01
	a 14	5	46	102	3326	7.18	356	0:00:01
	a 14	7	195	1604	3796	9.72	6439	0:00:08
	a 17	8	3589	45507	3079	31.71	608368	5:00:00
	a 21	10	2361	37423	4720	40.59	334898	5:00:00
	a 21	11	2893	36324	4770	41.44	334084	5:00:00
	a 48	10	26795	19456	57349	87.33	154736	5:00:00
	a 48	15	22343	32540	-	-	145813	5:00:00
	a 48	24	17236	30632	-	-	245307	5:00:00
	a 52	10	33319	16521	19769	74.6	107555	5:00:00
	a 52	15	29114	15508	32592	81.2	124780	5:00:00
	a 52	20	14288	33394	-	-	162161	5:00:00
	a 52	26	10778	33464	-	-	198811	5:00:00

Table 6 .

 6 8: Results for k = 2, L = 4 and rooted demands.

	|V | |D|	C-NC	LPC-NLPC	RP	COpt	Gap	NSub	CPU
	r 10	5	41	24	36	2358	1.35	17	0:00:01
	r 10	7	18	18	22	2848	4.09	23	0:00:01
	r 10	9	15	565	19	3481	12.28	588	0:00:01
	r 14	5	520	444	0	2601	7.9	383	0:00:01
	r 14	7	862	4177	882	2998	17.61	5820	0:00:36
	r 14	10	622	3481	668	3662	7.04	10540	0:00:31
	r 17	16	3202	83928	0	2700	22.65	380463	5:00:00
	r 21	7	717	1272	0	1789	6.59	425	0:00:02
	r 21	10	15721	35009	0	2570	25.91	431618	5:00:00
	r 30	29	7391	200914	0	13549	54.59	163377	5:00:00
	r 48	10	60181	46849	0	27557	77.47	81057	5:00:00
	r 48	15	69824	71232	0	37962	82.38	77855	5:00:00
	r 48	20	89805	86653	0	27814	72.68	70272	5:00:00
	r 48	30	87560	158432	0	38629	79.03	105848	5:00:00
	r 52	10	85786	59630	0	23916	83.1	62374	5:00:00
	r 52	20	116638	109693	0	19426	72.81	50496	5:00:00
	r 52	30	111091	174649	0	22143	72.07	63565	5:00:00
	r 52	40	43333	262234	0	22378	70.09	109805	5:00:00
	r 52	50	18217	281265	0	20731	64.4	120560	5:00:00

Preliminaries Notions and State-of-the-Art

The k-node-connected subgraph problem

Remerciements

Remerciements

Computational results

The Branch-and-Cut-and-Price algorithm described in the previous section has been implemented in C++, using SCIP 3.2.1 [4] to manage the Branch-and-Price, and CPLEX 12.5 as LP-solver for the exact pricing. All experiments were run on a com-puter equiped with a 2.10 GHz x4 Intel Core(TM) i7-4600U processor and running under linux with 16 GB of RAM. The maximum CPU time has been fixed to 5 hours. The test problems we have considered are complete euclidian graphs from SNDLIB library [1].

The entries of the tables presented below are:

|V |

: the number of nodes of the graph, Gen_Cuts : the number of generated cut and F -partition inequalities, Gen_Cols : the number of generated columns, COpt : value of the best upper bound obtained, Gap : the relative error between the best upper bound and the lower bound obtained at the root node of the tree, NSub : the number of nodes in the tree, CPU : total CPU time in hours:min:sec.

Our first series of experiments concerns the SNDLIB graphs. The results are summurized in Table 4.1. For the SNDLIB graphs, with 11 up to 65 nodes, all the instances have been solved to optimality within the time limit. The CPU time for these instances, except the last one, is less than one hour. Some of the instances of the table didn't require branching, for example diyuan (11 nodes), newyork (16 nodes) and sun (27 nodes). For all the instances the relative error between the lower bound at the root node and the best upper bound (Gap) is less than 1 %. We can also see that the column generation algorithm added a large number of variables and our separation procedures have detected an important number of cut inequalities and F -partition inequalities.

Our second series of experiments concerns the TSPLIB graphs given in Table 4.2. The instances we have considered have graphs with 14 up to 137 nodes. We observe that 12 instances over 13 have been solved to optimality within the time limit. For the last instance the algorithm has not been able to finish the resolution within 5 hours. A large number of variables were added by the column generation algorithm, and an important number of cut inequalities and F -partition inequalities have been generated. The gap between the lower bound at the root node of the Branch-and-Cut tree and the best upper bound is less than 0.01 for almost all the instances, except for pr76.

In the rest of this section, we focus on the comparison between the results obtained by the column generation algorithm and the Branch-and-Cut algorithm presented in Chapter 3 for k = 2, in terms of CPU time, Gap, number of nodes in the Branch-and-Cut tree and in terms of best solution.

) induces a partition of V \ Z and there exist two demands {s 1 , t 1 } and {s 2 , t 2 } with s 1 , s 2 ∈ V 0 , t 1 ∈ V 2 4 and t 2 ∈ V 2 5 . The sets V 1 4 and V 1 5 may be empty and s 1 and s 2 may be the same. Let also

is valid for kNDHP(G, 3).

) and Z, and T 2 and T 3 be the 3-s 2 t 2 -node-path-cuts induced by the partitions

, respectively, and Z. The following inequalities are valid for kNDHP(G, 3).

for all e ∈ F,

By summing these inequalities, divinding by 2 and rouding up the right hand side, we obtain inequality (5.15). Inequalities (5.15) will also be called triple-path-cut inequalities. Figure 5.6 gives an illustration.

Steiner-partition inequalities

Let R D be the set of terminal nodes of G. Let Z ⊂ V \ R D , and (V 0 , V 1 , ..., V p ), p ≥ 2, be a partition of V \Z such that V 0 ⊆ V \R D , and for all i ∈ {1, ..., p} there is a demand

) is equal to k -|Z| + 1 and the others are equal to k -|Z|, and the statement follows.

Theorem 27

The double cut inequality (5.13) defines a facet of kNDHP(G, 3)

Proof. i) Let C be the double cut inducing inequality (5.13). Using the following family of sets Π

, then the double cut inequality induced by Π is redundant with respect to the one induced by Π ′ , and the trivial inequalities

Thus it does not define a facet. ii) Let F be a facet defining double cut inequality and let T G\Z be the 3-st-node-pathcut induced by the partition (V 1 0 , V 2 0 ∪V 1 , V 2 , ..., V 4 ). As F defines a facet different from the node-cut inequalities, there exists a solution x 0 ∈ F such that x 0 (δ G\Z (V 1 0 ∪V 2 0 )) ≥ k -|Z| + 1. Then by Lemma 10, x 0 (T ) = k -|Z|. Thus, x 0 induces a graph which contains exactly k -|Z| node-disjoint 3-st-paths, P 1 , ..., P k-|Z| . Furthermore, each P i , i = 1, ..., k -|Z| intersects T G\Z in only one edge. Thus either P i ∩[V 0 , V 4 ] = ∅ or P i uses at least one edge between two non consecutive set of the partition (V 1 0 , V 2 0 , V 1 , V 2 , ..., V 4 ). In the latter case,

Which ends the proof.

Conclusion

In this chapter, we have studied the k-Node-Disjoint Hop-Constrained Network Design Problem (kNDHP) when L ∈ {2, 3, 4}. We have introduced an integer programming formulation for the problem when L ∈ {2, 3} and investigated the associated polytope.

We have presented several classes of valid inequalities and presented conditions under which these inequalities define facets.

Z which induces an inequality (5.3) or (5.4) violated by x.

In the sequel, we present the main ingredient and main results that will support our algorithm. First, consider a demand (s, t) ∈ D and let G st be the directed graph described in the proof of Theorem 28. Also let c be the associated weight vector. Remark that, as G is simple, that is does not contain parallel edges, if two 3-st-paths P 1 and P 2 are not node-disjoint, then they are of the form P 1 = (s, u, v, t) and P 2 = (s, v, z, t) with u, v, z ∈ V \ {s, t} and u = v = z = u. These two paths correspond in G st to paths (s, u, v ′ , t) and (s, v, z ′ , t). Conversely, two paths (s, u, v ′ , t) and (s, v, z ′ , t) of G st correspond to two paths (s, u, v, t) and (s, v, z, t) which are not node-disjoint. Consequently, when x is not feasible for the kNDHP, any maximum set of disjoint st-dipaths of the graph G st , for some demand (s, t) ∈ D, will contain two paths of the form (s, u, v ′ , t) and (s, v, z ′ , t), with u, v, z ∈ V \ {s, t} and u = v = z = u. Now we give the following procedure, that we call Procedure BuildZ, which aims to build a node Z ⊆ V . The procedure works as follows. Let Z ⊆ V be a node set of G and denote by Z the nodes of G st corresponding to those of Z, that is Z = {u, u ′ such that u ∈ Z}. At the begining of the procedure Z = ∅. Now, compute a maximum flow from s to t in the graph G st \ Z, with each arc a ∈ A st having the capacity c(a). This gives a maximum set P of arc-disjoint st-dipaths in G st \ Z. Remark that some of those paths may correspond to non node-disjoint 3-st-paths of G, that is they are of the form (s, u, v ′ , t) and (s, v, z ′ , t). Let P ′ be the set of these paths. Also let P ′ be the set of paths of G corresponding to those of P ′ and U ⊆ V the set of nodes of G which are shared by two paths of P ′ . Now, add to Z the nodes of U and repeat this procedure until |Z| ≥ k or U = ∅. It should be noticed that when U = ∅, the arc-disjoint st-dipaths obtained by the computation of the maximum flow in G st \ Z correspond to node-disjoint 3-st-paths of G \ Z.

The identification of the nodes of U can be easily done by simply watching, for each node u ∈ V \ Z, the arcs entering and leaving nodes u and u ′ with flow value 1 and 0. Namely, consider a node v ∈ U. This means that after the maximum flow computation, there are two paths (s, u, v ′ , t) and (s, v, z ′ , t). Since the arc capacities are either 0 or 1, this means that • the flow value on arc (s, v) is 1,

• the flow value on arc (v, z ′ ) is 1, for some z ∈ V \ {s, t, v}, • the flow value on arc (v ′ , t) is 1. Figure 6.2 illustrates the above remark. The solid lines represent arcs having flow value 1 and dashed lines represent arcs with flow value 0. The flow value of the arcs represented by dotted lines may be 0 or 1.

Observe that using Edmonds-Karp algorithm's [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF] for each maximum flow computation, the identification of the node set U at each iteration can be implemented to

. Also, Procedure BuildZ runs in at most k iterations. Therefore, Procedure BuildZ builds a node set Z in O(k|E| 2 |V |) time. Now, we give the following theorem.

Theorem 29 Let x ∈ {0, 1} E be an integral solution and (s, t) ∈ D. Assume that x satisfies all the st-cut and 3-st-path-cut inequalities. Let Z ⊆ V be the node set obtained by the application of Procedure BuildZ. Then, there is a st-node-cut or a 3-

st-node-path-cut inequality violated by x if and only if |Z| ≤ k -1 and the minimum weight of a cut of

Proof. Suppose that |Z| ≤ k -1 and a minimum weight st-dicut δ + Gst\Z ( W ), w.r.t weight vector c, is such that c(δ + Gst\Z ( W )) < k -|Z|. As shown by Bendali et al. [START_REF] Bendali | The k edge-disjoint 3-hop-constrained paths polytope[END_REF], this st-dicut corresponds to an st-cut or a 3-st-path-cut of G \ Z. Let C be this st-cut or 3-st-path-cut. Moreover, we have that

6.2 Branch-and-Cut Algorithm for the kNDHP with L = 4 and k = 2

In this section, we present a Branch-and-Cut algorithm for the kNDHP when L = 4 and k = 2, based on the formulation presented in [START_REF] Huygens | Integer programming formulations for the two 4-hop-constrained paths problem[END_REF]. The formulation uses inequalities (5.1)- (5.6). First, we present the general framework of the algorithm and then present the separation procedures we have devised for the inequalities involved in the algorithm.

The general framework

The general framework of the algorithm is similar to the one presented before. To reinforce the linear relaxation of this problem we add the rooted partition inequalities (5.25) in the cutting plane algorithm. The separation of the inequalities used in the Branch-and-Cut algorithm are performed in the following order 1) st-cut and st-node-cut inequalities,

2) rooted partition inequalities,

3) L-st-path-cut inequalities and L-st-node-path-cut inequalities (only for integral solutions).

We apply the rooted partition inequalities (5.25) for the rooted 2NDHP (that is, when the set of demands is rooted in a single node) and do not apply them when arbitrary demands are considered. Notice that the L-st-path-cut and L-st-node-path-cut inequalities are separated only for integral solutions. Indeed, as we will see in the next subsection, these two families of inequalities can be efficiently separated when the solution x * is integral. In the following, we describe the separation algorithms we have devised for the inequalities (5.1)-(5.4) and the rooted partition inequalities (5.25).

Separation procedures

Separation of st-cut inequalities and st-node-cut

It is well known that the separation of the st-cut inequalities (5.1) (resp. the st-nodecut inequalities (5.

Abstract

Given a weighted undirected graph and an integer k, the k-nodeconnected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the knode-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem. Next, we investigate the hopconstrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L.

We propose an integer linear programming formulation for L = 2, 3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B&C algorithm for solving the problem along with some computational results.