Keywords: spoken word recognition, final overlap priming, position-independent phonemes, TISK model

 to propose a novel account of final overlap phonological priming in terms of activation of both position-independent phoneme representations and bi-phone representations.

Perhaps one of the most robust effects in the literature on phonological priming during spoken word recognition is the facilitation observed on the processing of auditory target words when they are preceded by auditory primes that share their final phonemes with targets (e.g., RAMP-LAMP; [START_REF] Dumay | Behavioral and electrophysiological study of phonological priming between bisyllabic spoken words[END_REF][START_REF] Monsell | Competitor priming in spoken word recognition[END_REF][START_REF] Norris | Bias effects in facilitatory phonological priming[END_REF][START_REF] Radeau | The effect of overlap position in phonological priming between spoken words[END_REF][START_REF] Radeau | Facilitatory and inhibitory phonological priming effects as a function of overlap position[END_REF][START_REF] Radeau | Phonological priming between monosyllabic spoken words[END_REF][START_REF] Slowiaczek | Phonlogical priming in auditory word recognition[END_REF][START_REF] Slowiaczek | Phonological representations in prelexical speech processing: Evidence from form-based priming[END_REF]. This facilitation effect has been found to depend heavily on whether the primes and targets rhyme, and so share all phonemes from vowel to word offset. For example, in a shadowing task, [START_REF] Radeau | Facilitatory and inhibitory phonological priming effects as a function of overlap position[END_REF] manipulated the amount of final overlap between primes and targets. She observed facilitation for rime overlap (e.g., FLAMME-TRAME) in comparison to an unrelated prime condition (e.g., CLOCHE-TRAME), but no increase in the effect when the overlap included the final consonant of the onset in addition to the rime (e.g., GRAMME-TRAME). When primes and targets shared only their last consonant (e.g., FLEMME-TRAME), no effect was found. Also, in a study using the shadowing task and controlling for the number of shared phonemes in the different priming condition, [START_REF] Slowiaczek | Phonological representations in prelexical speech processing: Evidence from form-based priming[END_REF] obtained a greater facilitation effect when primes and targets shared the rime (e.g., RANK-BANK) than when prime-target overlap did not include the rime (e.g., inflected words HONKED-BANKED). Interestingly, Slowiaczek et al. also showed that the final overlap facilitation effect was no longer observed when primes and targets shared the vowel but none of the following consonants (e.g., RAMP-BANK), thus suggesting that vowel overlap alone is not sufficient to obtain rime priming.

The rime priming effect has two key components that suggest that pre-lexical representations and not lexical representations are responsible for the effect. First, the size of rime priming effects does not vary as a function of the relative frequency of the primes and the targets. Effects of similar size were found for word targets of lower frequency than primes and for word targets of higher frequency than primes [START_REF] Radeau | Phonological priming between monosyllabic spoken words[END_REF]. Finally, rime priming effects are not influenced by the lexical status of primes and targets. Similar effects were found with word primes and pseudoword primes (e.g., [START_REF] Radeau | The effect of overlap position in phonological priming between spoken words[END_REF][START_REF] Slowiaczek | Phonological representations in prelexical speech processing: Evidence from form-based priming[END_REF]. Also, rime priming effects have been observed for word and pseudoword targets (e.g., [START_REF] Dumay | Behavioral and electrophysiological study of phonological priming between bisyllabic spoken words[END_REF]. These results suggest that facilitatory rime priming effects are driven by pre-lexical representations that are shared across primes and targets. Activation of these shared representations during prime processing then impacts on the subsequent processing of the target.

Regarding spoken word recognition models, the rime priming effect fits well with the dominant view of spoken word recognition according to which units smaller than words are extracted from the speech signal, before making contact with the mental lexicon (e.g., [START_REF] Gaskell | Integrating form and meaning: A distributed model of speech perception[END_REF][START_REF] Hannagan | Spoken word recognition without a TRACE[END_REF][START_REF] Marslen-Wilson | Processing interaction and lexical access during word recognition in continuous speech[END_REF][START_REF] Mcclelland | The TRACE model of speech perception[END_REF][START_REF] Mehler | The role of syllables in speech processing: Infant and adult data[END_REF][START_REF] Norris | SHORTLIST: a connectionist model of continuous speech recognition[END_REF]. The rime priming effect can thus provide important evidence with respect to the nature of the pre-lexical representations that mediate spoken word recognition. Indeed, rime priming effects point to either subsyllabic groupings (e.g., the rime /aʀt/ in the French word "carte /kaʀt/") or simple ordered phoneme combinations such as bi-phones (e.g., the biphones /ka/-/aʀ/-/ʀt/ in the French word "carte /kaʀt/") that would be extracted from the speech signal and used to access lexical representations. Although units such as individual phonemes and syllables have often been proposed as intermediary units (e.g., [START_REF] Marslen-Wilson | Processing interaction and lexical access during word recognition in continuous speech[END_REF][START_REF] Mcclelland | The TRACE model of speech perception[END_REF][START_REF] Mehler | The role of syllables in speech processing: Infant and adult data[END_REF][START_REF] Norris | SHORTLIST: a connectionist model of continuous speech recognition[END_REF], bi-phone representations have been envisaged only recently, and are assumed in a relatively recent model of spoken word recognition, the TISK model [START_REF] Hannagan | Spoken word recognition without a TRACE[END_REF].

TISK is an interactive-activation model similar to the TRACE model [START_REF] Mcclelland | The TRACE model of speech perception[END_REF]. Both models assume separate levels of representation for phonemes and words that are organized hierarchically, with the activation of word units determined by their degree of overlap with the activation of phoneme units. TISK shares the two key principles of the TRACE model, namely phoneme-to-word facilitation and word-to-word inhibition, but it replaces the position-dependent phoneme units in TRACE by both a set of positionindependent phoneme units and a set of bi-phone units that represent ordered sequences of contiguous and non-contiguous phonemes. The position-independent phonemes and the biphone units postulated in TISK make it the sole model capable of accounting for a relatively new phenomenon observed in the field of spoken word recognition, the transposed-phoneme effect. This effect refers to the observation that a speech input like [kat] not only provides support for the corresponding lexical representation cat but also for the lexical representation that contains the same phonemes in a different order tack (e.g., [START_REF] Dufour | Phoneme-order encoding during spoken word recognition: A priming investigation[END_REF][START_REF] Toscano | Reconsidering the role of temporal order in spoken word recognition[END_REF], as well as the observation that nonwords (/baksɛt/) created by transposing two phonemes of a real word (/baskɛt/) are more readily confused with the baseword than nonwords (/bapfɛt/) created by substituting two phonemes of the same base-word (e.g., [START_REF] Dufour | Do you want /ʃoloka/ on a /bistɔk/? On the scope of transposed-phoneme effects with non-adjacent phonemes[END_REF][START_REF] Dufour | When you hear /baksɛt/ do you think /baskɛt/? Evidence for transposed-phoneme effects with multi-syllabic words[END_REF].

With respect to the aims of the present study, it is important to note that the bi-phone units postulated in TISK can also account for rime priming effects. Many studies examining rime priming effects have used rimes with a VC phonological structure (e.g., [START_REF] Dumay | Behavioral and electrophysiological study of phonological priming between bisyllabic spoken words[END_REF][START_REF] Radeau | Facilitatory and inhibitory phonological priming effects as a function of overlap position[END_REF][START_REF] Radeau | The effect of overlap position in phonological priming between spoken words[END_REF][START_REF] Radeau | Phonological priming between monosyllabic spoken words[END_REF][START_REF] Slowiaczek | Phonological representations in prelexical speech processing: Evidence from form-based priming[END_REF].

Therefore, within the framework of TISK it could simply be the repeated activation of the same bi-phones, composed of a vowel and a consonant, that caused the rime priming effect. Rime priming has also been reported with a more complex phonological structure and with rimes composed of a vowel and a consonantal cluster such as in the French prime-target pair "tarte /taʀt/ -"carte /kaʀt/" (e.g., [START_REF] Norris | Bias effects in facilitatory phonological priming[END_REF][START_REF] Slowiaczek | Phonological representations in prelexical speech processing: Evidence from form-based priming[END_REF]. TISK can also easily account for the facilitatory priming effect observed with this type of rime. It would be due to the activation of the bi-phones /aʀ/ and /ʀt/ during the processing of the prime /taʀt/ that are then re-activated during the processing of the target /kaʀt/, thus facilitating its prelexical processing and in turn its recognition. Rimes with a VCC phonological structure are particularly relevant for the TISK model since they allow testing an important prediction of TISK that no other model of spoken word recognition makes. Due to the existence of position-independent phonemes, TISK also predicts some facilitation of processing when the target word /kaʀt/ is preceded by the word /batʀ/ that shares the same final phonemes with the target but with the two final consonants transposed. In this case, according to the TISK model, the same final position-independent phonemes /a/-/ʀ/-/t/ should be activated by both the primes and the targets, thus causing a pre-lexical facilitation priming effect. The present study was designed to test this important prediction.

Here, we examined whether a final overlap facilitation effect can be observed when primes and targets shared the vowel plus the final consonants in a different order, as predicted by the TISK model. To do so, CVCC monosyllabic target words were used and were preceded either by a pseudoword prime that share the final three phonemes with targets, but with the two consonants in a different order (e.g., vodre /vɔdʀ/ -corde /kɔʀd/ "rope"), or by a pseudoword "rime" prime that shared the final three phonemes in exactly the same positions as in the targets (e.g., vorde /vɔʀd/ -corde /kɔʀd/ "rope"). The magnitude of the priming effect in these two conditions was evaluated relative to a control condition where primes and targets were unrelated (e.g., pulte /pylt/ -corde /kɔʀd/). The predictions were as follows. If, as postulated by the TISK model, position-independent phonemes mediate lexical processing, then we expected to find a facilitation effect when the primes and the targets share the final phonemes from the vowel but with the two final consonants transposed. We also expected to find a greater priming effect when the primes and the targets shared the final phonemes in the same positions, because in this case, and within the framework of TISK, the primes and the targets have not only the final (position-independent) phonemes in common but also the final bi-phones.

Method

Participants: A total of 150 participants were recruited on-line for the experiment. All participants reported to be native speakers of French and their reported age was between 18 and 60 years. Prior to the beginning of the experiment, participants provided informed consent and they were informed that the data would be collected anonymously. The sample size was determined on the basis of standard spoken word recognition experiments that traditionally involve between 12 and 20 participants per experimental list. Since this was an on-line experiment that facilitates both the recruitment of participants and running the experiment, we decided to increase the number of participants to 50 participants per experimental list. This allowed us to have a more highly-powered experiment and also to ensure that enough participants remained for analysis after rejecting those with excessive error rates and/or RTs. Materials: Thirty-six monosyllabic target words with a CVCC syllabic structure were selected from Vocolex, a lexical database for French [START_REF] Dufour | VoCoLex: A lexical database on phonological similarity between French words[END_REF]. For each target word, three pseudoword primes were created. The first shared the three final phonemes in the same position with the target (e.g., vorde /vɔʀd/ -corde /kɔʀd/ "rope"). The second also shared the three final phonemes but with the two final consonants transposed (e.g., vodre /vɔdʀ/ -corde /kɔʀd/). Finally, the third prime, used as control, was unrelated and shared no phonemes with the target (e.g., pulte /pylt/ -corde /kɔʀd/). All the control primes had a CVCC syllabic structure. The mean frequency of the target words was 39 occurrences per million.

The prime and target words are given in the Appendix. For interested readers we also provide in the Appendix the sonority profile and the phonemic category of the last two consonants of the transposed-phoneme and rime primes.

Three experimental lists were created so that each of the 36 target words was preceded by the three types of prime (rime, transposed-phoneme, control), and participants were presented with each target word only once. For the purpose of the lexical decision task, 36 CVCC pseudowords serving as targets were created by changing either the final or the initial phoneme of words not used in the experiment (e.g., the word serpe /sɛʀp/ "billhook"" became /fɛʀp/). So that the pseudowords followed the same criteria as the words, 12 were paired with a pseudoword prime sharing the final phonemes in the same position (e.g., /bɛʀp/-/fɛʀp/), 12 others were paired with a pseudoword prime sharing the final phonemes but with the two final consonants transposed (e.g., /bɛpʀ/-/fɛʀp/), and the remaining 12 were paired with a pseudoword prime sharing no phonemes (e.g., /pakl/-/fɛʀp/). To achieve a low proportion of related trials (i.e., 20%), 168 unrelated prime-target pairs having no phoneme in common and serving as filler trials were added to each list. Again, for the purpose of the lexical decision task, half of the filler targets were words and the other half were pseudowords. All the filler targets were paired with a pseudoword prime. All of the stimuli were recorded by a female native speaker of French, in a sound attenuated room, and digitized at a sampling rate of 44 kHz with 16-bit analog to digital recording. The mean duration of the targets words was 583 ms. The mean durations of the pseudoword primes were 580 ms, 589 ms and 587 respectively in the rime, transposed-phoneme, and control conditions. Procedure: The experiment was programmed using LabVanced software [START_REF] Finger | LabVanced: A Unified JavaScript Framework for Online Studies[END_REF].

Participants were instructed to put on their headphones and adjust the volume to a comfortable sound level. The primes and the targets were presented auditorily, and an interval (ISI) of 20 ms separated the offset of the primes and the onset of the targets. Participants were asked to make a lexical decision as quickly and accurately as possible by pressing the right arrow of their keyboard for the word response and the left arrow for the nonword response.

Reaction Time (RT) recording was triggered by the presentation of the target and was stopped by participants' response. The prime-target pairs were presented randomly, and an inter-trial interval of 2000 ms elapsed between the participant's response and the presentation of the next pair. Participants were tested on only one experimental list and began the experiment with 12 practice trials.

Results and Discussion

Fifteen participants were excluded from the analyses. Among them eight participants had an error rate above 40%, and the seven others had RTs greater than 1,500 ms on average. Two targets that gave rise to an error rate of more than 40% were also removed 1 . The mean RT and percentage of correct responses to target words in each condition are presented in Table 1.

<Insert Table 1 about here> 1 The 135 participants included in the analyses had an error rate comprised between 0 and 18%, and the 34 target words included in the analyses had an error rate comprised between 1 and 10%. The high error rate on the two target words removed from the analyses was likely due to the recordings of these stimuli that were somewhat noisy, and so not totally intelligible.

In order to compare the rime and the transposed-phoneme priming conditions, the model was releveled with the rime prime condition becoming the reference. The model revealed a significant difference with RTs on target words being 72 ms shorter when preceded by rime primes in comparison to transposed-phoneme primes (β = 0.0875, SE = 0.0065, t = 13.42; p < .001).

The percentage of correct responses was analyzed using a mixed-effects logit model [START_REF] Jaeger | Categorical data analysis: away from ANOVAs (transformation or not) and towards logit mixed models[END_REF] following the same procedure as for RTs. This analysis revealed no significant effects.

Discussion

A large body of research on spoken word recognition using the priming paradigm has reported facilitation of processing when target words are preceded by primes that share the rime with targets [START_REF] Dumay | Behavioral and electrophysiological study of phonological priming between bisyllabic spoken words[END_REF][START_REF] Monsell | Competitor priming in spoken word recognition[END_REF][START_REF] Norris | Bias effects in facilitatory phonological priming[END_REF][START_REF] Radeau | The effect of overlap position in phonological priming between spoken words[END_REF][START_REF] Radeau | Facilitatory and inhibitory phonological priming effects as a function of overlap position[END_REF][START_REF] Radeau | Phonological priming between monosyllabic spoken words[END_REF][START_REF] Slowiaczek | Phonological representations in prelexical speech processing: Evidence from form-based priming[END_REF]. This facilitatory rime priming effect has been taken as evidence that units smaller than the word, and in particular the rime, play a role during spoken word recognition. Here, we re-interpret the rime priming effect within the framework of the TISK model that assumes that not only phonemes but also sequences of two phonemes (i.e., bi-phones) are extracted from the speech signal before making contact with phonological representations of words in long-term memory. Within such a framework the rime priming effect would be due to the repeated activation of the same bi-phones during prime and target processing. Perhaps more importantly, TISK also assumes that the phonemes are coded independently of their position in the speech signal, and thus an important prediction made by TISK is that priming effects should also occur when the phonemes that compose a rime are transposed. In accordance with this prediction, we reported a facilitation of processing when CVCC primes and targets shared their final three phonemes but with the two final consonants transposed. This transposed-rime priming effect argues in favor of the existence of position-independent phonemes. Position-independent phonemes that are activated during prime processing result in a facilitation of target processing when the targets share these position-independent phonemes.

We also observed that CVCC primes that shared the final three phonemes in the same positions as the CVCC targets, and thus the rime, generated a significantly stronger priming effect than CVCC primes that shared the three last phonemes with target words but with the two consonants in different positions. We believe that this stronger priming effect is due to the fact that when primes and targets share the "intact" rime the prime-target overlap not only involved position-independent phonemes but also the bi-phone representations as postulated in TISK. On the other hand, in the "transposed-phoneme rime" condition, the only overlap between primes and targets was at the level of position-independent phonemes. Together our results place important constrains regarding the nature of the pre-lexical code that is computed during spoken word recognition, and suggest that position-independent phoneme units as well as the combination of these phonemes (i.e., bi-phones) are extracted from the speech signal and play a key role during spoken word recognition.

At a more theoretical level, the present study provides a further demonstration in favor of a flexible coding of phoneme order in spoken word recognition. This flexibility has also been reported in the encoding of letter order in numerous studies conducted with visual words (e.g., [START_REF] Perea | Does jugde activate COURT? Transposed-letter similarity effects in masked associative priming[END_REF]2004;see Grainger, 2008, for a review) as well as in the tactile modality [START_REF] Baciero | Raeding with the fingres: Towards a universal model of letter position coding[END_REF], which like the auditory modality is inherently serial. In the modeling of word recognition, this flexibility could be achieved either by assuming uncertainty (or noise) associated with the position of phonemes/letters within words (e.g., [START_REF] Gomez | The overlap model: A model of letter position coding[END_REF] or by assuming an intermediate level of representations between the phoneme/letter and word levels composed of open bi-phons/grams (i.e. ordered sequences of contiguous and non-contiguous phonemes/letters; e.g., [START_REF] Grainger | Modeling letter position coding in printed word perception[END_REF][START_REF] Hannagan | Spoken word recognition without a TRACE[END_REF][START_REF] Whitney | How the brain encodes the order of letters in a printed word: The SERIOL model and selective literature review[END_REF]. It should also be noted that one recent study [START_REF] Harrison | Is segmental interference positiondependent[END_REF] of written language production (written and typed word production) also argues in favor of some flexibility in the representation of segment order. Hence, the flexible orderencoding of linguistic units (e.g., phonemes and letters for spoken and written word comprehension and production) would appear to be modality-independent and could thus constitute a general mechanism in language processing, which could also be applicable to a wide range of cognitive processes requiring the processing of order information (see [START_REF] Logan | Serial order in perception, memory, and action[END_REF][START_REF] Ordonez Magro | Sequential versus simultaneous presentation of memoranda in verbal working memory: (How) does it matter?[END_REF].

Although the rime has often been proposed as playing a preponderant role in the final overlap priming effect, the syllable has also been proposed. For example, [START_REF] Dumay | Behavioral and electrophysiological study of phonological priming between bisyllabic spoken words[END_REF] found priming effects when primes and targets shared the complete second syllable (LURAGE -TIRAGE) and also when they shared only the rime (LUBAGE -TIRAGE), but the facilitation was stronger in the former than in the latter condition. These findings have been interpreted as suggesting that both rime and syllable representations, are involved in the final overlap facilitation effect. We proposed that this greater priming effect for syllable overlap than for rime overlap can be accounted for without the need to postulate syllable and rime units. Within the TISK framework the greater priming effect seen with complete syllable overlap would be simply be due to the fact that in this condition the primes and the targets share more bi-phones than in the rime overlap condition. It remains to be explained, however, why [START_REF] Radeau | Facilitatory and inhibitory phonological priming effects as a function of overlap position[END_REF] reported no increase in priming effects when the overlap included the consonant of the onset in addition to the rime (e.g., GRAMME-TRAME), since in such a case the primes and the targets have more bi-phones in common than when the prime and the target share only the rime (e.g., FLAMME-TRAME). A possible explanation is that the final overlap facilitation effect in the onset + rime condition of [START_REF] Radeau | Facilitatory and inhibitory phonological priming effects as a function of overlap position[END_REF] was weakened by a competition process between the primes and the targets at a lexical level of processing. This reasoning is based on studies showing that the strongest competitors of a target word are those that match the target on the first phonemes (e.g., [START_REF] Allopenna | Tracking the time course of spoken word recognition using eye movements: Evidence for continuous mapping models[END_REF][START_REF] Dufour | Lexical Competition in phonological priming: Assessing the role of phonological match and mismatch lengths between primes and targets[END_REF][START_REF] Slowiaczek | Prelexical facilitation and lexical interference in auditory word recognition[END_REF][START_REF] Slowiaczek | Prelexical facilitation and lexical interference in auditory word recognition[END_REF] and on studies showing activation of words that mismatch on initial phonemes, at least when the mismatching phonemes have a high degree of overlap in terms of phonetic features, as in the GRAMME-TRAME pair of the study of Radeau (e.g., Allopenna et al., 1998;[START_REF] Connine | Do the beginning of words have a special status in auditory word recognition[END_REF][START_REF] Marslen-Wilson | Perceptual distance and competition in lexical access[END_REF].

To sum up, we reported facilitation of processing when primes and targets shared the final phonemes from the vowel to word offset, and thus we replicated the so-called rime priming effect. Crucially, we also reported facilitation of processing when the two consonants of the "rime" are transposed. Rather than explaining the final overlap facilitation effect as reflecting the activation of syllabic representations and/or subsyllabic representations (i.e., the rime), we proposed, in accordance with the TISK model [START_REF] Hannagan | Spoken word recognition without a TRACE[END_REF], a new account of the effect, in terms of activation of both position-independent phoneme representations and bi-phone representations. More generally speaking, the results of our study provide further evidence for the role played by phoneme representations in spoken word words removed from the analyses; P= plosive; F = fricative; L = liquid; + = voiced; -= unvoiced; > = superior in terms of sonority; < = inferior in terms of sonority.

Table 1 :

 1 Mean Reaction Times (in ms) and percentages of correct responses in each priming condition. Pseudoword primes and target words used in the Experiment, and sonority profile with the phonemic category of the last two consonants of the transposed-phoneme and rime primes.

		Control	Transposed	Rime
	Reaction Time	981	961	889
	Correct Responses	96	96	97

RTs on target words (available at https://osf.io/qtrp2/; Open Science Framework; [START_REF] Foster | Open Science Framework (OSF)[END_REF] were analyzed using linear mixed effects models with participants and target words as crossed random factors, using R software (R Development Core Team, 2016) and the lme4 package [START_REF] Baayen | Mixed-effects modeling with crossed random effects for subjects and items[END_REF][START_REF] Bates | lme4: Linear mixed-effects models using S4 classes, R package version 2.6[END_REF]. The RT analysis was performed on correct responses, thus removing 181 (3.94%) data points out of 4590. RTs longer than 2,000 ms (2.74%) were considered as outliers, and were excluded from the analysis. For the model to meet the assumptions of normally-distributed residuals and homogeneity of variance, a log transformation was applied to the RTs [START_REF] Baayen | Analyzing reaction times[END_REF] prior to running the model. The model was run on 4288 data points. We tested a model with the variable prime type (rime, transposed-phoneme, control) entered as fixed effect. The model failed to converge when random participant and item slopes were included (see [START_REF] Barr | Random effects structure for confirmatory hypothesis testing: Keep it maximal[END_REF]. Therefore the final model only included random intercepts for participants and items.

In order to examine both the rime and the transposed-phoneme priming effect, we first reported the results of the model when the reference was the performance on the control primes. The model revealed a significant rime priming effect, with RTs on target words being 92 ms shorter when preceded by rime primes in comparison to control primes (β = -0.1040, SE = 0.0065, t = -15.98; p < .001). Crucially, the model also revealed a significant transposedphoneme priming effect with RTs on target words being 20 ms shorter when preceded by transposed-phoneme primes in comparison to control primes (β = -0.0165, SE = 0.0065, t = -2.54; p = .011). recognition, and suggest that phonemes and combinations of phonemes might suffice for accounting for various kinds of phonological priming effects.


Marin Bougeret
email: marin.bougeret@lirmm.fr

Jérémy Omer
email: jeremy.omer@insa-rennes.fr

Michael Poss
email: michael.poss@lirmm.fr

Optimization problems in graphs with locational uncertainty

Keywords: combinatorial optimization, robust optimization, N P-hardness, cutting plane algorithms, dynamic programming 1

Many discrete optimization problems amount to selecting a feasible set of edges of least weight. We consider in this paper the context of spatial graphs where the positions of the vertices are uncertain and belong to known uncertainty sets. The objective is to minimize the sum of the distances of the chosen set of edges for the worst positions of the vertices in their uncertainty sets. We rst prove that these problems are N P-hard even when the feasible sets consist either of all spanning trees or of all s -t paths. Given this hardness, we propose an exact solution algorithm combining integer programming formulations with a cutting plane algorithm, identifying the cases where the separation problem can be solved eciently. We also propose a conservative approximation and show its equivalence to the ane decision rule approximation in the context of Euclidean distances. We compare our algorithms to three deterministic reformulations on instances inspired by the scientic literature for the Steiner tree problem and a facility location problem.

Introduction

Research in combinatorial optimization has provided ecient algorithms to solve many complex discrete decision problems, providing exact or near-optimal solutions in reasonable amounts of time. The applications are countless, ranging from logistics (network design, facility location, . . .) to scheduling. In this paper, we are interested in the class S of deterministic combinatorial optimization problems that amount to selecting a feasible set of edges in a given graph G = (V, E) and that minimizes the sum of edge-weights. Any Π ∈ S represents a specic problem, such as the shortest path or the minimum spanning tree problem.

We consider further that G is a spatial graph embedded into a given metric space (M, d).

Each vertex i is assigned a position u i ∈ M so the weight of each edge {i, j} is given by its distance d(u i , u j ). Denoting by X ⊆ {0, 1} |E| the set of feasible vectors for a given instance, any Π ∈ S corresponds to a combinatorial optimization problem of the form

min x∈X {i,j}∈E x ij d(u i , u j ). (Π)
Problem Π encompasses many applications, such as network design and facility location.

These are typically subject to data uncertainty, be it because of the duration of the decision process, measurement errors, or simply lack of information. One successful framework that has emerged to address uncertainty is robust optimization (Ben-Tal and Nemirovski 1998),

where the uncertain parameters are modeled with convex sets such as polytopes, or with nite sets of points. Many authors have focused more particularly on robust discrete optimization problems see Bertsimas and Sim (2003), Buchheim and Kurtz (2018), Kasperski and Zieli«ski (2016), Kouvelis and Yu (2013) and the references therein. We enter this framework by considering the model where the positions of the vertices are subject to uncertainty, therefore impacting the distances among the vertices. The resulting problem thus seeks to nd a feasible set of edges that minimizes its worst-case sum of distances. Formally, we introduce for each vertex i ∈ V the set of possible locations as the uncertainty set U i ⊆ M of cardinality

σ i = |U i |.
We consider that there is no correlation between the positions of the dierent vertices, so a scenario is given by the tuple u = (u 1 , . . . , u |V| ) which belongs to the set U = × i∈V U i . Then, given Π ∈ S, we study in this paper the locational robust counterpart of problem Π, formally dened as

min x∈X max u∈U {i,j}∈E x ij d(u i , u j ). (LocRob-Π)
We also devote a particular attention to evaluating the objective function of LocRob-Π, often called the adversarial problem max u∈U {i,j}∈E

x ij d(u i , u j ). (adversarial)
We underline that we focus throughout on nite uncertainty sets. However, our setting encompasses polyhedral uncertainty sets whenever the distance function is convex.

Remark 1. Suppose that M ⊆ R p for some p > 0 and that d is a convex function. Then, maximizing over U is equivalent to maximizing over the polytope conv(U) = × i∈V conv(U i ).

Hence, in that case our setting covers polyhedral uncertainty sets.

As an illustration, the following two applications fall into the context of problem LocRob-Π.

Example 1 (Subway network design). Designing and expanding a subway network forms an important optimization problem faced by large cities. The new lines should eciently cover dense city areas while interacting well with the existing transportation lines. A key aspect of this problem amounts to locating the new subway stations. In addition to the technical considerations inherent to any construction, these also involve political considerations as local ocials are never happy to let their citizens face the inconvenience of heavy civil engineering. This political lever is particularly complex in cities like Brussels having multiple local governments that must all agree before the stations can nally be constructed. As the overall process takes years, facing local government changes, the exact locations of the metro stations typically evolve between the rst draft and the nal implementation. Now, the exact locations of the stations impact the lengths of the resulting lines, the construction cost of which is typically proportional to their lengths (Gutiérrez-Jarpa et al. 2013). The cost of digging the new lines can therefore be modeled as a network design problem with locational uncertainty on the position of the vertices, usually including additional technical and environmental constraints.

Example 2 (Strategic facility location). A production company wishes to expand its activities in a new region, locating additional facilities. We consider the strategic level where the company may only choose approximate locations, as the exact locations will be known later, after all technical and legal considerations have been studied. We consider a one-stage location problem where the selection of facilities and assignment of customers are decided at the same time. This is relevant, for instance, when clients may need dierent types of products that require dierent installations at the facilities. As always in such facility location problems, the distances between the future clients and facilities lead to signicant transportation costs that need to be kept as low as possible. In this particular case, these distances depend on locations that are uncertain at the time planning decisions are made. Importantly, the distances are provided by the underlying road network (Melkote and Daskin 2001), which yields a graphinduced metric (M, d). More generally, this framework is also relevant for any application of the p-median problem (Marín and Pelegrín 2019) with locational uncertainty.

Traditionally, robust optimization problems with an objective function that is concave in the uncertain parameters are reformulated as compact models using conic duality (Ben-Tal and Nemirovski 1998). These techniques do not readily extend to function d(u i , u j ) as the latter is non-concave in general. Actually, for Euclidean metric spaces based on the vector space R , ∈ Z + , d(u i , u j ) = u i -u j 2 is convex in u i and u j .

= max u i ∈U i ,u j ∈U j d(u i , u j ), for each (i, j) ∈ V 2 , i = j.
To summarize, we see that while Zhen et al. ( 2021) provide valuable tools for addressing problems dened in Euclidean metric spaces considering uncertainty polytopes, their approaches cannot be used for graph-induced metric spaces, such as those mentioned in Example 2. On the other hand, Citovsky et al. ( 2017) focused on the case where X contains all

Hamiltonian cycles of G. The main purpose of the present paper is thus to provide a more general solution algorithm that is valid for any set X and metric space (M, d). We only assume that U is nite, encompassing the two cases mentioned above. Specically, polyhedral uncertainty in Euclidean metric spaces is already discussed in Remark 1. Then, in the case of graph-induced metrics, the set M is the set of nodes of a nite graph, meaning that each U i ⊆ M must be nite as well.

Let us denote by G(x) = (V (x), E(x)) the subgraph induced by x, where

E(x) = {{i, j} ∈ E | x ij = 1} and V (x) = {i ∈ V | ∃e ∈ E(x) : i ∈ e }.
In this context, we can summarize our contributions as follows:

We prove that LocRob-Π is N P-hard even when X consists of all s -t paths and

(M, d) is the one-dimensional Euclidean metric space or when X consists of all spanning trees of G. These results illustrate how the nature of LocRob-Π fundamentally diers from the classical min-max robust problem with cost uncertainty, which is known to be polynomially solvable whenever the costs lie in independent uncertainty sets (Aissi et al. 2009).

We provide a general cutting-plane algorithm for LocRob-Π. We further show that problem adversarial is N P-hard and provide two algorithms for computing adversarial.

One is based on integer programming formulations while the other one relies on a dynamic programming algorithm that involves the threewidth of G(x).

We leverage the above dynamic programming to provide a compact formulation for the problem when any G(x) contains only stars (or unions of stars). We can, in theory, extend that idea to trees, albeit presenting poor numerical performance.

We propose a conservative approximation of the problem that uncouples U into its projections U i , i ∈ V. In the case of Euclidean metric spaces, this approximation leads to mixed-integer second-order conic reformulations, and turns out to be equivalent to the ane decision rule reformulation proposed by Zhen et al. (2021).

We compare the exact cutting plane algorithm numerically with the above conservative approximation and simple deterministic reformulations. The benchmark is composed of two families of instances. The rst family includes Steiner tree instances that illustrate subway network design. The second one is composed of strategic facility location instances.

The rest of the paper is structured as follows. Section 2 studies the hardness of adversarial and LocRob-Π. In Section 3, we develop the exact solution algorithm. The latter involves a dynamic programming algorithm for trees, generalized to graphs of bounded threewidth in the online supplement. Section 4 details the conservative reformulation. In Section 5, we present our numerical experiments. The online supplement details the extension of the dynamic programming to graphs with bounded threewidth (Sections EC.1 and EC.2), the details of the compact formulations (Section EC.3) for trees, and the equivalence between our conservative reformulation and that of Zhen et al. (2021) (Section EC.4).

Hardness results

We study in this section the complexity of the optimization problems LocRob-Π and adversarial.

Problem robust-Π

Let us start by observing that LocRob-Π is not harder than its nominal counterpart Π whenever the edges indexed by each x ∈ X are disjoint (do not have common endpoints).

In that case, we have

max u∈U {i,j}∈E x ij d(u i , u j ) = {i,j}∈E max u i ∈U i ,u j ∈U j x ij d(u i , u j ) = {i,j}∈E x ij d max ij .
Hence, solving LocRob-Π in the above setting amounts to solve

min x∈X {i,j}∈E
x ij d max ij .

As an example, consider that Π is the assignment problem so G is a bi-partite graph based on the partition of V into the two sets V 1 and V 2 of equal size, and any x ∈ X selects |V 1 | edges that cover all nodes. Problem Π being solvable in polynomial time, so is LocRob-Π.

In spite of this easy example, we show in this section that LocRob-Π can in general not be reduced to Π as LocRob-Π is typically harder than Π. We illustrate the hardness of

x ij c ij , (1)
where C is a given uncertainty set included in the positive orthant. Comparing 1 with LocRob-Π underlines that the diculty of LocRob-Π lies in the non-linearity of the distance function d. It is folklore (e.g., Aissi et al. (2009)) that when C is the Cartesian product of intervals,

C = × e∈E [c e , c e ]
for c e ≤ c e , problem 1 can be reformulated as min x∈X {i,j}∈E x ij c ij making the robust problems as easy as their nominal counterparts. Our rst result below shows that such is not the case for LocRob-Π, as sp turns N P-hard even in the simple case where each U i is a subset of R. Notice that in the 1-dimensional Euclidean space, the convexity of

d(u i , u j ) = |u i -u j | implies that U i is equivalent to the set {u i , u i }, for some u i ≤ u i , in line
with Remark 1.

Proposition 1. LocRob-SP is N P-hard even when (M, d) is the 1-dimensional Euclidean space.

Proof. Given a set of integers {a 1 , . . . , a n }, with A = n i=1 a i , the N P-complete decision problem partition asks for a subset S ⊂ {1, . . . , n} such that i∈S a i = A/2. Let K > 0 be a large enough integer. The reduction considers the graph G with 2n + 2 vertices and 4n edges as illustrated Figure 1; the regions U i are translated away from vertex o for visibility. Specically, our reduction locates vertices s and t at 0 while U i = {-u - i , u + i } for each vertex i dierent from s and t. The denition of u + and u -alternates along the vertices v i , v i+1 , v i+2 , . . . and similarly for vertices w i : for each i = 2k + 1, we dene u We rst show that for K large enough, the worst-case u ∈ U for any path P from s to t alternates from the top of an interval to the bottom of the subsequent interval along the path. To prove this, notice that for any vertex v ∈ V \ {s, t}, u - v ∈ [K -A, K + A] and u + v ∈ [K -A, K + A] and the same holds for any vertex w. Hence, if u alternates for the entire path, the resulting cost is not smaller than c = 2n(K -A). On the contrary, if u misses one alternation, its cost cannot be greater than c = 2(n -1)(K + A) + 2A. Hence, taking K > 2nA ensures c > c .

+ v i = K + a i , u - v i = K + A n -a i , u + w i = K and u - w i = K + A n , while for each i = 2k, we dene u + v i = K + A n -a i , u - v i = K + a i , u + w i = K + A n and u - w i = K. s t v 1 -u - v 1 u + v 1 w 1 -u - w 1 u + w 1 v 2 -u - v 2 u + v 2 w 2 -u - w 2 u + w 2 v n -u - vn u + vn w n -u -
The reduction works as follow. Let S ⊆ {1, . . . , n} be a subset of integers and S its complement. We associate to S the path P S from s to t that contains v i for each i ∈ S and w i for each i ∈ S. From the above, only two scenarios in U must be considered in the worst-case and each vertex i ∈ {w 1 , v 1 , . . . , w n , v n } contributes to the total length with either

v 0 w 0 v 1 w 1 v n w n (a) G v 1 0 w 1 0 v 1 1 w 1 1 v 1 n w 1 n v 2 0 w 2 0 v 2 1 w 2 1 v 2 n w 2 n (b) G M .
Figure 2: Graphs used in the reduction for the minimum spanning tree problem.

2u + i or 2u - i , depending on the scenario considered. We have

c(P S ) = max u∈U {i,j}∈P S u i -u j 2 = 2 max nK + i∈S a i , n(K + A n ) - i∈S a i = 2 max nK + i∈S a i , A + nK - i∈S a i = 2nK + 2 max   i∈S a i , i∈S a i   .
Hence, there exists a path P S in X with minimum cost of 2nK + A if and only if there exists a set S such that i∈S a i = i∈S a i = A/2.

For mst we can prove the hardness of the problem only for a more general metric space.

Proposition 2. LocRob-MST is N P-hard.

Proof. We consider the same partition problem as in the proof of Proposition 1. Now G contains the 2n + 2 vertices and 3n + 1 edges depicted on Figure 2a. We consider the metric space (M, d) induced by the weighted graph G M = (V M , E M , ω) depicted on Figure 2b. Let K > 0 be a number large enough. The dashed edges and thin edges have their weights equal to K and 2K, respectively, while

ω v 1 i-1 v 1 i = 3K + a i , ω v 2 i-1 v 2 i = 3K + A n -a i , ω w 1 i-1 w 1 i = 3K, and ω w 2 i-1 w 2 i = 3K + A
n for each i = 1, . . . , n. The weight vector ω satises the triangle inequalities, so the metric d induced on V M by the shortest paths in

G M satises d ij = ω ij for each {i, j} ∈ E M . Finally, we dene U v i = {v 1 i , v 2 i } and U w i = {w 1 i , w 2 i } for i = 0, . . . , n.
We rst observe that the cost of a vertical edge {v i , w i } is equal to K for all positions of (v i , w i ) ∈ U v i × U w i . Let us consider any tree T in G that contains n v vertical edges and n h horizontal edges, where n ≤ n h ≤ 2n. For K large enough, we claim that the worst-case u ∈ U locates all vertices either in the bottom layer of G M that consists of vertices v 1 i and w 1

i for i = 0, . . . , n, or in the top layer that consists of the remaining vertices. To prove the claim, notice that the weight of any horizontal edge in G M is comprised between 3K -A and 3K +A, while the weight of any diagonal edge is 2K. Hence, if u locates all its vertices either in the bottom or in the top layer, the resulting cost is not smaller than c = n h (3K -A)+n v K.

On the contrary, if u alternates at least once between the layers, its cost cannot be greater

than c = (n h -1)(3K + A) + 2K + n v K. Hence, taking K > (4n -1)A ≥ (2n h -1)A ensures c > c , proving the claim.
We prove next that for K large enough, any optimal tree T in G must contain n+1 vertical edges and n horizontal ones. Following the above claim, the cost of a horizontal edge {v i , v i+1 } or {w i , w i+1 } for a worst-case u ∈ U is comprised between 3K -A and 3K + A. Hence, any tree T with n h ∈ {n + 1, . . . , 2n} horizontal edges costs at least c = n h (3K -A) + n v K while any tree having n h -1 horizontal edges costs at most c = (n h -1)(3K + A) + (n v + 1)K.

Hence, taking K > 2nA ≥ n h A ensures c > c , proving n h = n in any optimal solution.
As in the proof of Proposition 1, we let S ⊆ {1, . . . , n} be a subset of integers and S its complement. We associate to S the tree T S that contains {v i-1 , v i } for each i ∈ S and {w i-1 , w i } for each i ∈ S. Following the claim above, only two scenarios in U must be considered, and following again the reasoning used in the proof of Proposition 1, we have

c(T S ) = max 3nK + i∈S a i , 3nK + A - i∈S a i = 3nK + max   i∈S a i , i∈S a i   .
Hence, there exists a spanning tree T S in X with minimum cost of 3nK + A/2 if and only if there exists a set S such that i∈S a i = i∈S a i = A/2.

We detail in the remark below how, for any positive integer , the metric space (M, d) used in the proof of Proposition 2 cannot be embedded isometrically into R . As a consequence, the hardness of LocRob-MST in Euclidean spaces remains an open problem.

Remark 2. The graph G M described in the above proof cannot be embedded isometrically into an Euclidean space, as can be seen by considering the triangle w 1 0 w 1 1 w 2 0 and the fourth point v 2 0 . The sides of the triangle have length d(w

1 0 , w 1 1 ) = 3K, d(w 1 1 , w 2 0 ) = 2K, and d(w 2 0 , w 1 0 ) = 2K. Hence, since d(v 2 0 , w 1 0 ) = d(v 2 0 , w 2 0 ) = K, any isometric embedding maps v 2 0 to the midpoint of segment w 1 0 w 2 0 , so its Euclidean distance to w 1 1 must be 11 2 K. This is in contradiction with d(v 2 0 , w 1 1 ) = min(ω v 2 0 w 1 0 +ω w 1 0 w 1 1 , ω v 2 0 v 2 1 +ω v 2 1 w 1 1 ) = min(4K, 4K + A n -a 1 )
. The above illustrates that when X contains all spanning trees of G, the complexity of LocRob-Π is still open when one considers only Euclidean metric spaces.

Problem adversarial

We now turn to the diculty of computing the objective function adversarial. Given that

x is xed throughout, we denote G(x) more shortly as G. Furthermore, we denote the sets of vertices and edges of G as V [G] and E[G], respectively. Our rst result (Proposition 3 below) is that adversarial is hard, even when the metric space is reduced to two points, or the input graph is a clique. For this, we consider particularly simple metric spaces, and rely on a reduction from problem max-cut. We recall that max-cut is a famous problem in combinatorial optimization that, given any input graph G, seeks a partition

{V 1 , V 2 } of V [G] such that |{e ∈ E[G] : |e ∩ V 1 | = 1}| is maximized.
Proposition 3. Even when |M| = 2, there is no PT AS for adversarial unless P = N P.

Proof. Let us denote the objective function of

max-cut as f max-cut (V 1 , V 2 ) = |{e ∈ E[G] | |e ∩ V 1 | = 1}|
. Further, we denote by opt max-cut (G) the value of an optimal solution for graph G. Given an input graph G of max-cut, we dene M = {0, 1} and I as the graph G itself,

U i = M for any i ∈ V [G], and the distance d by d(x, y) = |x -y|. Given a solution {V 1 , V 2 } (which is a partition) of max-cut, we dene u i = 0 if i ∈ V 1 ,
and

1 if i ∈ V 2 . This implies c(u, I) = f max-cut (V 1 , V 2 ). For the reverse direction, given a solution u of adversarial, we dene V 1 = {i | u i = 0} and V 2 = V [G] \ V 1 , and we also have c(u, I) = f max-cut (V 1 , V 2 ).
The above immediatly implies that there is an S-reduction (see for instane Crescenzi (1997)) from max-cut to adversarial, proving the result.

Let us now turn to parameterized complexity, and let tw be the treewidth of G, see Section EC.1.1. of the online supplement for the formal denition of treewidth. Informally, tw measures the thickness of a tree structure dening G. In particular, tw(G) = 1 for any tree G.

As we show in the next section that computing adversarial is polynomial on trees, a natural question is to determine if we can extend this result by proving that adversarial/tw admits an FPT algorithm (where adversarial/tw denotes problem adversarial parameterized by tw, as dened in Section EC.1.2. of the online supplement), meaning an algorithm running in f (tw) • |I| c for some computable function f and constant c. The following proposition implies that it is very unlikely, and thus places adversarial with the few problems that are not FPT by treewidth.

Proposition 4. adversarial/tw is W[1]-hard.

Proof. Given a graph G, and a set of integers (called colors) L(i) for any i ∈ V [G], problem list-col aims at deciding whether we can nd a color

f (i) ∈ L(i) for any i ∈ V [G] such that for any edge {i, j} ∈ E[G], f (i) = f (j). It is known Fellows et al. (2011) that list-col/tw is W[1]-hard.
Let us now prove that there is a parameterized reduction from list-col/tw to adversarial/tw, which implies (see Section EC.1.2. of the online supplement) that 3.

adversarial/tw is W[1]-hard. Given a graph G a list of colors L(i) for any i ∈ V [G], we dene M = i∈V [G] L(i), and
d(c 1 , c 2 ) = 0 is c 1 = c 2 ,

Exact solution of robust-Π

A popular type of algorithms solving exactly dicult robust optimization problems replaces the large uncertainty set by an approximation of small cardinality, leading to a relaxation of the original problem. Then, these algorithms iterate between solving integer programming formulations for the robust problem with small uncertainty set, and checking the optimality of the solution for the relaxation by solving an adversarial separation problem. This process leads to cutting plane algorithms (e.g., Bertsimas et al. (2016), Fischetti and Monaci (2012),

Naoum-Sawaya and Buchheim ( 2016)). Such algorithms involve frequent calls to computing the objective function adversarial, so we start this section by studying how to solve this problem. Then, we detail in Section 3.2 the overall cutting plane algorithm for LocRob-Π.

Problem adversarial

As in Section 2.2, we denote G(x) more shortly as G in what follows. Given the hardness results from the previous section, we propose two approaches to computing adversarial that have non-polynomial running times in general. The rst approach relies on an integer programming formulation. For each i ∈ V and k ∈ {1, . . . , σ i }, binary variable y k i takes value 1 if and only if vertex i is located at position u k i . Therefore, adversarial is equal to

max {i,j}∈E[G] σ i k=1 σ j =1 d(u k i , u j )y k i y j s.t. σ i k=1 y k i = 1, ∀i ∈ V [G] y i ∈ {0, 1} σ i , ∀i ∈ V [G]
which can be linearized using classical techniques.

It is also possible to compute adversarial eciently whenever G has small treewidth tw(G) using a dynamic programming algorithm. Let us detail the algorithm whenever G is a tree rooted at vertex r, which we assume oriented from r to its leaves L. We denote by D(i)

the set that contains the direct descendants of i, which is empty if i is a leaf. Let opt(i, u i ) be the maximum value obtained for the subtree starting at i given that node i is located at u i . We obtain the following recursion:

opt(i, u i ) = j∈D(i) max u j ∈U j d(u i , u j ) + opt(j, u j ), i ∈ V [G] \ L 0, i ∈ L (2)
and the optimal solution cost is given by max ur∈Ur opt(r, u r ). Dynamic programming recursion (2) will be used in our numerical experiments, which involve trees and stars.

Recall that tw = tw(G) and let us further denote σ = max i∈V [G] σ i . Using dynamic programming on a well-chosen tree decomposition of G (see Section EC.1.1. of the online supplement for the denition), one can readily extend the above idea to any graph of bounded treewidth, leading to Theorem 1, whose proof is deferred to Section EC.2 of the online supplement. We point out that according to Proposition 4 we cannot (unless

W[1] =FPT )
remove the dependency in σ to get for example a O(poly(n) × f (tw)), and this holds for any computable function f .

Theorem 1. adversarial/tw + σ is FPT . More precisely, we can compute an optimal solution of adversarial in time O(n × tw × σ O(tw) ).

Cutting plane algorithm for the robust problem

Now that we have depicted numerical methods for computing adversarial, we wish to make the extra step towards the exact solution of the complete problem, LocRob-Π. For this, we design an exact solution algorithm that generates scenarios of U on the y in the course of a branch-and-cut algorithm.

Let U be a nite subset of U. An exact algorithm for LocRob-Π, described in Algorithm 1, relies on the following relaxed formulation

min    ω ω ≥ {i,j}∈E x ij d(u i , u j ), ∀u ∈ U, x ∈ X    . (3)
Algorithm 1 describes an iterative cutting-plane implementation, alternating between the solution of the relaxed master problem (3) and the adversarial separation problem adversarial. Practical implementation of these algorithms typically rely instead on branchand-cut algorithms, where the adversarial separation problem is solved at each integer node of the branch-and-bound-tree.

Algorithm 1: Cutting-plane algorithm for LocRob-Π repeat Let (ω, x) be an optimal solution of (3) Let G be the graph induced by

x Compute c(G) = max u∈U {i,j}∈E[G] d(ũ i , ũj ) and let ũ be a maximizer if c(G) > ω then U ← U ∪ {ũ} until c(G) ≤ ω return G

Compact formulation for stars

Depending on the structure of the elements of X , the dynamic programming recursion (2) naturally leads to a compact formulation for the problem. We detail next this idea for the case where any x ∈ X describes a union of disjoint stars rooted at the elements of a known set R ⊆ V. For each r ∈ R and u k r ∈ U r , let us introduce the optimization variable z k r to model opt(r, u k r ), the cost of the star rooted at r given that u r = u k r . Let N (i) be the set of neighbours of any node i ∈ V. Plugging variables z and x into (2) and noticing that any node connected to r must be a leaf, we immediately obtain

z k r = j∈N (r)
x rj max

u j ∈U j d(u k r , u j ). (4)
Notice that the maximization appearing in the right-hand-side of (4) does not involve optimization variables, se we can dene the constant d max rkj = max u j ∈U j d(u k r , u j ). Then, introducing z r as the worst-case cost of the star rooted at r, we have

z r = max k∈[σr] z k r = max k∈[σr] j∈N (r)
x rj d max rkj .

(5)

Overall, we wish to minimize the sum of z r over all r ∈ R. Reformulating (5) through an epigraphic reformulation, we obtain

min ω s.t. ω ≥ r∈R z r (6) z r ≥ j∈N (r) x rj d max rkj , ∀r ∈ R, k ∈ [σ r ] (7)
x ∈ X , z ≥ 0

The above construction can, in theory, be extended to trees. However, in that case the recurrence relations lead to products between variables, which turns out to be inecient numerically. See Section EC.3 of the online supplement for details.

Conservative approximation

We introduce next a (conservative) approximation of LocRob-Π that leads to compact formulations. Let us introduce an additional optimization variable µ e ∈ M for each e ∈ E, and consider the following optimization problem

min x∈X µ∈M |E| max u∈U {i,j}∈E x ij (d(u i , µ ij ) + d(µ ij , u j )). (cons-Π)
One might interpret the additional variable µ ij as a compulsory crossing point from vertex i to vertex j, regardless of the position of these vertices. Using these crossing points, each distance function only involves a single node, leading to simpler reformulations as we show below.

Remark 3. Due to the triangle inequalities, the optimal solution cost of cons-Π is not smaller than the optimal solution cost of LocRob-Π, so cons-Π is a conservative approximation of LocRob-Π.

We show next how to reformulate cons-Π as a discrete optimization problem featuring a polynomial number of variables. Noticing that {i,j}∈E

x ij (d(u i , µ ij ) + d(µ ij , u j )) = i∈V {i,j}∈E x ij d(u i , µ ij ),
we obtain

max u∈U {i,j}∈E x ij (d(u i , µ ij )+d(µ ij , u j )) = max u∈U i∈V {i,j}∈E x ij d(u i , µ ij ) = i∈V max u i ∈U i {i,j}∈E x ij d(u i , µ ij ).
Thus, we can introduce an additional variable d i for each node i ∈ V, so cons-Π can be reformulated as

min i∈V d i (8) s.t. d i ≥ {i,j}∈E x ij d(u i , µ ij ), ∀i ∈ V, u i ∈ U i (9) x ∈ X , µ ∈ M |E| . ( 10
)
The interest of the above reformulation is that the uncertainty sets U i , i ∈ V, appear in distinct constraints, so (9) contains i∈V σ i constraints, which is signicantly smaller than the i∈V σ i elements in the global uncertainty set U. In practice, the numerical diculty of problem (8)(10) typically depends on the considered metric space (M, d) and feasibility set X . For instance, using ad-hoc pre-processing rules, we may be able to reduce the domain of each variable µ ij to a small subset of M ij ⊂ M. These rules may not even need to be exact as problem (8)( 10) is only a conservative approximation of the original problem LocRob-Π.

In what follows, we further develop the case where (M, d) is the p-dimensional Euclidean space so the distance d(u i , u j ) = u i -u j 2 is now well-dened for any u i , u j ∈ R p . We can leverage this to relax the discrete restriction µ ∈ M |E| to µ ∈ R p×|E| , obtaining

min i∈V d i (11) s.t. d i ≥ {i,j}∈E x ij u i -µ ij 2 , ∀i ∈ V, u i ∈ U i (12) x ∈ X , µ ∈ M |E| . ( 13
)
The non-linearities in constraints ( 12) can be avoided by replacing

x ij u i -µ ij 2 with x ij u i - µ ij 2 : if x ij = 1,
ν k i,e (15)
ν k i,e ≥ x e u k i -µ e 2 , ∀e ∈ E, i ∈ e, k ∈ [σ i ] (16) x ∈ X , µ ∈ M |E| . ( 17
)
We conclude this section by mentioning that ( 14

x ij u i -u j 2 , ∀u ∈ U (19) x ∈ X . ( 20
)
We detail in Section EC.4 of the online supplement how each constraint ( 19) can be reformulated by introducing recourse variables which, approximated through ane decision rules, leads exactly to (14)(17). This connection underlines that the dierence between the optimal solution costs of LocRob-Π and cons-Π can be interpreted as the suboptimality of ane decision rules for approximating two-stage robust optimization. It also suggests that stronger conservative approximations could be obtained by using more expressive decision rules, such as the lifted ane decision rules proposed by de Ruiter and Ben-Tal (2017).

Computational experiments

In this section, we compare numerically the exact algorithm from Section 3, denoted exact hereafter, with three heuristic algorithms that solve deterministic counterparts of LocRob-Π.

Namely, each of these heuristics considers a symmetric function d : V × V → R + and returns the optimal solution of min x∈X {i,j}∈E x ij dij . Three such functions d are considered:

worst: dij = max center: dij = d(β i , β j ), where β i is any geometric median of U i , dened as

u i ∈U i ,u j ∈U j d(u i , u j ),
β i ∈ arg min u∈M u ∈U i d(u, u ). avg: dij = 1 σ i σ j u i ∈U i ,u j ∈U j d(u i , u j ).
We also include in our numerical assessment the conservative approximation depicted in Section 4, and denoted cons. We compare these algorithms on the applications mentioned in the introduction: a subway network design problem, modeled as a Steiner tree problem (STP), and a simple plant location problem (SPL). Since the applications involve stars and trees, the separation problems of exact can be solved using the dynamic programming recurrence presented in (2).

The purpose of our experiments is two-fold. First and foremost, we wish to assess the numerical eciency of the exact solution algorithm in terms of solution times. Second, we measure the approximation ratios obtained by the heuristic algorithms, by comparing the cost of their solutions to the optimal solution costs.

Steiner tree problem

We consider the problem of expanding the subway network of a city, modeled as a Euclidean

Steiner tree problem. The compulsory points model the future stops of the subway, while the other points model the possible knickpoints of the lines. We thus consider an undirected graph G = (V, E) where T ⊆ V denotes the set of compulsory vertices; we consider an arbitrary root r ∈ T and set T 0 = T \ {r}. Set X thus contains all trees of G that cover the vertices of T . Sets U i ⊆ R 2 model the possible locations for the vertices, which we assume to be polyhedral sets, and we assume that the distance d(u i , u j ) = u i -u j 2 is the Euclidean distance.

We consider the classical disaggregated MILP formulation for the problem involving two sets of variables (Magnanti and Wong 1984). For each undirected edge {i, j} ∈ E, binary variable x ij takes value 1 if and only if the edge is used. Then, for each t ∈ T 0 and e = {i, j} ∈ E, the fractional variable f t ij decides how much ow related to t is sent on the directed arc (i, j). Let E bidir be the set of directed edges obtained from E by including the two opposite edges (i, j) and (j, i) for each undirected edge {i, j} ∈ E. Dening the incoming and outgoing stars at node i as δ -(i) = j (j, i) ∈ E bidir and δ + (i) = j (i, j) ∈ E bidir , respectively, and the balance of vertex i as b

t i = 0 for i ∈ T 0 \ {t}, b t r = -1 and b t t = 1, we obtain min   max u∈U {i,j}∈E x ij u i -u j 2   s.t. (j,i)∈δ -(i) f t ji - (i,j)∈δ + (i) f t ij = b t i , ∀i ∈ V, t ∈ T 0 f t ij + f t ji ≤ x ij , ∀{i, j} ∈ E, t ∈ T 0 f ≥ 0, x binary

Instances

We assess the dierent solution algorithms on the instances P6E with 100 vertices and 5 terminals (p619, p620, and 621) that are publicly available at http://steinlib.zib.de/ testset.php. Each of these instances has 180 edges. The position of the vertices, denoted ūi hereafter, are not available in the data les P6E, so we estimate them using a variant of the MDS-MAP algorithm from Shang et al. (2003). Specically, we apply classical multidimensional scaling (MDS) from the Julia package MultivariateStats (see https: //github.com/JuliaStats/MultivariateStats.jl) to compute the positions ū from the distances, completing the distance matrix with the shortest path values. The uncertainty sets U i , i ∈ V are then computed randomly based on two parameters: ∆ that scales the diameter of each set U i , and σ the common number of elements of all U i , i ∈ V. To be more precise, we rst compute the average distance among pairs of points in V, d = i<j ūi -ū j n(n-1)/2 . For each i ∈ V, we then uniformly draw one random value in ρ i ∈ [0, ∆ • d] and dene the circle C i of center ūi and radius ρ i . Then, we take σ equidistant points on C i , yielding

U i = ūi1 + ρ i cos 2kπ σ , ūi2 + ρ i sin 2kπ σ , k = 1, . . . , σ .
We consider each ∆ ∈ {0.2, 0.4, 0.6} and σ ∈ {4, 8, 12}. Following the above procedure, we create 5 random instances for each P6E instance and choice of parameters, yielding 135 instances in total.

Results

Figure 3 reports the average solution times, illustrating the impact of the dimension of the diameters of the uncertainty sets, represented by ∆, and the number of elements in each set, given by σ. The gure illustrates that, unsurprisingly, the three deterministic counterparts are solved much faster than cons and exact. More interesting is the fact that exact is faster than the heuristic algorithm cons when ∆ is small. However, the diculty of solving exact grows rapidly with the value of ∆. Notice also that three instances based on p621, corresponding to ∆ = 0.6, could not be solved to exact optimality within two hours, ending with optimality gaps of 1%, 5%, and 7%, respectively. Hence, the value reported on Figure 3a for ∆ = 0.6 is actually a lower bound for the true average value. Figure 5: Optimal solutions for instance p620 with ∆ = 0.6 and σ = 4, for which z(center)/z * = 1.46. Grey vertices are common to both solutions, while colored ones represent nominal positions and each element of U i for the vertices that are not shared by the two solutions (the facets of conv(U i ) have been added for clarity). We see how center disregards diameters, ending up with additional nodes having large uncertainty sets. More precisely, computing the average diameters of internal nodes for both solutions leads to 1974 and 3350 for exact and center, respectively. reports

g(x) = 100 #{instances for which z(H) ≤ (1 + x) • z * } #{all instances} . ( 21
)
These results show that worst, avg and cons provide solutions with values very close to the optimal one, with cons being the best of the three, always leading to the optimal solution. In contrast, the quality of center becomes rather poor as ∆ increases, ranging up to an extra cost 50% for some of these instances, and with nearly half of the instances with ∆ = 0.6 having an extra cost of at least 20%.

For some insight on the poor results of center, one may observe that it is the only approximation that completely neglects the shape (and diameter) of the uncertainty sets.

This means that the solution of center may make poor choices when selecting the nonterminal vertices included in the tree. In particular, the solution of center is likely to include non-terminal vertices whose uncertainty sets have much larger diameters than those selected in an optimal solution. We illustrate this by drawing an optimal solution and the solution returned by center in Figure 5. For more details on these aspects we refer to Bougeret et al.

(2022) where we study the approximation ratios of worst and center. Among other results, we show that while worst achieves a constant approximation ratio, the solution of center can be arbitrarily bad.

Remark 4. The optimality of the solutions returned by cons that is displayed on Figure 4 means that optimizing along function

c cons (x) = min µ max u∈U {i,j}∈E x ij (d(u i , µ ij ) + d(µ ij , u j ))
returns the same optimal solution as optimizing along the true objective

c(x) = max u∈U {i,j}∈E x ij d(u i , u j ).
It does not mean, however, that the conservative approximation (or, equivalently, the ane decision rule approximation, as discussed in Section EC.4 of the online supplement) is exact in this case. Specically, looking at the detailed results reveals that c cons (x * ) > c(x * ) for the optimal solution x * returned by cons.

Simple plant location

We consider a strategic facility location problem where the exact location of the facility may be perturbed due to local political and technical considerations, while the exact position of the clients themselves is subject to uncertainty (Correia and da Gama 2015). The distances between the facilities and the clients are computed from the shortest path distance on a weighted graph that represents the underlying road network. The problem can then be modeled with the weighted graph G = (V, E, l), the vertices of which represent the possible locations for the facilities and clients, while each edge and its weight represent the existence of a road between two vertices together with its length. The metric is induced by graph G, so M = V and d(u, v) is equal to the shortest path between u and v for every u, v ∈ V .

Let I ⊆ V and J ⊆ V represent the set of clients and possible locations for the facilities.

We consider the problem of choosing p facilities among J and assigning every client to its closest facility so as to minimize the total assignment cost. For each j ∈ J, let y j be a binary variable indicating whether a facility is located at j, and for each i ∈ I, j ∈ J, let

x ij ∈ {0, 1}
indicate whether client i is assigned to facility j. The robust problem can then be formulated as min max u∈U i∈I,j∈J

x ij d(u i , u j ) s.t. j∈J x ij = 1, ∀i ∈ I x ij ≤ y j , ∀i ∈ I, j ∈ J j∈J y j = p
x, y binary

Instances

We construct the graph G = (V, E, l) as follows. For each vertex i, we generate its position u i uniformly in the square [0, 1] 2 and we select edges so that the resulting graph is planar and connected and shorter edges are more likely to appear. This procedure allows to mimic real transportation networks (Daskin 1993). More precisely, we rst compute a minimum cost spanning tree based on the weights

{w ij = u i -u j -2
2 } to ensure the graph is connected. Then, we iteratively select m -n + 1 additional edges following the probability distribution

P rob ij = w ij {i ,j } w i j
for each i = j ∈ V while ensuring the resulting graph is planar. The length l ij of each edge {i, j} ∈ E is then given by u i -u j 2 and the the distance between every pair of vertices is given by the shortest path between them in G. For each i ∈ V, we dene U i as the σ vertices that are closest to i. Finally, I is dened as a random subset of V such that U i ∩ U i = ∅ for each i, i ∈ I and J = V \ I. Following the above procedure, we create 2 random instances for each choice of parameters n, m, σ and |I|, leading to 486 instances.

Results

Figure 6 reports the average solution times, showing that exact is able to solve every instance to optimality within a few seconds, being roughly twice slower than the heuristic algorithms.

The gure further underlines that n is the parameter having the strongest impact on the solution time. This was expected given that larger values for n imply more elements in I and J, and therefore, larger models. The charts presented for the remaining 4 parameters do not lead to clear conclusions. Heuristic cons is not included in the comparison because its eciency strongly depends on the denition of sets M ij , as discussed in Section 4. While dening M ij = M is likely to be intractable, it would lead to the tightest bounds. To obtain a good trade-o between quality and time, one should come up with ad-hoc sets M ij ⊂ M obtained through heuristics that would be tailored to the specic instances used. This is beyond the scope of the current paper, which aims at proposing general methods rather than ad-hoc algorithms for specic data sets.

Then, following again formula (21), Figure 7 reports the cumulative distributions of the cost increase of each of the three deterministic heuristics, relatively to the cost of the exact solution. The results focus only on the parameters having an impact on the resuting costs, namely n and σ. They illustrate that avg is the best approximation, followed closely by worst and center. They also show that center behaves worse for small instances and those having larger uncertainty sets.

Overall, these results illustrate that given the quick solution times of exact due to the compact formulation presented in Section 3.3, heuristic algorithms do not seem necessary for obtaining good solutions to this problem. Yet, if one wishes to reduce further the solution times, avg should be preferred over worst and center. 21), the cumulative distribution of the % of instances for which the returned solution has an additional (relative) cost less than the value of the abscissa.

Concluding remarks

This paper has been devoted to the study of general combinatorial optimization problems dened in spatial graphs with locational uncertainty, thus encompassing applications arising in transportation and facility location, among others. After proving the N P-hardness of these problems, we have developed an exact solution algorithm based on scenario generation.

The bottleneck of this algorithm lies in the separation problem, so we have studied in depth the complexity of that problem, also proposing an integer programming formulation. We have also proposed a conservative approximation that turns out to be equivalent to the ane decision rules approximation by Zhen et al. (2021) in the case of Euclidean distances. We have compared these algorithms numerically to dierent deterministic approximations on Steiner tree and location instances inspired by the scientic literature.

Our results illustrate that the exact algorithms are fast, being able to solve in reasonable amounts of time instances of realistic sizes. They also illustrate that the deterministic reformulations based on average or worst-case distances provide very good solutions in short amounts of time, oering interesting alternatives whenever an exact solution cannot be computed in an acceptable time.

Last, our solution algorithms and reformulations critically rely on the fact that the un-certainty sets are independent for each vertex i ∈ V. We believe that extending these to more general (correlated) uncertainty sets would be an interesting topic for future research.

gygn wD pomin pD uowlik vD vokshtnov hD wrx hD ilipzuk wD ilipzuk wD urh @PHISA Parameterized Algorithms @pringerAD v http://dx.doi.org/10.1007/ 978-3-319-21275-3F hskin w @IWWQA qenrndPX e rndom network genertorF Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, USA F de uiter pD fenEl e @PHIUA rtle nonliner deision rules for roust optimiztionF ehnil reportD orking pperF howney qD pellows w @PHIQA Fundamentals of Parameterized ComplexityF exts in gomputer iene @pringerAD v http://dx.doi.org/10.1007/978-1-4471-5559-1F hunning sD ruhette tD vuin w @PHIUA tumpX e modeling lnguge for mthemtil optimiztionF SIAM Review SW@PAXPWS!QPHD v http://dx.doi.org/10.1137/15M1020575F pellows wD pomin pD vokshtnov hD osmond pD urh D zeider D homssen g @PHIIA yn the omplexity of some olorful prolems prmeterized y treewidthF Information and Computation PHW@PAXIRQ!ISQF pishetti wD woni w @PHIPA gutting plne versus ompt formultions for unertin @integerA liner progrmsF Math. Program. Comput. R@QAXPQW!PUQF qutiérrezEtrp qD yreque gD vporte qD wrinov @PHIQA pid trnsit network design for optiml ost nd origin!destintion demnd ptureF Computers & Operations Research RH@IPAXQHHH!QHHWD sx HQHSEHSRVD v http://dx.doi.org/https://doi.org/10.1016/j. cor.2013.06.013F rnsusnto qeD uuhn hD iesemnn @PHISA uEdptility in twoEstge roust inry proE grmmingF Operations Research TQ@RAXVUU!VWIF usperski eD ieli«ski @PHHWA yn the pproximility of minmx @regretA network optimiztion prolemsF Information Processing Letters IHW@SAXPTP!PTTF usperski eD ieli«ski @PHITA oust disrete optimiztion under disrete nd intervl unerE tintyX e surveyF Robustness analysis in decision aiding, optimization, and analyticsD IIQ!IRQ @pringerAF uloks @IWWRA Treewidth, Computations and ApproximationsD volume VRP of Lecture Notes in Computer Science @pringerEerlgAD v http://dx.doi.org/10.1007/BFb0045375F uouvelis D u q @PHIQA Robust discrete optimization and its applicationsD volume IR @pringer iene 8 fusiness wediAF wgnnti vD ong @IWVRA xetwork design nd trnsporttion plnningX wodels nd lgoE rithmsF Transportation science IV@IAXI!SSF wrín eD elegrín w @PHIWA Ewedin prolemsF Location ScienceD PS!SH @pringer snE terntionl ulishingAD sfx WUVEQEHQHEQPIUUEPD v http://dx.doi.org/10.1007/ 978-3-030-32177-2_2F welkote D hskin w @PHHIA en integrted model of fility lotion nd trnsporttion network designF Transportation Research Part A: Policy and Practice QS@TAXSIS!SQVD sx HWTSEVSTRD v http://dx.doi.org/https://doi.org/10.1016/S0965-8564(00)00005-7F xoumEwy tD fuhheim g @PHITA oust ritil node seletion y enders deompositionF INFORMS J. Comput. PV@IAXITP!IURD v http://dx.doi.org/10.1287/ijoc.2015.0671F ostek uD hen rertog h @PHITA wultistge djustle roust mixedEinteger optimiztion vi iterE tive splitting of the unertinty setF INFORMS Journal on Computing PV@QAXSSQ!SURF oos iD hen rertog hD fenEl eD de uiter ptD hen t @PHIVA epproximtion of hrd unertin onvex inequlitiesF Optimization Online URL http://www.

EC.2. Computing the objective function on small treewidth graphs

Throughout this section, we consider the graph G = (V, E) and denote by u |X the vector u restricted to components u i such that i ∈ X, for any X ⊆ V .

EC.2.1. Denition of the auxiliary problem

In this section we consider that we are given a xed input of adversarial, and a nice tree

decomposition D = (T, B) of G. Given w ∈ V [T ], we denote U w = × i∈V [G w ] U i . Let us dene the following maximization problem Π. An input of Π is a pair (w, f ) where w ∈ V [T ],
and f is a function from X w to M such that for any i ∈ X w , f (i) ∈ U i . An output is a vector u ∈ U w such that for any i ∈ X w , u i = f (i), which we denote by u (w, f ). The objective is to maximize c(u, G w ). We denote by opt(w, f ) the optimal value for instance (w, f ). As usual in DP algorithms, to simplify the presentation we will dene an algorithm A that given an input (w, f ) only computes the value opt(w, f ). This algorithm could be easily modied to get an associated optimal solution.

EC.2.2. Join case

Let w be a join vertex with children w L and w R . Given two vectors u

L ∈ U w L and u R ∈ U w R , such that for any i ∈ X w , u L i = u R i , we dene u = u L u R by u i = u L i for any i ∈ V [G w L ], and
u i = u R i for any i ∈ V [G w R ]. Observe that u is well dened as for i ∈ X w , u L i = u R i .
Lemma 1. Let (w, f ) be an input of Π such that w is a join vertex with children w L and w R . For any u ∈ U w , u (w, f ) if and only if there exists u L , u R such that the following conditions hold:

u L (w L , f ) u R (w R , f ) X r = ∅.
Then, we output A(r, ∅). Notice that as X r = ∅, the second parameter (the function from X r to M) is dened nowhere and denoted ∅. As A solves Π optimaly, we have A(r, ∅) = opt(r, ∅). Moreover, as G r = G, we have opt(r, ∅) = c(G).

Let us now consider the running time of A. Given a tree decomposition with N vertices (in the tree of bags) and of width t, the size of the DP table is O(N σ t ), the time to compute one entry is dominated by the forget case where the branching is in O(σ), implying a running time in O(N σ t+1 ). Plugging the corresponding values, we get the claimed running time.

EC.3. Compact formulation for the Steiner Tree Problem

We extend next the construction from Section 3.3 to trees, albeit this involves logical constraints. We consider more particularly the case of the Steiner Tree Problem where a set of terminals T ⊆ V is given and any feasible solution is a Steiner tree connecting the terminals of T . We further assume that r is a given arbitrary root in T and that any x ∈ X describes an directed tree from r to the set of terminals T \ {r}. In particular, this involves that the edges are directed, so variables x ij and x ji now denote the two directed edges (i, j) and (j, i) obtained from {i, j}, leading to the directed set of edges E bidir . Similarly, we introduce the incoming and outgoing stars of i as δ -(i) = j (j, i) ∈ E bidir and δ + (i) = j (i, j) ∈ E bidir , respectively.

Then, extending the optimization variable z to any node in V , we obtain the following formulation min ω

s.t. ω ≥ z k r , ∀k ∈ [σ r ] (22)
z k i ≥ j∈δ + (i) x ij max ∈[σ j ] d(u k i , u j ) + z j , ∀i ∈ V, k ∈ [σ j ] (23) x ∈ X , z ≥ 0. ( 24
)
To linearize the maxima in the right-hand-side of (23), we introduce variables Z k ij such that

Z k ij ≥ d(u k i , u j ) + z j , ∀ ∈ [σ j ]
and replace (23) with The right-hand-side of constraints ( 25) can be further linearized with the help of additional variables X k ij and logical constraints

z k i ≥ j∈δ + (i) x ij Z k ij , ∀i ∈ V \ T 0 , k, ∈ [σ j ]. (25)
x ij = 1 =⇒ X k ij ≥ Z k ij .
We illustrate and compare the above formulation on small articial instances built upon the format instance which includes 7 vertices and 9 edges (the instance is available at http: //steinlib.zib.de/format.php). To get larger instances from the format instance, we remove the central terminal and add layered copies of the instance. Figure 8 depicts the original structure of the format instance and that obtained by adding one copy. We denote as format(κ) the instance with κ copies of the original graph. The results presented on Figure 9 underline that compact can hardly solve large instances, as the solution times increase signicantly with κ. They also illustrate that cons is much slower than exact on these small articial instances.

EC.4. Connection with the ane decision rules approximation from Zhen et al. (2021) Notice rst that, due to the convexity of the norm, the constraint ∀u ∈ U :

{i,j}∈E

x ij u i -u j 2 ≤ ω is equivalent to ∀u ∈ conv(U) :

{i,j}∈E

x ij u i -u j 2 ≤ ω.

Next, let us denote the unit ball of dimension p by W p , as well as W = × e∈E W p . Let us also direct arbitrarily every edge in E, leading to the set of directed edges E. Following the same idea as (Zhen et al. 2021, Theorem 1), we obtain that the constraint ∀u ∈ conv(U) :

(i,j)∈ E

x ij u i -u j 2 ≤ ω is equivalent to ∀u ∈ conv(U) :

(i,j)∈ E x ij max w ij ∈W p w T ij (u i -u j ) ≤ ω (26)
⇔∀w ∈ W, u ∈ conv(U) :

(i,j)∈ E

x ij w T ij (u i -u j ) ≤ ω (27) ⇔∀w ∈ W : max

   (i,j)∈ E x ij w T ij σ i k=1 λ k i u k i - σ j =1 λ j u j σ i k=1 λ k i = 1, ∀i ∈ V, λ ≥ 0    ≤ ω (28) ⇔∀w ∈ W : min    i∈V µ i µ i ≥   (i,j)∈ E x ij w T ij - (j,i)∈ E x ji w T ji   u k i , ∀i ∈ V, k ∈ [σ i ]    ≤ ω. ( 29
)
Observe that the left-hand side of (29) can be interpreted as a two-stage robust optimization problem without rst-stage variables, with µ playing the role of the second-stage variables, and with w representing the uncertain parameters. This type of models being notoriously dicult to solve to optimality, we follow (Zhen et al. 2021, Lemma 1) and seek a heuristic solution by considering second-stage variables µ that can be expressed as ane decision rules

µ i (w) = µ 0 i + (i ,j )∈ E µ T i,i j w i j , (30)
where µ 0 i ∈ R and µ i,i j ∈ R p . Replacing ( 19) by ( 29) with µ substituted with the right-hand side of (30), we obtain min ω

s.t. ω ≥ i∈V   µ 0 i + (i ,j )∈ E µ T i,i j w i j   , ∀w ∈ W µ 0 i + (i ,j )∈ E µ T i,i j w i j ≥   (i,j)∈ E x ij w T ij - (j,i)∈ E x ji w T ji   u k i , ∀i ∈ V, k ∈ [σ i ], w ∈ W x ∈ X .
Dualizing the robust counstraints with respect to w ∈ W yields min ω (31)

s.t. ω ≥ i∈V µ 0 i + (i,j)∈ E µ i,ij + µ j,ij + i =i,j µ i ,ij 2 (32)
µ 0 i ≥ (i,j)∈ E x ij u k i -µ i,ij 2 + (j,i)∈ E x ji u k i + µ i,ji 2 + (i ,j )∈ E:i =i ,j µ i,i j 2 , ∀i ∈ V, k ∈ [σ i ] (33)
x ∈ X .

(34)

We discuss next how we can substantially reduce the number of ane multipliers in (30), and consequently, in problem (31)(34). Let (ω, x, μ0 , μ) denote an optimal solution to (31)(34).

Observe that the optimal solution cost is equal to ω = max u∈U ω(u) where

ω(u) = i∈V   (i,j)∈ E xij u i -μi,ij 2 + (j,i)∈ E xji u i + μi,ji 2 + (i ,j )∈ E:i =i ,j μi,i j 2   + (i,j)∈ E μi,ij + μj,ij + i =i,j μi ,ij 2 (35) = (i,j)∈ E   xij u i -μi,ij 2 + xij u j + μj,ij 2 + i =i,j μi ,ij 2 + μi,ij + μj,ij + i =i,j μi ,ij 2   (36)
We are going to dene a sequence of two new solutions, μ and μ , such that the corresponding values ω (u) and ω (u) are not greater than ω(u) for each u ∈ U. First, we dene μ by setting μ i ,ij = 0 for all (i, j) ∈ E such that i / ∈ {i, j} and μ i ,ij = μi ,ij otherwise, and let ω (u) be the right-hand side of (36) with µ replaced by µ . Observe that i =i,j

μ i ,ij 2 + μ i,ij + μ j,ij + i =i,j μ i ,ij 2 = μ i,ij + μ j,ij 2 = μi,ij + μj,ij 2 ≤ i =i,j μi ,ij 2 + μi,ij + μj,ij + i =i,j μi ,ij 2
, which implies that

ω (u) ≤ ω(u), (37)
for each u ∈ U. Second, we dene another solution μ such that μ i,ij = μ i,ij and μ j,ij = -μ i,ij , ∀(i, j) ∈ E. Then, we denote as ω (u) the corresponding right-hand side of (36).

Observe that for each u ∈ U

ω (u) = (i,j)∈ E xij u i -μ i,ij 2 + xij u j + μ j,ij 2 + μ i,ij + μ j,ij 2 (38)
= (i,j)∈ E xij u i -μ i,ij 2 + xij u j -μ i,ij 2 ≤ ω (u). (39)
From ( 37) and (39), we see that we can set μi ,ij = 0 for all (i, j) ∈ E such that i / ∈ {i, j} and μi,ij = -μ j,ij , ∀(i, j) ∈ E without deteriorating the quality of the solution returned by (31)(34). Thus, renaming the variables µ i,ij as µ ij , formulation (31)(34) becomes

min ω s.t. ω ≥ i∈V µ 0 i µ 0 i ≥ (i,j)∈ E x ij u k i -µ ij 2 + (j,i)∈ E x ji u k i -µ ji 2 , ∀i ∈ V, u ∈ U
x ∈ X , and the equivalence with (14)(17) follows by removing the dummy variable ω, introducing articial variables to separate the norms into individual second-order cone constraints, and renaming µ 0 i as d i .

Figure 1 :

 1 Figure 1: Reduction from partition when U is a Cartesian product of segments.

  and 1 otherwise. We dene the uncertainty set of G as follows: for any i, we let U i = L(i). It is now straightforward to verify that we have a YES-instance of list-col if and only if c(G) = |V [E]|. As the reduction can be computed in polynomial time, and the graph (and thus its treewidth) is unchanged, this provides a parameterized reduction, and we get the desired result.

  as suggested by Citovsky et al. (2017).

  The algorithms have been coded in Julia(Bezanson et al. 2012), using JuMP (Dunning et al. 2017) to interface the mixed integer linear programming (MILP) solver CPLEX. They have been carried out on a processor Intel(R) Core(TM) i7-10510U CPU1.80GHz using up to 4 threads in parallel and with a total running time limit of 2 hours. The source code of every algorithm and the data sets are publicly available at https://github.com/mjposs/ locational_uncertainty.

Figure 3 :

 3 Figure 3: STP: Average solution times in seconds on instances P6E for each algorithm when varying one of the parameters.

Figure 4 :

 4 Figure 4: STP: % of instances for which the additional relative cost is less than x.

Figure 4

 4 Figure4reports the cumulative distributions of the cost increase for each of the four heuristic algorithms, relatively to the cost of the exact solution. Formally, let z(H) denote the cost of the solution returned by H ∈ {center, worst, avg, cons} and z * denote the optimal solution cost. For each H ∈ {center, worst, avg, cons}, the corresponding curve

Figure 6 :

 6 Figure 6: SPL: Average solution times in seconds for each algorithm when varying one of the parameters.

Figure 7 :

 7 Figure7: SPL: For each heuristic algorithm, the curve plots (21), the cumulative distribution of the % of instances for which the returned solution has an additional (relative) cost less than the value of the abscissa.

Figure 8 :

 8 Figure 8: Small instances inspired by the format instance from SteinLib, T contains the larger nodes.

Figure 9 :

 9 Figure 9: STP: Average solution times in seconds on instances format(κ) for each algorithm when varying one of the parameters.

  Function u i -u j 2 is closely related to the second-order cone (SOC) constraints considered by Zhen et al. (2021) for robust problems with polyhedral uncertainty sets. Zhen et al. (2021) linearize such robust SOC constraints by introducing adjustable variables, turning the problem into an adjustable robust optimization problem that can be tackled exactly (Ayoub and Poss 2016, Zhen et al. Interestingly, the approach of Zhen et al. (2021), extended in Roos et al. (2018) to more general convex functions, makes no particular assumption on the feasibility set of the decision variables X . A second work closely related to LocRob-Π is that of Citovsky et al. (2017),

	2018, Zeng and Zhao 2013) or approximately using ane decision rules (Ben-Tal et al. 2004)
	or nite adaptability approaches (Bertsimas and Dunning 2016, Hanasusanto et al. 2015,
	Postek and Den Hertog 2016, Subramanyam et al. 2019), among others.

who rely on computational geometry techniques to provide constant-factor approximation algorithms in the special case where X contains all Hamiltonian cycles of G. They propose in particular to solve a deterministic counterpart of LocRob-Π where the uncertain distances are replaced by the maximum pairwise distances d max ij

  both expressions coincide; otherwise, x ij = 0, and setting µ ij = 0 also yields equality. Introducing additional variables to isolate each norm into a unique constraint, we nally obtain the following mixed-integer second-order cone programming formulation

	min	d i	(14)
	i∈V
	s.t. d i ≥
		e∈E i∈e

  optimizationonline.org/DB_HTML/2018/06/6679. html F hng D uml D hng D promherz w @PHHQA voliztion from mere onnetivityF Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computingD PHI!PIPF is a yes-instance of L 1 if and only if (x , k ) is a yes-instance of L 2 , k ≤ g(k) for some computable function g, and the running time is bounded by f (k) • |x| O(1) for some computable function f . If L 1 is W[1]-hard and there is a parameterized reduction from L 1 to L 2 , then L 2 is W[1]-hard

	urmnym eD qounris giD iesemnn @PHIWA uEdptility in twoEstge mixedEinteger roust optimiztionF Mathematical Programming Computation I!QPF mn rD ursn yiD inr wÇ @PHHIA he roust spnning tree prolem with intervl dtF Oper. Res. Lett. PW@IAXQI!RHD v http://dx.doi.org/10.1016/S0167-6377(01)00078-5F (x, k) as well.
	eng fD ho v @PHIQA olving twoEstge roust optimiztion prolems using olumnEndE onstrint genertion methodF Operations Research Letters RI@SAXRSU!RTIF
	hen tD de uiter ptD oos iD den rertog h @PHPIA oust optimiztion for models with unE ertin seondEorder one nd semide(nite progrmming onstrintsF INFORMS Journal on Computing F
	hen tD rertog hhD im w @PHIVA edjustle oust yptimiztion vi pourierEwotzkin iliminE tionF Operations Research TT@RAXIHVT!IIHHD v http://dx.doi.org/10.1287/opre.2017.
	1714F

Electronic Companion

EC.1. Denitions related to parameterized complexity and treewidth EC.1.1. Tree decompositions and treewidth A tree decomposition of a graph G = (V, E) is a pair D = (T, B), where T is a tree and B = {X w | w ∈ V [T ]} is a collection of subsets of V , called bags, such that:

for every edge {i, j} ∈ E, there is a w ∈ V [T ] such that {i, j} ⊆ X w , and for every {x, y, z} ⊆ V [T ] such that z lies on the unique path between x and y in T ,

We call the vertices of T vertices of D and the sets in B bags of D. The width of a tree decomposition D = (T, B) is max w∈V [T ] |X w | -1. The treewidth of a graph G, denoted by tw(G), is the smallest integer t such that there exists a tree decomposition of G of width at most t. Let us now recall the denition of a nice tree decomposition, which will make the presentation of the algorithm used to proof Theorem 1 much simpler.

Let D = (T, B) be a rooted tree decomposition of G (meaning that T has a special vertex r called the root). As T is rooted, we naturally dene an ancestor relation among bags, and say that X w is a descendant of X w if the vertex set of the unique simple path in T from r to w contains w. In particular, every vertex w is a descendant of itself. For every w ∈ V [T ],

Such a rooted decomposition is called a nice tree decomposition of G if the following conditions hold:

Every vertex of T has at most two children in T .

For every leaf ∈ V [T ], X = ∅. Each such vertex is called a leaf vertex.

If w ∈ V [T ] has exactly one child w , then either X w = X w ∪ {i} for some i ∈ X w . Each such vertex is called an introduce vertex.

X w = X w \ {i} for some i ∈ X w . Each such vertex is called a forget vertex.

1 If w ∈ V [T ] has exactly two children w L and w R , then X w = X w L = X w R . Each such vertex w is called a join vertex.

We recall that one of the key property of such a nice decomposition is that for any w ∈ V [T ],

X w is a separator of G. This implies in particular that, in a join vertex, there is no edge

Given a tree decomposition of a graph G of width t and x vertices, it is possible to transform it in polynomial time into a nice one of width t and xt vertices (Kloks 1994).

Moreover, it is possible (Bodlaender et al. ( 2013 The most common way to transfer W[1]-hardness is via parameterized reductions. A parameterized reduction from a parameterized problem L 1 to a parameterized problem L 2 is an algorithm that, given an instance (x, k) of L 1 , outputs an instance (x , k ) of L 2 such that

). In the ⇐ direction, observe that u L u R is well dened as for any i ∈ X w , u L i = u R i = f (i), and u (w, f ) is also immediate.

Lemma 2. Let (w, f ) be an input of Π such that w is a join vertex with children w L and w R . Then, opt(w, f ) = opt(w L , f )+opt(w R , f )-d (w,f ) , where

Proof. Let us start with the ≤ inequality. Let u such that c(u, G w ) = opt(w, f ). Let u L and u R as dened by Lemma 1. Observe that c(u, G w ) = c(u, G w L ) + c(u, G w R ) -d (w,f ) as edges inside X w are counted twice in the rst two terms. We have c(u, G w L ) = c(u L , G w L ), and c(u L , G w L ) ≤ OP T (w L , f ) as u L (w L , f ), and same properties hold for the right side.

Let us now turn to the other inequality. Let w,f ) , implying the desired inequality.

We are now ready to dene the DP algorithm A in the join case. Given an input (w, f ) of Π such that w is a join vertex with children w L and w R , A(w, f ) returns A(w L , f ) + A(w R , f ) -d (w,f ) . It follows from induction and using Lemma 2 that A(w, f ) = opt(w, f ).

EC.2.3. Introduce case

Given any input (w, f ) of Π and X ⊆ X w , we denote by f |X function f restricted to X. The following two lemmas are easily veried. Lemma 3. Let (w, f ) be an input of Π such that w is an introduce vertex with children w . Let i be such that X w = X w ∪ {i}. For any u ∈ U w , u (w, f ) if and only if the following conditions hold:

Lemma 4. Let (w, f ) be an input of Π such that w is an introduce vertex with children w . Let i be such that X w = X w ∪ {i}. Then, opt(w, f ) = opt(w , f |X w ) + d (i,w,f ) , where

4

We are now ready to dene the DP algorithm A in the introduce case. Given an input (w, f ) of Π such that w is an introduce vertex with children w , where X w = X w ∪{i}, A(w, f ) returns A(w , f |X w ) + d (i,w,f ) . Using Lemma 4 and induction, we obtain that A(w, f ) = opt(w, f ).

EC.2.4. Forget case

Let (w, f ) be an input of Π such that w is a forget vertex with children w . Let i such that X w = X w ∪ {i}. For any x ∈ M, we denote f (i,x) the function from X w to M such that f (i,x) (j) = f (j) for any j = i, and f (i,x) (i) = x. We obtain the following lemma.

Lemma 5. Let (w, f ) be an input of Π such that w is a forget vertex with children w . Let i be such that X w = X w ∪ {i}. For any u ∈ U w , u (w, f ) if and only if u (w , f (i,u i ) ).

Lemma 6. Let (w, f ) be an input of Π such that w is a forget vertex with children w . Let i be such that X w = X w ∪ {i}. Then, opt(w, f ) = max x∈U i opt(w , f (i,x) ).

Proof. Observe rst that

Let us now turn to the other inequality. Let x * ∈ U i maximizing the right side. Let u such that c(u, G w ) = opt(w , f (i,x * ) ). Notice that as u (w , f (i,x * ) ), u i = x * , and thus u (w , f (i,u i )). According to Lemma 5, u (w, f ), implying that c(u, G w ) = c(u, G w ) ≤ opt(w, f ).

We are now ready to dene the DP algorithm A in the forget case. Given an input (w, f ) of Π such that w is a forget vertex with children w , where X w = X w ∪ {i}, A(w, f ) returns max x∈U i A(w , f (i,x) ). It follows by induction and using Lemma 6 that A(w, f ) = opt(w, f ).

EC.2.5. Putting pieces together

Theorem 2. adversarial/tw + σ is FPT . More precisely, we can compute an optimal solution of adversarial in time vertices. Remember that this nice tree decomposition is rooted on a vertex r such that