Marie Laurence Knittel
email: marie-laurence.knittel@univ-lorraine.fr

Rafael Marín
email: rafael.marin@univ-lille.fr

Developing a resource for -ance nouns, and related verbs and adjectives

.

We describe the procedure we followed to extract relevant data from Lexique3 and the tests we used to pair Nance with their relevant bases. The correlation between the mass/count properties of Nance, the (a)telicity of the related verbs, and the open/closed scale of the related adjectives is then discussed in detail.

Our results show that over 90% of Nance are mass. Mass Nance are mostly related to stative verbs and unbounded adjectives, in line with the Extended Boundedness Hypothesis. As for count Nance, all are related to telic verbs, but a significant number of them are unexpectedly paired with non-degree (vs bounded) adjectives. Therefore, the EBH is only partially confirmed by count Nance.

So as to expand AdVeNance, we began to examine nouns in -ence (Nence, e.g. préférence 'preference'). A preliminary analysis of these nouns and their verbal bases reveals that, similarly to Nance, most Nence are mass, and most of mass Nence derive from stative verbs.

Introduction

French -ance nominals (Nance) constitute a relatively small but most interesting noun class, since they can be related to verbs (1a), adjectives (1b) or both (1c) [START_REF] Dal | Les noms en -ance/-ence du français : quel(s) patron(s) constructionnel(s) ? Actes du CMLF[END_REF][START_REF] Knittel | Les noms en -ance : un panorama[END_REF].

(1) a. appartenance N / appartenir V 'belonging' / 'to belong' b. constance N / constant Adj 'consistency', 'steadyness' / 'constant' c. abondance N / abonder V / abondant Adj 'abundance' / 'to abound' / 'abundant' As a consequence, they constitute a useful set of data to study the possible semantic relationship between three categories. In particular, they allow to check an extended version of the Boundedness Hypothesis [START_REF] Bach | An extension of classical transformational grammar[END_REF][START_REF] Mourelatos | Events, processes and states[END_REF][START_REF] Jackendoff | Parts and boundaries[END_REF][START_REF] Brinton | Aspectuality and countability[END_REF], which takes into account not only nouns and verbs, but also adjectives.

There is a broad agreement in the linguistic community that each category prototypically conveys a certain type of meaning. Verbs would then denote eventualities, nouns entities and adjectives properties. Each of these concepts is in turn characterized by a typical semantic property. Verbs fall into aspectual classes; nouns can be mass or count, and adjectives, when gradable, are either bounded or unbounded.

In its original version, the Boundedness Hypothesis [START_REF] Bach | An extension of classical transformational grammar[END_REF][START_REF] Mourelatos | Events, processes and states[END_REF] predicts a parallelism between verbal and nominal properties. More specifically, it predicts that mass nouns, as describing unbounded entities, should be related to atelic verbs, that describe unbounded events; conversely, count nouns parallel telic verbs, both describing bounded entities.

The Extended Boundedness Hypothesis, that we propose here, adds adjectives [START_REF] Paradis | Adjectives and boundedness[END_REF] to the initial hypothesis, and predicts that open-scale adjectives should be paired with mass nouns and atelic verbs, while closed-scale adjectives are paired with count nouns and telic verbs. In line with [START_REF] Gumiel-Molina | On degree minimizers in Spanish[END_REF], we assume that closed-scale adjectives are those having a closed upper bound, i.e. a scale with a final boundary.

This work aims at verifying empirically the Extended Boundedness Hypothesis by means of the analysis of a significant number of Nance nouns, extracted from Lexique 3, and their related verbs and/or adjectives. The annotation of these nouns, verbs and adjectives has led to the elaboration of AdVeNance, a morpho-semantic resource that will be described here.

In the following section, we describe the bases of AdVeNance; particularly, the selection of Nance (ant their related verbs and adjectives), and the annotation of their relevant properties. In section 3, we present the main results we have found. In section 4, we include a comparison between Nance and a new group of nouns, those ending in -ence (Nence), that we will also include in AdVeNance. Finally, section 5 summarizes our main findings and points out some questions for further research.

The AdVeNance resource

Aims

The aim of the AdVeNance resource is to provide a list of Nance with the semantically related verbs and/or adjectives (1), annotated according to the properties relevant to the Extended Boundedness Hypothesis: nominal countability, verbal aspect and adjectival scalarity. The resource appears as a database providing columns presenting each category and its relevant feature, as shown in

Nance selection

The nouns that we analyzed were extracted from the resource Lexique [START_REF] New | Une base de données lexicales du français contemporain sur internet : LEXIQUE[END_REF]. From a total of 244 Nance listed in Lexique, we had to discard the nouns that were irrelevant for our study. Thus, we excluded non-suffixed nouns (2a), nouns without morphological relation with verbs or adjectives (2b), nouns build on other Nance by prefixation (2c), and spelling doublets (2d).

(

Matching Nance with their base(s)

The first annotation step was to pair the Nance kept at the end of the above selection with their related category in an appropriate manner, so as to discard improper pairs or triplets.

To do so, we used the tests provided in the literature. On the one hand, to identify Nance related to adjectives, we used the tests provided by [START_REF] Rainer | I nomi di qualità nell'italiano contemporaneo[END_REF], [START_REF] Van De Velde | Le spectre nominal : des noms de matières aux noms d'abstractions[END_REF], [START_REF] Flaux | Les noms en français : esquisse de classement[END_REF], [START_REF] Beauseroy | Syntaxe et sémantique des noms abstraits statifs : des propriétés verbales et adjectivales aux propriétés nominales[END_REF]. On the other hand, Nance related to verbs were identified using tests from [START_REF] Grimshaw | Argument structure[END_REF], [START_REF] Melloni | Polysemy in Word Formation : The Case of Deverbal Nominals[END_REF], [START_REF] Balvet | La ressource Nomage. Confronter les attentes théoriques aux observations du comportement linguistique des nominalisations en corpus[END_REF], [START_REF] Fradin | Remarks on state denoting nominalizations[END_REF][START_REF] Fradin | Les nominalisations et la lecture 'moyen[END_REF][START_REF] Fradin | La variante et le double[END_REF], [START_REF] Kerleroux | Il y a nominalisation et nominalisation[END_REF].

In doing so, we were led to check if the formal closeness between Nance and the potential verbal or adjectival basis reflected a regular semantic pattern, which was not always the case. For example, ambiance 'atmosphere' does not react in the appropriate manner to the above tests, and cannot be easily related to ambiant Adj , 'ambient', 'surrouding'2 . That is why we choose to discard this pair and similar ones.

Another necessary step, as far as adjectives are concerned, was to identify and eliminate forms that behave rather as present participles or as nouns. For example, in the case of gérance 'stewardship', the potential base gérant does not qualify as an adjective, but either as a noun or as the present participle of gérer 'to manage'.

At the end of this stage, we gathered a list of 112 nouns, among which 72 are related to verbs, 97 to adjectives, and 56 to both, as shown in Table 2.

Nance [112] Related to V Non-related to V Total Related to Adj 56 41 97 Non-related to Adj 16 -Total 72 41

Table 2. Distribution of Nance and their related categories

The availability of triplets (N/V/Adj) confirmed previous observations [START_REF] Dal | Les noms en -ance/-ence du français : quel(s) patron(s) constructionnel(s) ? Actes du CMLF[END_REF][START_REF] Knittel | Les noms en -ance : un panorama[END_REF], that Nance can be related to verbs and/or adjectives. Although in a reduced number, the nominals of the AdVeNance resource constitute a reliable list of nouns paired with their related verbs and/or adjectives.

Annotation

After the matching of the 112 Nance with their corresponding verb and/or adjective, we proceeded to the examination of their relevant characteristics, namely mass/count opposition for nouns, aspect for verbs and scalarity for adjectives.

The mass/count distinction was annotated following a methodology similar to that of [START_REF] Dugas | Héritage sémantique des noms aux verbes : Étude des verbes dénominaux en français[END_REF], mostly applying the same tests. Unlike mass nouns, count nouns accept plurals (3a), count quantifiers (3b) and definite numerals (3c). On the other hand, unlike count nouns, mass nouns allow partitive articles (4a), as well as modification by intensifiers (4b).

(3) On the other hand, verbs have been annotated with respect to the four Vendlerian classes (states, activities, accomplishments and achievements). As illustrated in Table 3, these four classes are characterized by means of three features: dynamicity, telicity and duration. Thus, states are the only verbs denoting non-dynamic situations; both states and activities are atelic, while accomplishments and achievements are telic; as for achievements, they are the only verbs denoting punctual (i.e. non durative) situations. 3. Aspectual features of the Vendlerian verb classes.

Dynamicity Telicity Duration

State - - + Activity + - + Accomplishment + + + Achievement + + - Table
Regarding the annotation of verbs, we used a battery of standard aspectual tests [START_REF] Dowty | Word meaning and Montague grammar[END_REF], following a general procedure as the one described in [START_REF] Balvet | La ressource Nomage. Confronter les attentes théoriques aux observations du comportement linguistique des nominalisations en corpus[END_REF].

States (préférer 'to prefer'), unlike dynamic predicates, are not compatible with the progressive form être en train de 'to be V-ing' (5a), and are not good answers either to questions of the type -Que s'est-il passé hier? 'What happened yesterday?' (5b).

(5) States a.

*Il est en train de préférer les bettes. lit.: 'He is preferring chard.' b.

-Que s'est-il passé hier? 'What happened yesterday?' *-Il a préféré les bettes.

lit.: -He preferred chard.'

Atelic predicates are only compatible with for x time modifiers (6a), while telic predicates are compatible with in x time modifiers (6b). For similar reasons, telic predicates combine with expressions such as 'to take x time to V' (6c). Elle a réparé la voiture en trois heures.

'She repaired the car in three hours.' c.

Il m'a fallu trois heures pour réparer la voiture. 'It took me three hours to repair the car.'

Finally, among telic predicates, achievements are not compatible with the aspectual semiauxiliaries continuer 'to keep on' or arrêter 'to stop' (7).

(7) *Marie a {continué/arrêté} de trouver le vaccin.

'Marie {continued/stopped} to find the vaccine.'

All these tests are summarized in Table 4, which illustrates the way we have used them so as to assign aspectual classes to verbs.

State

Activity Accomplishment Achievement

Progressive - + + - What happened - + + + for x time + + - - in x time / take x time - - + + keep on + + + - stop - + + -
Table 4. The behavior of aspectual classes according to a battery of tests.

Finally, adjectives have been examined with respect to gradability and scalarity. The first distinction bo be made is between degree and non-degree adjectives (8a): only the former accept modification by très 'very' and similar adverbials [START_REF] Paradis | Adjectives and boundedness[END_REF]. After that, we distinguished, among degree adjectives, those encoding open scales from those encoding closed scales [START_REF] Kennedy | Scale structure, degree modification, and the semantics of gradable predicates[END_REF]. Following standard views [START_REF] Kennedy | Scale structure, degree modification, and the semantics of gradable predicates[END_REF], we used diagnostics oriented towards upper bounds and others oriented to lower bounds. Thus, for example, closed upper bounds accept modification by complètement 'completely' (8b), while closed lower bounds accept modification by légèrement 'sightly' (8c). However, according to EBH, we assume that bounded (or closed) adjectives are those having a closed upper bound. On the other hand, open-scale adjectives, unlike closed-scale ones, accept diagnostics on comparison (8d-e).

(8) a. très petit 'very small' ; *très mortel 'very mortal' b. {complètement / légèrement} transparent 'completely / slightly transparent' c. *{complètement / légèrement} étranger 'completely / slightly foreign' d. Marie est grande pour une enfant de neuf ans.

'Marie is tall for a nine year old girl.' e. Par rapport à son ami, Marie est grande.

'Compared to her friend, Marie is tall.'

Results

Our first result concerns the number of unbounded items in the three categories under examination.

We This provides a first confirmation of the accuracy and coverage of the Extended Boundedness Hypothesis. The following sections describe our results in more details.

Deverbal Nance and their corresponding verbs

The distribution of the aspectual properties of verbs with respect to the countability of Nance are shown in Table 5 The data in Table 5 clearly confirm that the overwhelming majority of mass Nance (98.4%) are related to atelic verbs (10a), which is in line with [START_REF] Balvet | La ressource Nomage. Confronter les attentes théoriques aux observations du comportement linguistique des nominalisations en corpus[END_REF]. More precisely, we notice that 85,7% of these atelic verbs are stative (10b), an observation also made by [START_REF] Fábregas | Lexical categories and aspectual primitives: The case of Spanish -ncia[END_REF] for Spanish. Conversely, the verbs related to count nouns are systematically telic (11). These results clearly confirm the Boundedness Hypothesis as far as nouns and verbs are concerned.

(10) a. assistance 'assistance' > assister 'to assist'; ignorance 'ignorance' > ignorer 'to be unaware'; maltraitance 'abuse'> maltraiter 'to abuse' b. dominance 'dominance' > dominer 'to dominate'; gouvernance 'governance' > gouverner 'to govern', 'to rule'; nuisance 'nuisance', 'disturbance' > nuire 'to harm', 'to affect'

(11) délivrance 'delivery', 'deliverance' > délivrer 'to issue', 'to set free'; soutenance 'defense (of a thesis)' > soutenir 'to defend (a thesis)'; vengeance 'revenge' > (se) venger 'to retaliate' According to the Extended Boundedness Hypothesis, we should find unbounded adjectives in relation with mass nouns, and bounded adjectives related to count nouns. Table 6 shows that this prediction is not completely borne out. On the one hand, 79.12% of mass nouns are related to unbounded adjectives (12), while there is no count nouns related to an unbounded adjective, in line with the Extended Boundedness Hypothesis. However, count nouns are mostly paired with non-degree adjectives (13a), where bounded adjectives were expected (13b). This result, although unexpected and in need of closer analysis, has to be weighed against the reduced number of count nouns paired with adjectives (6/97).

Deadjectival Nance and their corresponding adjectives

(12) abondance 'abundance' > abondant 'abundant'; endurance 'endurance' > endurant 'enduring'; répugnance 'disgust' > répugnant 'disgusting'

(13) a. naissance 'birth' > naissant 'nascent'; renaissance 'revival' > renaissant 'reviving'; suppléance 'replacement', 'substitution' > suppléant 'substitute' b. défaillance 'failure' > défaillant 'defective'

Nance related with verbs and adjectives

Finally, Table 7 sums up the properties of Nance related with both verbs and adjectives, and confirms our previous results.

Nouns [56] Verbs 7. The properties of verbs and adjectives related with Nance.

As before, we observe that mass nouns are mostly paired with atelic verbs and unbounded adjectives (14a), while the few count nouns that we have found are paired with telic verbs and nondegree adjectives (14b). In the latter case, however, the reduced number of examples prevents us to draw a firm conclusion. Similarly, the unavailability of count nouns related to atelic verbs is an interesting result, corresponding to our expectations. However, no strong conclusion can be drawn from such a number of cases.

( 2).

Regarding the relevant semantic features of each category, we have for now completed the annotation process for both nouns and verbs, but we do not yet have gathered all the data for adjectives.

In the case of nouns, we observed a prevalence of mass nouns (99/109), which was also the case for Nance. Similarly, verbs, although less represented for Nence than Nance, are mostly stative (25/29).

Table 9 These data lead us to conclude that Nance and Nence, as well as their related categories, display similar characteristics. In both cases, we observe a predominance of mass nouns and stative verbs. Thus, unboundedness is a consistent pattern of at least two of the categories involved.

Although more research is needed to examine thoroughly the relations between the mass/count properties of Nence and the aspectual properties of their related verbs on the one hand, and the gradable / scalar properties of their related adjectives on the other hand, we can conclude that the two sets of data we examined tend to confirm the Extended Boundedness Hypothesis.

Concluding remarks and further research

The AdVeNance resource contains 112 Nance associated with their corresponding verbs and/or adjectives. All its items are annotated for the features prototypical to their category: mass/count for nouns. lexical aspect for verbs, scalarity for adjectives. The results provided by the annotation evidence that mass nouns are mostly related with atelic verbs and/or unbounded adjectives, thus confirming the Extended Boundedness Hypothesis [START_REF] Bach | An extension of classical transformational grammar[END_REF][START_REF] Mourelatos | Events, processes and states[END_REF][START_REF] Paradis | Adjectives and boundedness[END_REF]). Although we do not have a full picture of Nence and their related verbs and adjectives yet, the first results we obtained seem to point in the same direction.

The next step of the AdVeNance project is to make the resource we built available to the community as a remotely interrogatable database.

As a further development, we consider comparing the properties of Nance and their related verbs and adjectives with their Italian and Spanish counterparts, for which similar cross-categorial relations are observed.

( 6 )

 6 Telic vs atelic predicates a. Il s'est promené {pendant/*en} trois heures. 'He walked {for/*in} three hours.' b.

Table 1 .

 1

	Nouns	Countability Verbs	Aspect	Adjectives Scalarity
	confiance	mass			confiant	closed-scale
	persistance mass	persister state	persistant open-scale
	vengeance count	venger	achievement

Table 1 .

 1 Sample of the AdVeNance resource.

  connaissance 'knowledge'; méfiance 'distrust', 'suspicion' b. consister Stative 'to consist'; dominer Stative 'to dominate' vs. croître Dynamic 'to grow'; errer Dynamic 'to wander' c. arrogant 'arrogant'; important 'important'; répugnant 'disgusting'

	noticed indeed a significant proportion of mass nouns (103/112) (9a), atelic verbs (62/72), among
	which 54 are stative) (9b), and unbounded adjectives (72/97 upper open)
	a. élégance 'elegance';

Table 5 .

 5 . Aspectual properties of verbs related to Nance.

	Verbs

Table 6 .

 6 Table6presents the distribution of degree and scalar properties of adjectives with respect to the countability of Nance. Scale properties of adjectives paired with Nance.

	Nouns [97]	Adjectives
			Non-degree	9	9,89%
	Mass	91 Unbounded	72 79.12%
			Bounded (upper)
			Non-degree	5	83.3%
	Count	6 Unbounded	0	0%
			Bounded (upper)	1	16.7%

Table 8 .

 8 14) a. condescendance 'condescendance' > condescendre 'to condescend' / condescendant 'condescending'; médisance 'slander' > médisance 'slander' / médisant 'slandering' b. naissance 'birth' > naître 'to be born' / naissant 'nascent'; suppléance 'replacement', 'substitution' > suppléer 'to substitute'/ suppléant 'substitute'As a further step, we began to expand AdVeNance by also including nouns ending in -ence (Nence), that stand in the same relation with verbs and adjectives as Nance, as shown in example (15).From the 212 Nence extracted from Lexique3, we discarded nouns that are not paired with verbs or -ent adjectives (conférence 'conference') and prefixed nouns (incohérence 'inconsistency', from cohérence 'consistency'), similarly to what we did for Nance. The few Nence referring to concrete objects (cf. semence 'seed') were also eliminated. We finally obtained a list of 109 forms related to verbs (15a), adjectives ending in -ent (15b) and both (15c), as displayed in Table8. Distribution of Nence and their related categories Table8shows that most Nence are related to adjectives (103/109), whereas verbs are less represented (29/109, among which 6 Nence with verbs only). By contrast, we found 97 Nance related to adjectives, 72 to verbs and adjectives, and 16 to verbs only, on a total of 112 nouns (see Table

	4 A comparison with Nence
	(15) a. préférence N / préférer V		'preference' / 'to prefer'
	b. éloquence N / éloquent Adj		'eloquence' / 'eloquent'
	c. négligence N / négliger V / négligent Adj	'negligence', 'carelessness' / 'to neglect' /
			'negligent', 'careless'
	Nence [109]	Related to V Non-related to V	Total
	Related to Adj	23	80	103
	Non-related to Adj	6	-
	Total	29

Table 9 .

 9 provides a comparison of the distribution of nominal countability and verbal aspect for Nence and Nance. Comparison of the properties of Nance and Nence and their related verbs.

		Features	Nence (109)	Nance (112)
	Nouns	Mass	99 (90,82%)	102 (91,07%)
		Count	10 (9,17%)	9 (8,03%)
	Verbs	Total	29 (100%)	72 (100%)
		State	25 (86,2%)	54 (75%)
		Activity	2 (6,9%)	8 (11,11%)
		Accomplishment	-	2 (1,78%)
		Achievement	2 (6,9%)	8 (11,11%)

The AdVeNance project is supported by the Maison des Sciences de l'Homme de Lorraine (MSHL-USR 3261).

The definitions found in the CNRTL (https://www.cnrtl.fr) confirm this discrepancy. AMBIANT: Qui entoure ou circule autour, qui environne. [Engl. ambient, surrouding] AMBIANCE: Qualité du milieu (matériel, intellectuel, moral) qui environne et conditionne la vie quotidienne d'une personne, d'une collectivité.[Engl. atmosphere]


Bernard Fortz
email: bernard.fortz@ulb.ac.be

Topology-Constrained Network Design

Introduction

Many network design problems considered in this book aim at optimizing simultaneously the decisions on opening links (with an associated fixed cost) and the capacity to allocate to these links in order to satisfy a set of demands, with a variable routing cost associated to these demands. However, in certain situations, the demand is not known in advance, or involves a lot of uncertainty, leading to an approach in two phases, where the topological design of the network (considering only fixed cost of opening links) is considered first, and the decisions on routing and capacity allocation taken in a second (later) stage. This approach is relevant when the fixed costs are high compared to routing and capacity costs, and/or when topological decisions do not affect too much capacity decisions. For example, in telecommunications, fiber optic cables have a virtually unlimited capacity, and the limitation of capacity arises from equipment placed in the nodes of the network (routing cards). While decisions to dig a trench to lay a cable are very costly and must be taken over a long term horizon, increasing capacity by adding or upgrading equipment into nodes is relatively simple and cheap.

In this chapter, we study models and techniques for long-term planning of the first phase, i.e., we only deal with topological aspects. Two main issues appear in the planning process of networks: economy and survivability. Economy refers to the construction cost, which is expressed as the sum of the edge costs, while survivability refers to the restoration of services in the event of node or link failure. The goal is then to determine a set of links connecting all nodes under some survivability criteria.

For example, in telecommunications, the network is seen as a given set of nodes and a set of possible fiber links that have to be placed between these nodes to achieve connectivity and survivability at minimum cost. Until about 25 years ago, the limited capacity of copper cables resulted in highly diverse routing. The developments in fiber-optic technology have led to components that are cheap and reliable, having an almost unlimited capacity. The introduction of such a technology has made hierarchical routing and bundling of traffic very attractive. This approach has resulted in sparse, even treelike network topologies with larger amounts of traffic carried by each link. Trees satisfy the primary goal of minimizing the total cost while connecting all nodes. However, only one node or edge breakdown causes a tree network to fail in its main objective of enabling communication between all pairs of nodes.

This means that some survivability constraints have to be considered while building the network. Losing end-to-end customer service could lead to dramatic loss of revenue for commercial service providers. Constructing network topologies that provide protection against failures has become one of the most important problems in the field of network design.

The most studied models deal with k-connectivity requirements, i.e., the ability to restore network service in the event of a failure of at most k -1 components of the network. Among them, the minimum-cost two-connected spanning network problem consists in finding a network with minimal total cost for which two node-disjoint paths are available between every pair of nodes. This means that two-connected networks are able to deal with a single link or node failure. Two-connected networks have been found to provide a sufficient level of survivability in most cases, and a considerable amount of research has focused on so-called low-connectivity constrained network design problems, i.e., problems for which each node j is characterized by a requirement r j ∈ {0, 1, 2} and min{r i , r j } node-disjoint paths between every pair of nodes i, j are required.

Two-connectivity seems a sufficient level of survivability for most networks, since the probability of dealing with two simultaneous failures is usually very low for fiber optics technologies used in telecommunications networks. However, it turns out that the optimal solution of this problem is often very sparse (in many cases such as a Hamiltonian cycle). In such a topology, primary routing paths and re-routing paths in case of failure might become very long. This introduces another difficulty as it causes large delays in the network.

To avoid this, two kinds of solutions have been proposed in the literature. The first one imposes a constraint on the length of the paths (in terms of number of links crossed), the so-called hop-constrained models. The second approach consists of imposing that each edge belongs to at least one cycle whose length is bounded by a given constant, which ensures the existence of an alternate short path in case of failure.

The chapter is organized as follows. After introducing in Section 2 the specific notation and some fundamental definitions used in the chapter, we begin by the simplest but fundamental problem: the design of connected networks (and in particular the minimum spanning tree problem) is covered in Section 3. Next we turn our attention to networks requiring a higher level of survivability in Section 4. Sections 5 and 6 consider problems in which the length of re-routing paths in case of failure is limited, by introducing hop constraints and rings of bounded lengths, respectively. Section 7 provides links to the relevant literature that was used as basis to this chapter, as well as interesting references to dig further. We conclude in Section 8 with some perspectives on future trends in topological network design.

Notation and Definitions

Most models considered in this chapter are based on undirected graphs as capacity is not involved and links are usually bi-directional. Therefore, the given sets of nodes and possible connections are represented by an undirected graph G = (N, E) where N is the set of nodes and E is the set of edges that represent the possible pairs of nodes between which a direct connection can be established. The graph G may have parallel edges but should not contain loops. Throughout this chapter, n = |N | and m = |E | will denote the number of nodes and edges of G.

Given a subset of nodes S ⊂ N , the edge set

δ(S) = {{i, j} ∈ E | i ∈ S, j ∈ N \S}
is called the cut induced by S. We write δ G (S) to make clear -in case of possible ambiguities -with respect to which graph the cut induced by S is considered. For a single node i ∈ N , we denote δ(i) = δ({i}). The set

E(S) = {{i, j} ∈ E | i ∈ S, j ∈ S}
is the set of edges having both end nodes in S. We denote by G(S) = (S, E(S)) the subgraph induced by edges having both end nodes in S. If E(S) is empty, S is an independent set. G/S is the graph obtained from G by contracting the nodes in S to a new node w (retaining parallel edges). Given two subsets of nodes S 1 and S 2 , S 1 ∩ S 2 = ∅, the subset of edges having one endpoint in each subset is denoted by

[S 1 : S 2 ] = {{i, j} ∈ E | i ∈ S 1 , j ∈ S 2 }.
We denote by Nz = N \{z} and Ee = E\{e} the subsets obtained by removing one node or one edge from the set of nodes or edges. Gz denotes the graph (Nz, E\δ(z)), i.e., the graph obtained by removing a node z and its incident edges from G. This is extended to a subset Z ⊂ N of nodes by the notation G -Z = (N \Z, E\(δ(Z) ∪ E(Z))).

Each edge e = {i, j} ∈ E, has a fixed cost c e = c i j representing the cost of establishing the direct link connection, and a length d e = d i j = d(i, j). It is assumed throughout this work that these edge lengths satisfy the triangle inequality, i.e.,

d(i, j) + d( j, k) ≥ d(i, k) for all i, j, k ∈ N .
The cost of a network (N, F ) where F ⊆ E is a subset of possible edges is denoted by c(F ) = e ∈ F c e . The distance between two nodes i and j in this network is denoted by d F (i, j) and is given by the length of a shortest path linking these two nodes in F .

Without loss of generality, all costs are assumed to be nonnegative, because an edge e with a negative cost c e will be contained in any optimum solution.

For any pair of distinct nodes s, t ∈ N , an [s, t]-path P is a sequence of nodes and edges (v 0 , e 1 , v 1 , e 2 , . . ., v l-1 , e l , v l ), where each edge e i is incident to the nodes v i-1 and v i (i = 1, . . ., l), where v 0 = s and v l = t, and where no node or edge appears more than once in P. A collection P 1 , P 2 , . . ., P k of [s, t]-paths is called edge-disjoint if no edge appears in more than one path, and is called node-disjoint if no node (other than s and t) appears in more than one path. A cycle (containing s and t) is a set of two node-disjoint [s, t]-paths. A Hamiltonian cycle is a cycle using each node of the network exactly once. A graph G = (N, E) is k-edge-connected (resp., k-nodeconnected) if, for each pair s, t of distinct nodes, G contains at least k edge-disjoint (resp., node-disjoint) [s, t]-paths.

When the type of connectivity is not mentioned, we assume node-connectivity. The edge connectivity (resp., node-connectivity) of a graph is the maximal k for which it is k-edge-connected (resp., k-node-connected). A 1-edge-connected network is also 1-node-connected, and we call it simply connected. A cycle-free graph is a forest and a connected forest is a tree. A connected component of a graph is a maximal connected subgraph. If Ge has more connected components than G for some edge e, we call e a bridge. Similarly, if Z is a node set and G -Z has more connected components than G, we call Z an articulation set of G. If a single node forms an articulation set, the node is called articulation point.

Node In order to formulate network design problems as integer linear programs, we associate with every subset F ⊆ E an incidence vector y F = (y F e ) e∈E ∈ {0, 1} | E | by setting

y F e =
1 if e ∈ F , 0 otherwise .

Conversely, each vector y ∈ {0, 1} | E | induces a subset

F y = {e ∈ E | y e = 1}
of the edge set E. For any subset of edges F ⊆ E we define

y(F ) = e∈ F y e .

Connected Networks

A fundamental constraint in topological network design is to ensure all nodes can communicate. This translates into the constraint that a path must exist between any pair of nodes in the graph, or in other terms, the constructed graph must be connected.

The problem of finding a minimum cost connected network is polynomially solvable: if costs are non-negative, there exists an optimal solution with the minimum number n -1 of edges in a connected graph, hence the problem reduces to the wellknown Minimum Spanning Tree problem. A simple algorithm to solve it is the greedy algorithm: start with an empty solution; order the edges of G = (N, E) by increasing costs; iteratively consider each edge in this sorted list and add it to the solution if it does not form a cycle with the edges already selected.

The property that a spanning tree is a graph with n -1 edges and without cycles is the basis of the greedy algorithm described above. This property also leads to an integer programming formulation of the problem. Let y e be a binary variable indicating whether edge e ∈ E is part of the spanning tree. Then the minimum spanning tree problem can be formulated as Minimize e∈E c e y e

(1)

Subject to y(E) = n -1, (2)
y(E(S)) ≤ |S| -1 ∀∅ S ⊂ N, (3)
y e ∈ {0, 1}, ∀ e ∈ E, (4)
where constraint (2) imposes the cardinality constraint and constraints (3) are subtour elimination constraints that eliminate all possible cycles from the solution.

Although there is an exponential number of subtour elimination constraints, they can be separated in polynomial time by a simple minimum cut computation. Primal-dual arguments can be used to show that the linear programming relaxation of formulation (1)-( 4) is integer, and its extreme points coincide with the incidence vectors of spanning trees. Moreover, the same arguments can be used to prove the correctness of the greedy algorithm.

Another formulation for the minimum spanning tree problem is obtained by considering a spanning tree as a connected subgraph with n -1 edges. Connectivity can be imposed by forcing each cut in the graph to contain at least one edge, leading to the cut-set formulation Minimize e∈E c e y e

(5)

Subject to y(E) = n -1, (6) y(δ(S)) ≥ 1 ∀∅ S ⊂ N, (7)
y e ∈ {0, 1}, ∀ e ∈ E, (8)
where subtour elimination constraints have been replaced by cut inequalities (7).

In general, the linear relaxation of ( 5)-( 8) has fractional extreme points and therefore its polytope strictly contains the polytope induced by ( 1)-( 4). Cut inequalities can be generalized: Consider a partition S 1 , S 2 , . . ., S p of N into p nonempty subsets. Any spanning tree contains at least p -1 edges joining the sets S 1 , S 2 , . . ., S p , leading to the valid inequality 1 2

p i=1 y(δ(S i )) ≥ p -1 (9)
that is usually called partition inequality or multi-cut inequality. Cut inequalities ( 7) are a special case of ( 9) with p = 2. Again, it is possible to show that the polyhedron of the linear relaxation of the formulation given by ( 6), ( 9), ( 8) has integer extreme points. Hence the linear relaxations of the multi-cut formulation and of the subtour formulation are equivalent and both define the convex hull of incidence vectors of spanning trees.

The subtour and multi-cut formulations are ideal, but are not usable as such in practice, as they suffer from an exponential number of constraints. However, a cutting-plane approach can be used, as both classes of inequalities can be separated in polynomial time.

Another approach is to model the problem with extended formulations, by introducing new sets of variables but keeping the number of constraints polynomial. One of these extended formulations makes use of directed flows between an arbitrarily chosen root node r ∈ N and all the other nodes to impose connectivity. Indeed, the constructed graph is connected if and only if there exists a path from r to every other node k ∈ N \ {r }. To this aim, let us consider each node k r as a commodity, where one unit of flow originates at node r and must be delivered to node k. In order to represent these flows, we define A = {(i, j), ( j, i)|{i, j} ∈ E} as the directed set of arcs obtained by replacing each edge by two arcs in opposite direction. As in previous chapters, let x k i j be the flow of commodity k in arc (i, j). We can then formulate the minimum spanning tree problem as: Minimize e∈E c e y e (10) Subject to

j ∈N + i x k i j -j ∈N - i x k ji = w k i , ∀i ∈ N, ∀ k ∈ N \ {r } (11) x k i j + x k ji ≤ y e , ∀ e = {i, j} ∈ E, ∀ k, k ∈ N \ {r }, (12) y(E) = n -1, ( 13
)
x k i j ≥ 0, ∀ (i, j) ∈ A, ∀ k ∈ N \ {r }, (14)
y e ∈ {0, 1}, ∀ e ∈ E, (15)
where, for each i ∈ N , we define

N + i = { j ∈ N : (i, j) ∈ A}, N - i = { j ∈ N : ( j, i) ∈ A}. ( 16
)
Flow balance constraints (25) define a path between r and k with

w k i =        1, if i = r, -1, if i = k, 0, otherwise. ( 17
)
Each edge is given a natural direction as flows are directed away from the root r of the tree. Constraints (12) ensure that flow is sent only on edges present in the spanning tree, and always in the same direction. Finaly (13) are the usual cardinality constraints.

This formulation can also be seen as an application of the max flow-min cut theorem, and again leads to a complete description of the convex hull of incidence vectors of spanning trees (or to be more precise, the projection of the formulation on the space of y-variables defines this polyhedron). Now consider the general case where costs are not restricted to be positive. Then a minimum cost connected network is not necessarily a tree, as all negative cost edges should belong to the optimal solution, possibly creating cycles. Hence the subtour formulation is not valid anymore. However, the multi-cut and the flow formulations become valid if cardinality constraints ( 6) and ( 13) are removed. Moreover, the obtained formulations are ideal again in the sense that their linear relaxation (or its projection) describe the convex hull of incidence vectors of connected networks.

Survivable Networks

The major problem with the models presented above is that the topology tends to be sparse, as costs are minimized, the most extreme case being the minimum spanning tree. However, networks are subject to failures. For example, in the context of telecommunications, a network is seen as a set of gateway nodes (routers or telephone offices) and (fiber) links that are placed between nodes. If connectivity is the only constraint imposed on the network, a single link or node failure will disconnect it, which is clearly not acceptable.

In this context, survivability refers to the restoration of services in the event of node or link failure, or, in other words, a network is survivable if there exists a prespecified number of node-disjoint or edge-disjoint paths between any two nodes. Again, the only costs considered are construction costs, like the cost of digging trenches and placing a fiber cable into service.

A considerable amount of research has focused on low-connectivity constrained network design problems. These models can be described informally as follows: a set of nodes that have to be connected by a network is given. These nodes are classified according to their importance, namely the • special nodes, for which a "high" degree of survivability has to be ensured in the network to be constructed; • ordinary nodes, which have to be simply connected to the network;

• optional nodes, which may not be part of the network at all. The pairs of nodes between which a direct transmission link can be placed are also given, together with the cost of placing the fiber cable and putting it into service. The problem now consists in determining where to place fiber cables so that the construction cost, i.e., the sum of the fiber cable costs, is minimized and certain survivability constraints are ensured. For instance, we may require that • the destruction of any single link may not disconnect any two special nodes, or • the destruction of any single node may not disconnect any two special nodes.

These requirements are equivalent to ask that there exist

• at least two edge-disjoint paths, or • at least two node-disjoint paths between any two special nodes.

Higher survivability levels may be imposed by requiring the existence of three or more paths between certain pairs of nodes according to their importance class. However, up to now, low-connectivity requirements have been found to provide a sufficient level of survivability for telecommunications operators.

In graph-theoretic language, the set of nodes and possible link connections can be represented again by an undirected graph G = (N, E). The survivability requirement or importance of a node is modeled by node types. In particular, each node s ∈ N has an associated nonnegative integer r s , the type of s. Sometimes, we also write r(s) instead of r s . A network (N, F ), where F ⊆ E is a subset of the possible links, is said to satisfy the node-connectivity requirements, if, for each pair s, t ∈ N of distinct nodes, (N, F ) contains at least r(s, t) = min{r s , r t } node-disjoint [s, t]-paths.

Similarly, we say that (N, F ) satisfies the edge-connectivity requirements, if, for each pair s, t ∈ N of distinct nodes, the network contains at least r(s, t) edge-disjoint [s, t]-paths. If all node types have the same value k, it is equivalent to request that (N, F ) is k-node-connected or k-edge-connected.

We consider here the low-connectivity requirements, i.e., node types r s ∈ {0, 1, 2}. Using our previous classification of nodes,

• special nodes have type 2, • ordinary nodes have type 1, and • optional nodes have type 0.

To shorten notation, we extend the type function r to sets by setting r(S) = max{r s | s ∈ S} for all S ⊆ N, and con(S) = max{r(s, t) | s ∈ S, t ∈ N \S} = min{r(S), r(N \S)} ∀ S ⊂ N, ∅ S N .

We write con G (S) to make clear with respect to which graph con(S) is considered.

We can now formulate the connectivity constrained network design problem as the following integer linear program:

Minimize e ∈E c e y e (18)
Subject to y(δ(S)) ≥ con(S)

∀ S ⊂ N, ∅ S N, (19)
y(δ G-z (S)) ≥ con G-z (S) ∀ z ∈ N, S ⊂ N \{z}, ∅ S N \{z}, (20)
y e ∈ {0, 1} ∀ e ∈ E. (21)
It follows from Menger's Theorem that, for any feasible solution y of this program, the subgraph (N, F y ) of G defines a network satisfying the node-connectivity requirements. Removing (20), we obtain an integer linear program for edgeconnectivity requirements. Inequalities ( 19) are called cut inequalities, while inequalities (20) are called node cut inequalities.

The connectivity constrained network design problem is NP-hard in general. In particular :

• If r s ∈ {0, 1}, ∀s ∈ N , it reduces to the well-known NP-hard Steiner tree problem in networks. • If r s = 2, ∀s ∈ N , it consists in determining a minimum cost two-connected network. This last problem is NP-hard even if the graph is complete and costs satisfy the triangle inequality, since with an algorithm for this problem, one could decide whether a graph has a Hamiltonian cycle by associating a cost equal to 1 to all graph edges and cost equal to 2 to all non-graph edges.

However, for some particular connectivity requirements or costs, or when the underlying graph G is restricted, the problem may become polynomially solvable: This problem is NP-hard in general, but solvable in polynomial time in the case where either the number of nodes of type 0 or the number of nodes of type 1 is restricted.

• If r s = 1,
The general formulation described above and many of its special cases received a lot of attention. Polyhedral results have been obtained for different special cases of the model (see Section 7 for references to surveys on the subject).

An important class of valid inequalities for k-node-connected networks are obtained by a generalization of partition inequalities (9). First, we observe that the deletion of k -1 nodes from a k-node-connected network leaves a connected graph. Thus, if Z ⊆ N is a node set with exactly k -1 nodes and S 1 , S 2 , . . ., S p (p ≥ 2) is a partition of N \Z into p nonempty subsets, the inequality

1 2 p i=1 y(δ G-Z (S i )) ≥ p -1 (22)
is valid for the polytope of k-node-connected networks. These inequalities are called node-partition inequalities, and can be seen as a generalization of node cut inequalities (20). When r(s) = 2 for all s ∈ N , partition inequalities can be generalized further: consider again a patition S 1 , S 2 , . . ., S p (p ≥ 2) of N and let F ⊆ δ(S 1 ) with |F | odd. The F -partition inequality is defined as

1 2 p i=1 y(δ(S i )) -y(F ) ≥ p - |F | 2 . ( 23
)
To show it is valid, simply add valid inequalities

y(δ(S i )) ≥ 2 ∀ i = 2, . . ., p, -y e ≥ -1 ∀e ∈ F , y e ≥ 0 ∀e ∈ δ(S 1 ) \ F ,
divide by 2 and round up to obtain (23). The formulation above is in the space of design variables only, and involves an exponential number of constraints. As in Section 3, it is also possible to obtain valid polynomial-size models by the introduction of flow variables. We do it here only for edge-connectivity requirements. Assuming that we want to construct a network in which there are r(s, t) edge-disjoint paths between nodes s and t, we can define a set K of commodities where we have one commodity for each node pair s, t such that r(s, t) > 0, with a flow requirement of r(s, t) where the source and sink of commodity k are arbitrarily chosen between s and t.

Minimize

e ∈E c e y e (24) Subject to

j ∈N + i x k i j -j ∈N - i x k ji = w k i , ∀i ∈ N, ∀ k ∈ K, (25)
x k i j + x k ji ≤ y e , ∀ e = {i, j} ∈ E, ∀ k ∈ K, (26)
x k i j ≥ 0, ∀ (i, j) ∈ A, ∀ k ∈ K, (27)
y e ∈ {0, 1}, ∀ e ∈ E, (28)
Flow balance constraints (25) define r(s, t) paths between s and t for each commodity k ∈ K corresponding to the node pair s, t, with

w k i =        r(s, t), if i = s, -r(s, t), if i = t, 0, otherwise, (29)
and ( 26) impose that these paths are edge-disjoint.

Applying simple max-flow / min-cut arguments, it is quite easy to see that the linear relaxation of the flow formulation is equivalent to the formulation involving only design variables with an exponential number of constraints.

Hop Constraints

The models from the previous section usually lead to designs that are very sparse. In general, the survivability constraints alone may not be sufficient to guarantee a cost effective routing with a good quality of service. The reason for this is that the routing paths may be too long, leading to unacceptable delays. Since in most of the routing technologies, delay is caused at the nodes, it is usual to measure the delay in a path in terms of its number of intermediate nodes, or equivalently, its number of arcs (or hops). Thus, to guarantee the required quality of service, one can impose a limit on the number of arcs in the routing paths.

Given a graph G = (N, E) with nonnegative edge costs c e , e ∈ E, and a set of node pairs K (sometimes called commodities), we study the problem of constructing a minimum cost set of edges so that the induced subgraph contains at least K edgedisjoint paths with at most L edges between each pair in K.

In theory, we could formulate the limit on the number of hops in a path in the space of design variables only. This approach was used by several authors (see Section 7) but has a major drawback: it leads to formulations with an exponential number of constraints, some of which are really hard to interpret and also difficult to handle numerically (the associated separation problem being NP-hard).

In this chapter, we prefer to use extended formulations, once again based on multi-commodity flow variables, that allow to model the limit on the path length more naturally. Moreover, these formulations imply all the valid inequalities known for formulations in the space of design variables. More precisely, the projection of the extended formulations presented here on the space of design variables strictly contains the polyhedron defined by formulations in the space of design variables presented in the literature so far.

The basic idea is to use a layered representation of graph G to implicitly force each path to use at most L edges. We model the subproblem associated with each commodity with a directed graph composed of L + 1 layers as illustrated in Figure 1.

Namely, from the original non-directed graph G = (N, E), we create a directed layered graph G q = (N q , A q ) for each commodity q ∈ K, where N q = N q 1 ∪ . . . ∪ with N q 1 = {o(q)}, N q L+1 = {d(q)} and N q l = N \{o(q)}, l = 2, . . ., L. Let v q l be the copy of v ∈ N in the l-th layer of graph G q . Then, the arc sets are defined by

A q = {(i q l , j q l+1 ) | {i, j} ∈ E, i q l ∈ N q l , j q l+1 ∈ N q l+1
, l ∈ {1, . . ., L}} ∪ {d(q) l , d(q) l+1 , l ∈ {2, . . ., L}}, see Figure 1. In the sequel, an (undirected) edge in E with endpoints i and j is denoted {i, j} while a (directed) arc between i q l ∈ N q l and j q l+1 ∈ N q l+1 is denoted by (i, j, l) (the commodity q is omitted in the notation as it is often clear from the context).

Note that each path between o(q) and d(q) in the layered graph G q is composed of exactly L arcs (hops), which correspond to a maximum of L edges (hops) in the original one. In fact this is the main idea of this transformation, since in the layered graph any path is feasible with respect to the hop-constraints. The usual multi-commodity flow equations defined in this layered graph yield the following model: Minimize e ∈E c e y e (30) Subject to

j ∈N + i x lq i j -j ∈N - i x l-1 q ji = w q i , ∀i ∈ N q , ∀ l ∈ {2, . . ., L + 1}, ∀ q ∈ K (31) L l=1 x lq i j + x lq ji ≤ y e , ∀ e = {i, j} ∈ E, ∀ q ∈ K, (32)
x lq i j ≥ 0, integer, ∀ (i, j, l) ∈ A q , ∀ q ∈ K, ( 33
)
y e ∈ {0, 1}, ∀ e ∈ E, (34) (35)
Flow balance constraints (31) define K paths between o(q) and d(q) in the layered graph G q with

w k i =        K, if i = o(q), -K, if i = d(q), 0, otherwise. (36)
Constraints ( 32) guarantee that paths are edge-disjoint and only use installed edges. This model can become very large when the number of commodities and the size of the network increase, but it can be solved efficiently using Benders decomposition. It is also interesting to mention that if there is only one commodity, and with nonnegative costs, the linear relaxation of this model is always integral when L ≤ 3.

Rings

As stated before, models from Section 4 lead to very sparse designs. In fact, it turns out that the optimal solution of the two-connected network problem is often a Hamiltonian cycle. Hence, any edge failure implies that the flow that was routed on that edge must be rerouted, using all the edges of the network, an obviously undesirable feature.

It is therefore necessary to add extra constraints to limit the region of influence of the traffic that it is necessary to reroute if a connection is broken. Hop constraints presented above are a possible way to achieve this. Another approach presented in this section is based on the technology of self-healing rings, quite popular in telecommunications networks. Self-healing rings are cycles in the network equipped in such a way that any link failure in the ring is automatically detected and the traffic rerouted by the alternative path in the cycle. It is natural to impose a limited length of these rings. This is equivalent to set a bound on the length of the shortest cycle including each edge.

This leads to the problem of designing a minimum cost network with the following constraints:

1. The constructed network contains at least two node-disjoint paths between every pair of nodes (2-connectivity constraints), and 2. each edge of the network belongs to at least one cycle whose length is bounded by a given constant K (ring constraints).

This problem is called the Two-Connected Network with Bounded rings (2CNBR) problem. The length of an edge can be unitary (i.e., similar to hop constraints), or can be weighted, to represent for example the physical delay for flowing through a given edge.

A useful tool to analyze feasible solutions of 2CNBR is the restriction of a graph to bounded rings. Given a graph G = (N, E) and a constant K > 0, we define for each subset of edges F ⊆ E its restriction to bounded rings F K as

F K = e ∈ F :
e belongs to at least one cycle of length less than or equal to K in F .

The subgraph G K = (N, E K ) is the restriction of G to bounded rings. Note that an edge e ∈ E\E K will never belong to a feasible solution of 2CNBR.

Further we denote by Y the set of incidence vectors of subsets F ⊆ E such that

1. F is two-connected, 2. F = F K .
Then, the 2CNBR problem consists in Checking that G K is two-connected, i.e., that Y is nonempty, can be done in polynomial time. We therefore assume in the remainder of this chapter that there always exists a feasible solution to the problem.

Since all costs c e , e ∈ E are assumed to be nonnegative, there always exists an optimal solution of 2CNBR whose induced graph is minimal with respect to inclusion. More precisely, if F K is two-connected, as F ⊇ F K , F is also twoconnected and the cost of F is greater than or equal to the cost of F K . We can thus relax the constraints and just require that F K is two-connected for a set of edges F to be feasible. Hence, 2CNBR can be equivalently formulated as In order to formulate the problem using only design variables y, observe that if a subset of edges F ⊆ E is such that (G -F ) K is not two-connected, then G -F does not contain a feasible solution. Therefore each feasible solution contains at least one edge from F .

As we are only interested in minimal feasible solutions, this is sufficient to formulate the 2CNBR problem as the following integer linear program:

Minimize e∈E c e y e (37) Subject to y(F ) ≥ 1, ∀ F ⊆ E, (G -F ) K is not two-connected, (38)
y e ∈ {0, 1}, ∀ e ∈ E. (39)
Constraints (38) are called subset constraints.

As feasible solutions of 2CNBR are two-connected graphs, valid inequalities for the design of 2-connected networks are also valid for 2CNBR. In particular, cut constraints (19) and node-partition inequalities ( 22) are very important in branchand-cut strategies to solve the problem. However, for general 2-connected networks, cut constraints are facet-defining under very mild conditions, while in many cases they do not define facets for 2CNBR. By studying conditions for these inequalities to define facets, it is possible to strengthen them.

Given a subset of nodes S ⊆ N , ∅ S N , the cut constraint imposes that there are at least two edges leaving S, i.e., y(δ(S)) ≥ 2.

To characterize which cut constraints define facets, it is useful to know, for any pair of edges e, f ∈ δ(S), if there exists a solution whose incidence vector lies in the face y(δ(S)) = 2, i.e., if there exists a feasible solution containing e and f but no other edge of δ(S)). This is the case if and only if

C e, f = E(S) ∪ E(N \S) ∪ {e, f } is feasible, i.e., if (C e, f ) K is two-connected.
A useful tool to represent and analyze the vectors belonging to the face defined by a cut constraint is the ring-cut graph: Given a graph G = (N, E), a constant K > 0, and a subset of nodes S ⊂ N , ∅ S N , the ring-cut graph RCG S,K = (δ(S), RCE S,K ) induced by S is the graph defined by associating one node to each edge in δ(S) and by the set of edges

RCE S,K = {e, f } ⊆ δ(S) : (C e, f ) K is two-connected .
With the help of the ring-cut graph, it is possible to characterize which cut constraints are facet-defining. Moreover, the ring-cut graph can be used to derive new valid inequalities for 2CNBR. If F ⊆ δ(F ) is an independent subset in the ring-cut graph RCG S,K , then

y(F ) + 2y(δ(S)\F ) ≥ 3 (40)
is a valid inequality for the 2CNBR problem. Inequalities (40) are called ring-cut inequalities, and are also very useful to strengthen formulations of 2CNBR.

7 Bibliographical Notes

Connected Networks

The greedy algorithm for the Minimum Spanning Tree problem is due to [START_REF] Kruskal | On the shortest spanning subtree of a graph and the traveling salesman problem[END_REF]. The tree polytope is a special case of the matroid polytope first described by [START_REF] Edmonds | Matroids and the greedy algorithm[END_REF]. For a review on polyhedral results for tree related problems, see [START_REF] Magnanti | Optimal trees[END_REF]. Another compact formulation for the minimum spanning tree problem (not described here) was proposed by [START_REF] Martin | Using separation algorithms to generate mixed integer model reformulations[END_REF]. Grötschel, Monma and Stoer studied in detail network design problems with connectivity constraints. A survey of their work can be found in Grötschel et al. (1995a) and [START_REF] Stoer | Design of Survivable Networks[END_REF]. A later survey by [START_REF] Kerivin | Design of survivable networks: A survey[END_REF] concentrates on polyhedral aspects for some special cases and presents a general branch-and-cut algorithm. They also consider problems with bounded rings and hop-constrained problems.

Survivable Networks

In their earliest work on the subject, [START_REF] Grötschel | Integer polyhedra arising from certain design problems with connectivity constraints[END_REF] introduced a general model mixing edge and node survivability requirements. They examined the dimension of the associated polytope and proved facet results for cut and node-cut inequalities.

They also described completely the polytope of the (1-)connected network problem, based on the work of [START_REF] Cornuéjols | The traveling salesman problem on a graph and some related integer polyhedra[END_REF], by the introduction of partition inequalities. The first separation algorithm for these inequalities was proposed by [START_REF] Cunningham | Optimal attack and reinforcement of a network[END_REF] and requires |E | min-cut computations. [START_REF] Barahona | Separating from the dominant of the spanning tree polytope[END_REF] reduced this computing time to |N | min-cut computations. F -partition inequalities were first proposed by [START_REF] Mahjoub | Two-edge connected spanning subgraphs and polyhedra[END_REF].

Low-connectivity constrained network design problems have been introduced by [START_REF] Monma | Methods for designing communications networks with certain two-connected survivability constraints[END_REF] and [START_REF] Stoer | Design of Survivable Networks[END_REF], who introduced most of the terminology and models presented in Section 4. For high-connectivity requirements, the reader is referred to Grötschel et al. (1995b) and [START_REF] Stoer | Design of Survivable Networks[END_REF].

Directed multi-commodity flow formulations were studied by [START_REF] Magnanti | Strong formulations for network design problems with connectivity requirements[END_REF], and they introduced improved directed flow models that are much stronger than the cut formulations for some variants of the problem (in particular when there are many nodes with unitary requirements).

The complexity of the minimum cost two-connected network problem was established by [START_REF] Eswaran | Augmentation problems[END_REF]. An in-depth survey of Steiner tree problems was made by [START_REF] Winter | Steiner problems in networks : a survey[END_REF]. The algorithm for solving the Steiner tree problem in polynomial time when either the number of nodes of type 0 or the number of nodes of type 1 is restricted is due to [START_REF] Lawler | Combinatorial Optimization : Networks and Matroids[END_REF]. At the time of writing, the most recent and efficient exact approaches for some variants of the Steiner tree problem are due to [START_REF] Fischetti | Thinning out steiner trees: a node-based model for uniform edge costs[END_REF].

Hop Constraints

Hop-constraints were considered by [START_REF] Balakrishnan | Using a hop-constrained model to generate alternative communication network design[END_REF] as a means of generating alternative base solutions for a network design problem. Later on, [START_REF] Gouveia | Using variable redefinition for computing lower bounds for minimum spanning and steiner trees with hop constraints[END_REF] presented a layered network flow reformulation whose linear programming bound proved to be quite tight. This reformulation has, then, been used in several network design problems with hop-constraints [START_REF] Pirkul | New formulations and solution procedures for the hop constrained network design problem[END_REF][START_REF] Gouveia | Network flow models for designing diameterconstrained minimum-spanning and Steiner trees[END_REF]Gouveia et al., 2003) and even some hop-constrained problems involving survivability considerations (more on this below). It is also interesting to point out that the apparently simple general network design problem with L = 2 already contains a complex structure [START_REF] Dahl | The 2-path network problem[END_REF] who also conduct a computational study of this variation of the problem.

The K-edge-disjoint L-hop-constrained network design problem was first studied by Huygens et al. (2007) who only consider L ≤ 4 and K = 2. The node-disjoint variant was studied by [START_REF] Gouveia | Telecommunications Planning: Innovations in Pricing, Network Design and Management[END_REF] and later by [START_REF] Gouveia | Hop-contrained node survivable network design: An application to MPLS over WDM[END_REF] who consider a more complicated version. A summary of these results is also presented in the survey by [START_REF] Kerivin | Design of survivable networks: A survey[END_REF]. [START_REF] Itaí | The complexity of finding maximum disjoint paths with length constraints[END_REF] and later [START_REF] Bley | On the complexity of vertex-disjoint length-restricted path problems[END_REF] study the complexity of this problem for the node-disjoint and the edge-disjoint cases. More recently, [START_REF] Bley | Approximability of 3-and 4-hop bounded disjoint paths problems[END_REF] also studied the approximability of the problem for L = 3 and L = 4. Some authors focused on the formulation of some variants of the problem in the space of design variables. For K = 1, [START_REF] Dahl | Notes on polyhedra associated with hop-constrained walk polytopes[END_REF] has provided such a formulation and shown that it describes the corresponding convex hull for L ≤ 3. Later on, Dahl et al. (2004) have shown that finding such a description for L ≥ 4 would be much more complicated. For K ≥ 2 the results are even worse. [START_REF] Huygens | Two edge-disjoint hop-constrained paths and polyhedra[END_REF] have extended Dahl's result for K = 2 and L ≤ 3. For L ≥ 4, the only interesting result for the moment is the one given by Huygens and Mahjoub (2007) for L = 4 and K = 2 where a valid formulation has been given. However, in terms of valid inequalities and with the exception of the well known L-path cut inequalities, nothing is known for larger values of L. This may also explain why the only cutting plane method for the more general problem with several sources and several destinations by Huygens et al. (2007) only considers L ≤ 3.

The extended formulation for the general case presented in Section 5 was introduced by [START_REF] Botton | Benders decomposition for the hopconstrained survivable network design problem[END_REF] who also proposed an efficient Benders decomposition method to solve it. They also applied this algorithm to a generalisation of the model with so-called reliable edges [START_REF] Botton | On the hop-constrained survivable network design problem with reliable edges[END_REF]. For the single commodity case, [START_REF] Botton | The 2 edge-disjoint 3-paths polyhedron[END_REF] proposed valid inequalities that completely describe the polyhedron of incidence vectors of feasible solutions for K = 2 and L = 3 (hence for arbitrary costs), extending results by [START_REF] Bendali | The edge-disjoint 3-hopconstrained paths polytope[END_REF] for non-negative costs.

A version of the problem where the hop constraint limit is different in the nominal graph and in case of failures was introduced by Gouveia and Leitner (2017) and an efficient branch-and-cut approach for this problem was proposed by [START_REF] Gouveia | Branch-and-cut methods for the network design problem with vulnerability constraints[END_REF].

Another application of extended formulations for hop constrained problems in the context of distribution networks was proposed by De [START_REF] Boeck | Extended formulation for hop constrained distribution network configuration problems[END_REF], where some preprocessing techniques to reduce the size of the resulting formulations are also discussed.

Recently, [START_REF] Gouveia | Layered graph approaches for combinatorial optimization problems[END_REF] published a survey of layered graph approaches for hop constrained problem.

Rings

The Two-Connected Network with Bounded Rings problem was first studied by [START_REF] Fortz | Solving the two-connected network with bounded meshes problem[END_REF]. More polyhedral results can be found in [START_REF] Fortz | Design of Survivable Networks with Bounded Rings[END_REF]; [START_REF] Fortz | Polyhedral results for two-connected networks with bounded rings[END_REF]. [START_REF] Fortz | Two-connected networks with rings of bounded cardinality[END_REF] studied the particular case of unit edge lengths. The edge-connectivity version of the problem was studied by [START_REF] Fortz | Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut[END_REF].

Other network design problems involve the creation of rings of bounded lengths. [START_REF] Goldschmidt | SONET/SDH ring assignment with capacity constraints[END_REF] study the problem of connecting subsets of customers to a concentrator through a self-healing ring connected to a backbone ring of concentrators. This problem, called the SONET Ring Assignment Problem (SRAP) has the drawback that many instances are infeasible. [START_REF] Carroll | A branch-and-cut algorithm for the ring spur assignment problem[END_REF] studied a generalization of the SRAP, called the Ring Spur Assignment Problem (RSAP). In this problem, the objective is to design a set of bounded disjoint local rings that are interconnected by a backbone ring, like in the SRAP. Since no SRAP solution exist in some real world instances, locations that have no possible physical route due to limitations of geography can be connected to local rings by spurs off the local rings.

Conclusions and Perspectives

Topological network design is a very important topic, and is often used as first step of network planning, considering a long-term horizon where demand is not known in advance. Decoupling the decisions on capacity and routing from the physical design is possible because technology in telecommunications make these two sets of decisions independent, as fiber optics cables have almost infinite capacity, but capacity restrictions arise from equipments that are subsequently added to the nodes.

However, when considering topological design, the simplest model that consists of building a connected network (and that can be solved in polynomial time), is not sufficient as survivability and quality of service aspects must be ensured: one must guarantee that redundancy exists in the network to cover different cases of failures, and that paths used for connecting demand nodes are not too long. Unfortunately, as soon as such constraints are added, all problems become NP-hard and more challenging. Therefore, there is also quite a lot of literature (not covered in this chapter) dealing with the development of heuristics for the problems presented here.

Concerning exact methods, problems with survivable requirements only (as those presented in Section 4) have been extensively studied from the polyhedral point of view. The problems are usually modeled in the "natural" space of design variables and several classes of facet-inducing valid inequalities have been proposed in the literature, leading to powerful branch-and-cut algorithms able to solve realistic size instances very efficiently.

As soon as constraints on the length of the paths are added, formulating the problems in the space of design variables only becomes much more challenging, and most approaches rely on extended formulations. But, despite the progress of modern solvers, these formulations quickly become intractable because of their large size, and decomposition methods like Lagrangian relaxation, Benders decomposition or branch-and-price are often used.

Interesting open problems involve a better understanding of Benders cuts arising from Benders decomposition methods for these problems in order to develop more efficient separation algorithms, as currently most approaches rely on solving linear programs for the separation. Given that large size instances remain intractable, there is also a large unexplored research direction in matheuristics, i.e., methods using structural knowledge from exact methods to derive effective heuristics and provide a certificate of quality for the solutions obtained. To the best of our knowledge, the state-of-the-art heuristics are meta-heuristics that do not use any knowledge gained from exact method development.

On a more managerial side, it would also be interesting to measure more precisely, on realistic instances, the loss in solution quality due to the separation of topological design and capacity allocation / routing decisions compared to an integrated strategy.

  ∀s ∈ N , the problem reduces to the minimum cost connected network problem studied in the previous section. • If r s = 1 for exactly two nodes of N and r s = 0 for all the other nodes, the problem becomes a shortest path problem. • If r s = k, k ≥ 2, for exactly two nodes of N and r s = 0 for all the other nodes, the problem becomes a k-shortest paths problem. • If r s ∈ {0, 1}, ∀s ∈ N , the problem reduces to the Steiner tree problem in networks.

Fig. 1

 1 Fig. 1 Original network (a) and its alternative (or associated) layered representation (b) when L = 4

Theorem 1 (Menger (1927)).

  and edge-disjoint [s, t]-paths are related to cuts and articulation sets by Menger's theorem:

	1. In a graph G = (N, E), there is no cut of size k -1 or less disconnecting two given
	nodes s and t, if and only if there exist at least k edge-disjoint [s, t]-paths in G.
	2. Let s and t be two nonadjacent nodes in G. Then there is no articulation set Z
	of size k -1 or less disconnecting s and t, if and only if there exist at least k
	node-disjoint [s, t]-paths in G.