Je Remercie Particulièrement Ada

Benoît, Bérengère, Brigitte, Dominique, Dritan, Gérald, Gildas, Laurie Benjamin

Louise

Lyes

Mylène Nathalie Michael

Rym Sabine Paul

Véronique Merci

Christophe Andry

Marianne Gaëtan

François Les Corentin

Deux Guigui

Maxime Thibaud Karim

Eliane Christian

Keywords: Operational research, combinatorial optimization, dominance rules, constraint programming, delay-tolerant networks, systems of systems

avoir accepté de rapporter ce manuscrit, ainsi que Jacques Carlier et Vincent Jost pour avoir participé au jury. Je suis heureux d'avoir pu leur présenter mes travaux, et j'espère très sincèrement qu'ils ont pris plaisir à évaluer cette thèse. Je remercie tout particulièrement Jacques, notre Grand Guru à tous, qui en plus de nous avoir conseillés dans l'étude de complexité menée en début de thèse, m'a fait l'immense honneur de présider le jury.

Je remercie ensuite Antoine Jouglet pour sa patience et sa disponibilité durant ces trois années passées en sa compagnie. Chargé de TD en recherche opérationnelle, en programmation orientée objet, en programmation logique, en programmation par contraintes, puis responsable d'un projet de recherche sur le job shop, et enfin directeur de thèse passionnant, il aura été à tous les étages de ma formation utcéenne. Dans chacune de ses missions, sa pédagogie excelle, son dévouement est complet, et ses qualités humaines... simplement indiscutables. Mon aventure universitaire se serait sans aucun doute arrêtée trois ans plus tôt sans Antoine. Je tiens d'ailleurs à m'excuser auprès de son épouse Delphine et de leurs enfants pour les nombreuses heures dominicales qu'il a sacrifiées pour moi.

S ystems of systems are supersystems comprising elements which are themselves complex, independent operational systems, all interacting to achieve a common goal [START_REF] Jamshidi | System of Systems Engineering: Principles and Applications[END_REF]. When the subsystems are mobile and deployed in extreme environments, these may suffer from a lack of continuous end-to-end connectivity. To address the technical issues in such networks, the common approach is termed delay-tolerant networking [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. Routing relies on a store-forward mechanism -i.e. data are sent from one system to another, depending on the communication opportunities that arise when two systems are close to each other, and stored throughout the network in hope that all messages will reach their destination.

In this work, we assume that the trajectory of each system (of each node) is deterministic and perfectly known. Thus, we focus on applications where it is possible to make realistic predictions about node mobility. This includes satellite networks (where the trajectory of nodes depends on straightforward physics) and public transportation systems. The problem is making the best use of knowledge about possibilities for communication -termed contacts in the literature -when data need to be routed from a set of nodes to another within a given time horizon. The fundamental question is "which elements of the information should be transferred from which node to which node when contacts occur". A solution to this problem is termed a transfer plan.

The literature on that topic is limited. Intermittently-connected networks have been widely addressed with opportunistic [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF] and stochastic [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Burns | MV routing and capacity building in disruption tolerant networks[END_REF][START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF] approaches, but few papers [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF][START_REF] Jain | Routing in a delay tolerant network[END_REF][START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF] have considered the deterministic case (although the applications mentioned above may require such studies). In particular, in our opinion, the literature already proposes very interesting models, but still lacks a clear and unified framework for such a situation.

That is why we started the thesis by formalizing the problem. We notably studied a simplified version -the dissemination problem -where we consider a single datum, split into several datum units, to be transmitted from a set of source nodes to a set of recipient nodes. To this end, we consider a sequence of contacts, i.e. an ordered set of pairs of nodes. During each contact, at most one datum unit can be transferred from one node called sender, to another called receiver. We proved that this (combinatorial) problem is strongly NP-Hard, when there are at least two recipients, or at least two datum units.

Subsequently we worked towards solving this problem. More specifically, we proposed several dominance rules to reduce its search space. These lead to deduction algorithms aiming at identifying useless contacts, and necessary transfers. Typically, a contact that is never leveraged in a dominant solution can be removed from the instance before the main solving process starts, i.e. before the enumeration procedure starts. These deductions algorithms, used as preprocessing procedures, achieved very promising results. Unfortunately our numerical experiments showed that they were inefficient when combined with a branch-and-cut algorithm (when they were dynamically used while an integer linear program modelling the problem was being solved).

Afterwards, to more appropriately use the dominance rules, we proposed a constraint-programming-based enumeration algorithm (a branch-and-bound procedure). This significantly outperformed the integer-linear-programmingbased approach mentioned above. Constraint programming was shown to be particularly adapted to incorporation of ad hoc computations/methods, e.g. lower bounds, symmetry breaking techniques, nogood recording. It achieved the best experimental results on a benchmark of self-generated instances.

Finally, we addressed a robust version of the problem. This ongoing work aims to find robust transfer plans. More precisely, we seek solutions enabling the datum units to be correctly delivered, even if some transfers fail. This is based on an adaptation of the constraint programming algorithm developed beforehand for the case where all failures are disregarded. We actually hope that our approach will help prediction errors to be more effectively managed in practice.

Note that this work was presented at three international congress (namely EURO|INFORMS 2013, MISTA 2013 [START_REF] Bocquillon | Minimizing the dissemination length in the one-datum-unit data transfer problem[END_REF] and BWCCA 2013 [START_REF] Bocquillon | Data Transfer in Delay-Tolerant Networks[END_REF]). It won the first MS2T Award during the first international workshop organised by Labex MS2T [START_REF] Labex | Control of Technological Systems-of-Systems[END_REF] in october 2013. A study on the complexity of the dissemination problem has been published in the international, peered-reviewed, European Journal of Operational Research [START_REF] Bocquillon | The data transfer problem in a system of systems[END_REF]. Two other papers have been submitted to similar journals. These papers [START_REF] Bocquillon | A constraint-programming-based approach to solve the data dissemination problem[END_REF][START_REF] Bocquillon | Modeling elements and solving techniques for the data dissemination problem[END_REF] deal with more technical aspectse.g. dominances rules, constraint programming, etc. 1

Table of contents

The dissemination problem T he present chapter describes the background and the issues that led to this thesis. We will first remind the limits of TCP/IP protocols for networks subject to frequent partitioning (termed intermittently-connected networks), and subsequently what leads to the emergence of delay-tolerant networks (cf. Section 1.1). Then we will focus on the challenges related to routing data in such a network. The common approach is to use a store-forward mechanism -i.e. data are sent from one node to another, depending on the communication opportunities that arise, and stored throughout the network in hope that messages will reach their destination (cf. Section 1.2). These works being part of a study on systems of systems, we will also draw the parallel between systems of systems and delaytolerant networks (cf. Section 1.3). Finally, with all these elements in hand, we will formalize the problem that will be tackled in the following chapters. In short, the problem is making use of knowledge about possibilities for communication when data need to be routed from one subset of nodes to another within a given time horizon (cf. Section 1.4). Thus this study focuses on applications where node mobility can be reliably predicted.

Challenged internets

In 2015 the estimated number of Internet users is about three billions, that is more than 40% on a world population of seven billions. This uncontested success relies on the highly popular TCP/IP model [START_REF] Tanenbaum | Computer Networks[END_REF] (that is the Internet protocol suite), whose most important elements are the Transmission Control Protocol and the Internet Protocol. These protocols make key assumptions regarding the performances of underlying links [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF] -e.g. an end-to-end path exists between a data source and its peer(s), the maximum round-trip time between any pair of nodes is not excessive, and the end-to-end packet drop probability is small. These assumptions may not be realistic in networks that are characterized by many disconnections (due to node mobility), a limited longevity (especially where end nodes are placed in a hostile environment), possible lack of large memory (embedded systems), low duty cycle operation (due to energy saving policies for instance), or using non-reusable protocols (these do not usually provide a sufficient abstraction for supporting layered protocol families such as Internet). For instance, disconnections result in the absence of a long-standing reliable end-to-end path, and thus lead to higher latency, poor data rate and long queuing time.

Thus, TCP/IP protocols may operate poorly on exotic networks such as terrestrial mobile networks, wireless sensor networks, vehicle ad hoc networks, military ad hoc networks, low-Earth-orbit space networks, or interplanetary networks.

Many solutions were then proposed to adjust classical protocols to such networks. These include proxy-agent-based approaches, where middle boxes entities (dedicated nodes) translate classical protocols to specific ones, and link-repair approaches [START_REF] Border | Performance Enhancing Proxies Intended to Mitigate Link-Related Degradations[END_REF], which attempt to fool the classical protocols into believing they are operating over a well-performing physical infrastructure.

In general, unfortunately, the first approach leads to less reusable solutions and does not achieve interoperability satisfactorily, while the second increases the complexity of the architecture too significantly [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF].

In fact, the well-known electronic courier service (e-mail) is the closest to address routing challenges in exotic networks. Flexible naming, asynchronous message-based operation, error reporting and interoperability are particularly relevant. E-mail falls short due to its lack of dynamic routing, weakly-defined delivery semantics, and lack of consistent application interface [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF]. Therefore Fall called for a paradigm shift, and proposed a new delay-tolerant network architecture that uses messages as the primary unit of data interchange. This architecture was designed to ensure interoperability, performances, and security in heterogeneous networks where end-to-end routing paths may not exist. It operates as an overlay network on top of the transport layer of disparate regional (permanently connected) networks [START_REF] Fall | A delay-tolerant network architecture for challenged internets[END_REF] (the routing is then hierarchical). A store-forward mechanism is used to address issues related to disconnections between the regional networks (cf. Section 1.2).

For concrete examples, we refer to the following projects:

• Zebranet [START_REF] Juang | Energy-efficient computing for wildlife tracking[END_REF]: researchers drive through a forest collecting data about the dispersed zebra population.

• DakNet [START_REF] Pentland | DakNet: rethinking connectivity in developing nations[END_REF]: a public bus carries a mobile access point between villages and a large city that has a high-speed Internet connectivity. This way, the bus provides a disconnected Internet access to isolated villages.

• Bluespots [START_REF] Lebrun | Bluetooth content distribution stations on public transit[END_REF]: a small computer on a bus serves as a bluetooth content distribution station in a university public transit scenario.

• Disaster Monitoring Constellation [START_REF] Wood | Use of the Delay-Tolerant Networking Bundle Protocol from Space[END_REF]: a multi-satellite Earth-imaging low-Earth-orbit sensor network where captured image swaths are stored onboard each satellite and later downloaded from the satellite payloads to a ground station.

Delay-tolerant networks

When end-to-end connections are difficult (impossible) to establish, routing in a delay-tolerant network relies on a store-forward approach -i.e. messages are transferred from one node to another, depending on the communication opportunities (termed contact) that arise, and stored throughout the network in hope that each message will reach its destination(s).

To minimize latency, and/or to maximize the chances of a message being successfully transmitted to its destination(s), the common solution, termed epidemic routing [START_REF] Vahdat | Epidemic Routing for Partially Connected Ad Hoc Networks[END_REF], is to replicate messages and to spread out many copies over the network. Of course, this approach is not suitable where nodes have limited memory capacity, or where links bandwidth is weak.

In fact, when nodes produce contents that are larger than links capacity, nodes must slice messages in order to transmit fragments (also termed datum units) separately. This raises the problem of deciding the datum units to be sent during each contact (whenever nodes meet). Belblidia et al. [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF] proposed, for example, a popularity-based decentralized heuristic (named Prevalence-Aware Content Spreading) which tends to homogenize the dissemination of each piece of data in the network. This problem has exercised an increasing number of researchers over the last decade. Many [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Burns | MV routing and capacity building in disruption tolerant networks[END_REF][START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF] proposed some stochastic methods that estimate different probabilistic metrics to, in fine, decide the data to be transmitted. Others [START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF][START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF] considered deterministic time evolving networks and proposed solutions that optimize a given criteria (average delay, robustness, ...). These approaches focus on applications where it is quite possible to make realistic predictions about node mobility. Such applications include satellite networks (where the trajectory of nodes depends on straightforward physics), fleets of drones, and public transportation systems. For example, Jain et al. [START_REF] Jain | Routing in a delay tolerant network[END_REF] built a scenario with twenty buses, equipped with wireless communication devices, making scheduled trips inside San Francisco.

These so-called deterministic delay-tolerant networks are the heart of this thesis. We will address the problem of making use of knowledge about node mobility when information needs to be routed from sources to destinations within a given time horizon. The fundamental question is which elements of the information should be transferred from which node to which node when contacts occur. A solution to such a problem is termed a transfer plan.

The literature is quite limited at this time. Alonso and Fall [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF] proposed a linear formulation for computing a minimum delay transfer plan (routing) with respect to a set of nodes, a set of contacts and a set of messages. Links need to be assigned to data such that every message can travel through the network from one sender to one receiver. The formulation incorporates some constraints that are to be found in real applications, e.g. transmission delay (the length of time required by the sending node to process all the bytes that are sent), propagation delay (the amount of time it takes for the head of the signal to travel from the sender to the receiver over the medium concerned), and buffers capacity (embedded memory). As in most of the works presented below, data transmissions are modelled by unidentified numbers of bytes to be transferred through a dynamic transportation graph. So the problem can be seen as a dynamic multi-commodity flow problem [START_REF] Even | On the Complexity of Timetable and Multicommodity Flow Problems[END_REF] in which messages are commodities, and edge capacities are time-varying. The main drawback here is that flow conservation constraints forbid duplication of data, making such approaches unsuitable for multicast and multisource situations. Alonso's and Fall's works were subsequently extended by Jain et al. [START_REF] Jain | Routing in a delay tolerant network[END_REF], who in particular proposed oracles to compare the performances of routing algorithms in terms of the amount of knowledge of network topology that is required. For example, the contacts oracle can answer any question regarding the contacts. Computational tests showed, as expected, that the greater the available knowledge, the better the performances. Zhao et al. [START_REF] Zhao | Multicasting in delay tolerant networks[END_REF] extended the oracles of Jain et al. to take multicasting protocols into account, e.g. the membership oracle answer questions related to group dynamics. In this thesis we consider that all the oracles are available.

Interferences are often neglected (since delay-tolerant networks are often sparse). In order to address higher-dimensional problems, other assumptions were proposed. For example, Handorean et al. [START_REF] Handorean | Accommodating Transient Connectivity in Ad Hoc and Mobile Settings[END_REF] defined atomic contacts, where contact durations (as opposed to inter-contact durations) are assumed to be instantaneous (both propagation and transmission delays are therefore disregarded). Later, Hay and Giaccone [START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF] made the same assumptions, and proposed a remarkable model that they called the event-driven graph. As the graph is time-independent and polynomial in size with respect to the number of contacts in the instance, very basic tools from graph theory can be used to solve numerous problems straightforwardly. So, for example, the authors solve shortest-path or maximum-flow subproblems to minimize the delay or to maximize the network throughput.

Other models were proposed. Merugu et al. [START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF] proposed the space-time graph, i.e. a graph comprised of several snapshots (instantaneous connectivity graphs) placed side by side, and interconnected by temporal edges. Ferreira [START_REF] Ferreira | Building a reference combinatorial model for MANETs[END_REF] proposed the evolving graph, an effective combinatorial model capturing the most significant characteristics of time-varying networks. This model will be described in Section 1.4.

Finally -for those who want to go further -we refer to the delay-tolerant networking research group [START_REF]The delay-tolerant networking research group[END_REF], Voyiatzis' survey [START_REF] Voyiatzis | A Survey of Delay-and Disruption-Tolerant Networking Applications[END_REF], and to Zhang's survey [START_REF] Zhang | Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges[END_REF] for their extensive review of the literature. The large number of papers that they reference, reflects a high level of interest in problems of routing in delay-tolerant networks.

However, to our knowledge, no paper has so far addressed the multisource case, despite its relevance if resulting algorithms are to be executed on-line, such as when routing tables need to be refreshed dynamically, following new predictions on node mobility or connectivity.

Systems of systems

We actually address problems of routing in delay-tolerant networks to better identify issues related to communications in systems of systems (these works being part of a multi-disciplinary scientific program that is focused on Control of Technological Systems of Systems [START_REF] Labex | Control of Technological Systems-of-Systems[END_REF]). Systems of systems have been defined in many ways. However, a practical definition may be that systems of systems are supersystems comprising other elements that are themselves complex, independent operational systems, all interacting to achieve a common goal [START_REF] Jamshidi | System of Systems Engineering: Principles and Applications[END_REF]. To this end, the systems (satellites, drones, sensors, ...) exchange information and collaborate.

From a data transportation point of view, when systems are mobile and intermittently connected, a system of systems can be considered as a delaytolerant network comprised of several heterogeneous systems. Every system is characterized by:

• the capacity of its buffer, which quantifies the amount of bytes that the system is able to store in its non-volatile memory (when this overflows, a specific algorithm has to select some datum units to be dropped);

• the life expectancy of its battery, which limits the activity of the whole system for a given period;

• a set of data that it wishes to store during a given period (or before a given deadline), and a set of data it already stores;

• and some transmitters (e.g. Bluetooth and/or IEEE 802.11 devices).

Transmitters are communication devices (interfaces) that enable the systems to collaborate and share data, by making opportunistic use of the possibilities for communication (contacts) that arise when two entities are close enough to each other. Every contacts is characterized by:

• the time interval during which the link is active;

• its transmission delay -the length of time required by the sending node to process all the bytes that are sent (the delay caused by the bit-rate, also known as the bandwidth of the link);

• and its propagation delay -the length of time it takes for the signal to travel from the sender to the receiver (this may be significant in some applications, particularly in extraterrestrial networks where signals may take several hours to reach their destination, e.g. the end-to-end round trip time from Jupiter and Pluto to Earth vary between 81.6 and 133.3 minutes, and between 593.3 and 1044.4 minutes respectively, according to the orbital location of the planets [START_REF] Akyildiz | InterPlaNetary Internet: state-of-the-art and research challenges[END_REF]).

Contacts enable elements of a system of systems to collaborate and to route information from a subset of source nodes to a subset of recipient nodes. Such a collaboration becomes necessary, for example, where contact durations are relatively short with respect to the quantity of information to be transferred, and where, consequently, the complete data cannot be transferred in a single contact. To tackle this problem, modern protocols subdivide data into several datum units which are sent in any order to recipient systems [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF].

It is worth nothing here that the datum units may be sent to non-recipient messenger systems whose role is to store and pass on the datum units.

The challenge is to find a valid transfer plan (valid store-forward routing paths) to transfer data from their sources to their destinations. Some criteria may have to be optimized, such as:

• the dissemination lengths (the average or the maximum delay);

• the number of contacts that are actually tapped (energy saving policy);

• or the robustness (the impact of network failures on the solution).

In this thesis, we only focus on the first criterion, i.e. the maximum delay is to be minimized. Note, however, that we will also consider some robustness constraints in Chapter 5 (at first networks failures will be disregarded).

In Table 1.1 we provide an overview of the constraints to be found in the literature. In particular, we report the papers which studied these constraints or, conversely, which neglected them. In the following, we make some of these assumptions too.

• The network is assumed to be very sparse. Therefore interferences are disregarded [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Handorean | Accommodating Transient Connectivity in Ad Hoc and Mobile Settings[END_REF][START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF][START_REF] Jain | Routing in a delay tolerant network[END_REF][START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF][START_REF] Mongiovi | Efficient multicasting for delay tolerant networks using graph indexing[END_REF][START_REF] Zhao | Multicasting in delay tolerant networks[END_REF].

• Contact durations (as opposed to inter-contact durations) are assumed to be instantaneous. So both propagation and transmission delays are neglected -i.e. contacts are atomic [START_REF] Handorean | Accommodating Transient Connectivity in Ad Hoc and Mobile Settings[END_REF][START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF][START_REF] Mongiovi | Efficient multicasting for delay tolerant networks using graph indexing[END_REF].

• Buffers [START_REF] Handorean | Accommodating Transient Connectivity in Ad Hoc and Mobile Settings[END_REF][START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF][START_REF] Mongiovi | Efficient multicasting for delay tolerant networks using graph indexing[END_REF] and batteries [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Handorean | Accommodating Transient Connectivity in Ad Hoc and Mobile Settings[END_REF][START_REF] Jain | Routing in a delay tolerant network[END_REF][START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF][START_REF] Mongiovi | Efficient multicasting for delay tolerant networks using graph indexing[END_REF][START_REF] Zhao | Multicasting in delay tolerant networks[END_REF] are infinite. • We consider one datum, sliced into several datum units. These are then sent separately [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF]. During every contact, at most one datum unit can be transferred, from one node to another. In this way, we do not follow the traditional flow-based approach [START_REF] Jain | Routing in a delay tolerant network[END_REF][START_REF] Mongiovi | Efficient multicasting for delay tolerant networks using graph indexing[END_REF][START_REF] Zhao | Multicasting in delay tolerant networks[END_REF], and every datum unit can have multiple sources and multiple destination. In fact, we consider a many-to-many -as opposed to one-to-many [START_REF] Mongiovi | Efficient multicasting for delay tolerant networks using graph indexing[END_REF][START_REF] Zhao | Multicasting in delay tolerant networks[END_REF] -approach.

The dissemination problem

Let us now formally define our problem.

First we consider a set N = {1, 2, . . . , n} of n interacting mobile systems, termed the nodes, and one datum D = {1, 2, . . . , u} of u datum units. Each datum unit (also termed "unit") represents a unitary, indivisible fragment of data. Each node i ∈ N possesses a subset O i ⊆ D of units from the outset. Subset R ⊆ N defines the nodes wishing to obtain the datum D (i.e. all the datum units) inside the given time horizon. For the sake of clarity, the term source nodes (or "sources") will refer to the nodes i ∈ N | O i = ∅. The nodes in R are termed the recipient nodes (or "recipients").

Remark 1.1

To simplify the formulation of this problem, we assume that the recipient nodes need to obtain all the datum units. Note, however, that the results described in this manuscript can all be generalised (with minor updates) to the case where the recipients only need a subset of the units.

To ensure the dissemination of the datum D, nodes may exchange datum units whenever they are close enough to communicate (such a communication opportunity is termed a contact). We assume that the contacts are perfectly known, or easily predictable at any time, since the trajectory of each node is deterministic. Thus, we consider a sequence of contacts σ = {σ 1 , σ 2 , . . . , σ m } of m ordered pairs of N 2 . During contact (s, r) ∈ σ, the sending node s can send to the receiving node r at most one datum unit that it already possesses (either from the outset or as a result of previous contacts). Once the contact has occurred, node r also possesses unit k. Below nodes s c and r c denote the sender and the receiver in contact σ c ∈ σ, i.e. σ c = (s c , r c ).

Remark 1.2

To represent an undirected contact [i, j], we can consider a first directed contact (i, j), followed by a reverse contact (j, i). Similarly, to represent a longer contact (i, j), during which several datum units might be sent, we can duplicate the contact (one contact per possible transfer).

A transfer plan φ : {1, 2, 3, . . . , m} → {∅, {1}, {2}, . . . , {u}} is a function where φ(c) designates the datum unit received by node r c during contact σ c . If φ(c) = ∅, then nothing is transmitted during contact σ c . From now on T φ denotes the target set {∅, {1}, {2}, . . . , {u}} of φ. Each transfer plan φ has a corresponding set of states O t i ⊆ D, defined for each node i ∈ N , and each time index t ∈ {0, 1, . . . , m}, such that:

(1) ∀i ∈ N , O 0 i = O i , (2) ∀c ∈ {1, 2, ..., m}, O c rc = O c-1 rc ∪ φ(c), (3) ∀c ∈ {1, ..., m}, ∀i ∈ N \{r c }, O c i = O c-1 i (1.1)
Thus each state O t i contains the datum units received by node i during the first t contacts of sequence σ (in addition to the datum units that node i has possessed from the outset). The transfer plan is valid where nodes transmit only datum units that they possess, i.e.

∀σ c ∈ σ, φ(c) ∈ {∅} ∪ {{k} | k ∈ O c-1 sc } (1.2)
A valid transfer plan φ has a delivery length λ i (φ) for each node i ∈ N , corresponding to the smallest time index t at which node i possesses all the units k ∈ D, i.e. λ i (φ) = min {t ∈ {0, 1, . . . , m} | O t i = D}. If this index does not exist, then it is assumed that λ i (φ) = ∞. The dissemination length λ(φ) of the transfer plan corresponds to the smallest time index t at which all the recipient nodes are delivered, i.e. λ(φ) = max i∈R {λ i (φ)}.

The dissemination problem is to find a valid transfer plan φ minimizing the dissemination length λ(φ). The problem is NP-Hard in the strong sense, but it can be polynomially solved if u = 1 or |R| = 1 (cf. Chapter 2). It can be seen as the offline version of the problem tackled by Belblidia et al. [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF].

Evolving graphs

An instance of this problem can be described by an evolving graph [START_REF] Ferreira | Building a reference combinatorial model for MANETs[END_REF], that is a multigraph whose vertices represent nodes, and whose arcs represent connections between these nodes. An arc is labelled with time intervals that indicate when the link is really active. To appropriately take account of time constraints, the notion of path is replaced by the notion of journey, that is an ordered set of arcs having increasing labels. For our requirements, every contact is thus represented by one arc whose label is given by its position in the sequence σ.

In Figure 1.1, [σ 1 = (1, 6), σ 3 = (6, 5)] is a journey (because 3 ≥ 1). This represents the fact that node 6 can forward the unit it receives from node 1 at time 1 to node 5 at time 3. Nonetheless, [σ 13 = (5, 6), σ 1 = (1, 6)] is not a journey (since 1 < 13). More generally, given a datum unit k ∈ D, a journey [(i, u), . . . , (v, j)] between a source node i ∈ N | k ∈ O i and a recipient j ∈ R represents a store-forward routing to transfer unit k from i to j.

Therefore, as will be shown in Chapter 2, a set of arc-disjoint branchings (in the evolving graph) that are rooted on the source nodes of a given datum unit k ∈ D, and such that the whole covers all the recipient nodes, defines a store-forward routing to disseminate unit k. For example, in Figure 1.1, the bold arcs define a set of branchings to disseminate datum unit 1 from nodes 1 and 2 to all the other nodes. Thus, solving the dissemination problem can be seen as finding such a set of arc-disjoint branchings for each datum unit in an evolving graph (see the branchings with bold and doubled arcs). [START_REF] Akyildiz | InterPlaNetary Internet: state-of-the-art and research challenges[END_REF][START_REF] Bertsimas | The Price of Robustness[END_REF], (6, 1), [START_REF] Bertsimas | The Price of Robustness[END_REF][START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF], [START_REF] Akyildiz | InterPlaNetary Internet: state-of-the-art and research challenges[END_REF][START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF], [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF], . . . , [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF][START_REF] Bertsimas | The Price of Robustness[END_REF]]

(a) an instance of the dissemination problem

⎧ ⎨ ⎩ N = R = {1, 2, 3, 4, 5, 6}; D = {1, 2}; O 1 = {1, 2}; O 2 = {1}; O 3 = O 4 = O 5 = O 6 = ∅ ; σ = [
(b) a valid transfer plan ⎧ ⎨ ⎩ φ(4) = φ(5) = φ(7) = φ(10) = {1}; φ(1) = φ(3) = φ(6) = φ(8) = φ(11) = {2}; φ(2) = φ(9) = φ(12) = φ(13) = ∅ (c) the corresponding evolving graph [22]

Complexity results

A s mentioned in Section 1.4, we are going to prove the "dissemination problem" is NP-Hard in the strong sense (cf. Section 2.1). Thereafter, we will show that this problem can be solved in polynomial time when there is only one datum unit, or only one recipient, or when the number u of datum units and the number |R| of recipients are lower than a given constant (cf. Section 2.2). Besides this, knowing whether there exist k mutually arc-disjoint branchings in an evolving graph -or whether there exist k mutually arc-disjoint Steiner trees in a digraph without circuit -will be shown to be NP-Complete in the strong sense (cf. Section 2.3).

To our knowledge, apart from a few papers on evolving graphs [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF][START_REF] Ferreira | Complexity of Minimum Spanning Tree in Evolving Graphs and the Minimum-Energy Broadcast Routing Problem[END_REF][START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF], there is no previous work attempting to determine the theoretical complexity of routing problems in deterministic delay-tolerant networks. In this chapter we therefore study the complexity of the dissemination problem. We aim to determine the frontier between easy and hard cases.

In Section 2.1, we will show that the general case is NP-Hard in the strong sense. Thereafter, in Section 2.2, we will show that it is polynomially solvable where u = 1 or |R| = 1. Finally, in Section 2.3, we will prove the complexity of two problems also related to delay-tolerant networking.

The data transfer problem

In this section, we show that the problem, called the data transfer problem, of finding a valid transfer plan such that ∀i ∈ R, O m i = D (all the recipients receive all the units) is strongly NP-Hard. It also leads to the NP-Hardness of the dissemination problem (i.e. the optimization version, where the delivery length is minimized).

Let us consider the decision version of the data transfer problem, denoted henceforward as Dt:

Problem 2.1 -the data transfer problem Given a set N = {1, 2, . . . , n} of n nodes • a subset R ⊆ N of recipient nodes • a sequence σ = (σ 1 , . . . , σ m ) of m pairs (i, j) ∈ N 2 with i = j • a set D = {1, 2, . . . , u} of u datum units • for each node i ∈ N , a subset O i ⊆ D of datum units initially possessed by node i -is there a valid transfer plan φ : {1, . . . , m} → {∅, {1}, . . . , {u}} | ∀i ∈ R, O m i = D ?
The data transfer problem (Dt) is obviously in NP, since it can be decided in polynomial time whether a transfer plan φ is valid and such that ∀i ∈ R, O m i = D. Below we show the problem is strongly NP-Complete when u = 2 and |R| is not upper bounded, or conversely when |R| = 2 and u is not upper bounded. To achieve this, we reduce a problem known as being strongly NP-Complete to the studied cases.

In [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF], Garey and Johnson give a comprehensive guide to the theory of NP-Completeness, and provide an extensive list of NP-Complete/NP-Hard problems. In this chapter, we consider the 3-Satisfiability problem, referred to below as 3-Sat, cf. [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF], page 259. 3-Sat is strongly NP-Complete and is stated as follows:

Problem 2.2 -3-Satisfiability Given a set X = {x 1 , x 2 , . . . , x p } of p variables • a set C = {c 1 , . . . , c s } of s clauses over X such that, for each c ∈ C, |c| = 3 -
is there a truth assignment that satisfies C ?

The case u ≥ 2

We now show that 3-Sat is reducible in polynomial time to the special case of Dt where u = 2 (Dt2u).

Theorem 2.1

The data transfer problem is strongly NP-Hard for u ≥ 2.

Polynomial-time reduction

Consider an instance of 3-Sat (cf. Problem 2.2). From this instance we build an instance of Dt2u as follows.

Datum -We have u = 2 and then D = {1, 2}.

Nodes -We consider the following nodes.

• With each clause c j ∈ C, j ∈ {1, 2, . . . , s}, is associated a node ω j ∈ N in Dt2u with O ω j = {2}.
The datum units possessed by node ω j will correspond to the logical value of clause c j , in such a way that clause c j will be considered to be true if node ω j possesses datum unit 1, and to be false otherwise. In this way, all clauses are false at the beginning (since the associated nodes possess only unit 2).

• With each variable x i ∈ X, i ∈ {1, 2, . . . , p}, are associated 2 nodes l i and li ∈ N in Dt2u with O l i = Ol i = ∅. The datum units received by these nodes will respectively correspond to the logical values of literals x i and xi . The literal among {l i , li } which will store datum unit 1 will be considered to be true, while the other one (which will store datum unit 2) will be considered to be false. Initially all literals are considered to be undetermined (the associated nodes possess no datum units).

• In Dt2u is also created a node α ∈ N with O α = {1, 2}. This node is the only one that initially possesses the two datum units. It will enable the logical value of each literal to be given by providing unit 1 only to the nodes associated with literals which have to be true, and then unit 2 only to the nodes associated with literals which have to be false.

• The recipients are R = {ω j | j ∈ {1, . . . , s}} ∪ {l i | i ∈ {1, . . . , p}}.
Therefore, exactly n = s + 2p + 1 nodes have been created.

Sequence of contacts -The sequence of contacts σ = σ 1 • σ 2 • σ 3 is built from the concatenation of 3 subsequences:

• subsequence σ 1 is built such that for each i ∈ {1, 2, 3, . . . , p}, we have

σ 1 i = (α, l i ) and σ 1 p+i = (α, li ) (hence |σ 1 | = 2p); • subsequence σ 2 (of size 3s
) is built such that for each j ∈ {1, 2, . . . , s}, considering that c j = {l j1 , l j2 , l j3 }, we have:

for k ∈ {1, 2, 3}, σ 2 3(j-1)+k = (l i , ω j ) if l jk = x i ( li , ω j ) if l jk = xi ;
• and subsequence σ 3 is built such that for each i ∈ {1, 2, . . . , p}, we have

σ 3 i = ( li , l i ) (hence |σ 3 | = p).
Thus, a sequence of exactly m = 3p + 3s contacts has been created.

For example, let us consider the following instance of 3-Sat:

• p = 3 and X = {x 1 , x 2 , x 3 }; • s = 2 and C = {c 1 , c 2 }; • c 1 = {x 1 , x2 , x3 } and c 2 = {x 1 , x2 , x 3 }.
The associated instance for Dt2u is (cf. Figure 2.1):

• u = 2 and D = {1, 2};

• n = 9, N = {ω 1 , ω 2 , l 1 , l 2 , l 3 , l1 , l2 , l3 , α}, and R = {ω 1 , ω 2 , l 1 , l 2 , l 3 }; • O ω 1 = O ω 2 = {2}, O l i = Ol i = ∅ for all i ∈ {1, 2, 3}, and O α = {1, 2}; • m = 15, σ = σ 1 • σ 2 • σ 3 with: -σ 1 = [(α, l 1 ), (α, l 2 ), (α, l 3 ), (α, l1 ), (α, l2 ), (α, l3 )]; -σ 2 = [(l 1 , ω 1 ), ( l2 , ω 1 ), ( l3 , ω 1 ), ( l1 , ω 2 ), ( l2 , ω 2 ), (l 3 , ω 2 )]; -σ 3 = [( l1 , l 1 ), ( l2 , l 2 ), ( l3 , l 3 )].
From a valid transfer plan to a truth assignment satisfying C Suppose that there exists a valid transfer plan φ such that ∀i ∈ R, O m i = D for the Dt2u instance defined above. From this transfer plan, we can build a truth assignment that satisfies C as follows.

The logical values of all literals are set during subsequence σ 1 . Consider the pair of nodes {l i , li } (i ∈ {1, 2, . . . , p}) associated with the pair of literals {x i , xi }. First, during subsequence σ 1 , node l i has an initial contact with α during which it receives at most one unit of D. The situation is identical for node li . Then, during subsequence σ 3 , a contact occurs between nodes li and l i . Since l i ∈ R, the transfer plan is such that O m l i = D. Therefore, the only way for such a transfer plan to be obtained is where, during the contacts of σ 1 , l i obtains one datum unit of D and li obtains the other one. Next, during the contacts of σ 3 , each node li gives its unit to node l i . This process ensures that following subsequence σ 1 (at time t = 2p):

α l 2 l2 l1 l 1 l 3 l3 ω 1 ω 2 σ 2 1 σ 2 4 σ 2 5 σ 2 2 σ 2 6 σ 2 3 σ 3 1 σ 3 2 σ 3 3 {1, 2} {2} {2} σ 1 1 σ 1 4 σ 1 2 σ 1 5 σ 1 3 σ 1 6
O 2p l i = {1} and O 2p li = {2} or O 2p l i = {2} and O 2p li = {1}
In the first case, x i is set to true (and xi is set to false). In the second case, x i is set to false. At the end of the sequence σ 1 , exactly one of the literals in {x i , xi } is then considered to be true, and the other false.

Let us now show that this assignment satisfies C. During the contacts of sequence σ 2 , nodes {l i , li | i ∈ {1, 2, . . . , p}} can only transfer the datum unit they possess to the nodes {ω j | j ∈ {1, 2, . . . , s}} associated with the clauses they are related to. During sequence σ 2 , each node ω j , j ∈ {1, . . . , s}, related to clause c j , is in contact with 3 nodes. These represent the 3 literals which compose the clause. There are therefore 3 possible ways for each node ω j to retrieve datum unit 1 (meaning that c j is true). After sequence σ 2 , all nodes ω j , j ∈ {1, . . . , s} are such that 1 ∈ O 2p+3s

ω j = O m ω j = D, since ω j ∈ R.
Thus there is a truth assignment for C.

In Figure 2.1 the bold arcs correspond to the contacts where datum unit 1 is transmitted (conversely, the doubled arcs correspond to the contacts where datum unit 2 is transmitted). It gives rise to the truth assignment x 1 = true, x 2 = true, and

x 3 = true, which satisfies C = {{x 1 , x2 , x3 }, {x 1 , x2 , x 3 }}.
From a truth assignment satisfying C to a valid transfer plan Let us assume there exists a truth assignment that satisfies C. We can build a corresponding valid transfer plan as follows.

• Subsequence σ 1 : For each i ∈ {1, 2, . . . , p},

φ(i) = {1} and φ(p + i) = {2} if x i is true (x i is false); or φ(i) = {2} and φ(p + i) = {1} otherwise.
• Subsequence σ 2 : For j ∈ {1, 2, 3, . . . , s}, considering that {l j1 , l j2 , l j3 } are the 3 nodes associated with the literals of clause c j ,

∀k ∈ {1, 2, 3}, φ(|σ 1 | + 3(j -1) + k) = {1} if l jk stores unit 1; φ(|σ 1 | + 3(j -1) + k) = ∅ otherwise.
If clause c j is satisfied, at least one node l jk can transmit datum unit 1 to ω j . Therefore, after subsequence σ 2 , every node ω j , j ∈ {1, 2, . . . , s}, possesses all the datum units, i.e. O m ω j = D. • Subsequence σ 3 : For each i ∈ {1, . . . , p}, we set:

φ(|σ 1 • σ 2 | + i) = O 2p li
Recall that li possesses the datum unit that l i needs. Therefore every node l i , i ∈ {1, 2, . . . , p}, possesses all the datum units after σ 3 .

Every node i ∈ R possesses all the datum units. Thus the resulting transfer plan is such that ∀i ∈ R, O m i = D.

The case |R| ≥ 2

We now show that 3-Sat is reducible in polynomial time to the special case of Dt where |R| = 2 (Dt2r). For this purpose we adapt the proof of Even, Itai and Shamir [START_REF] Even | On the Complexity of Timetable and Multicommodity Flow Problems[END_REF] showing that the two-commodity integral flow problem is strongly NP-Complete. The significant difference is that instead of dealing with units of flow, we are now dealing with identified datum units which can be duplicated (i.e. conservation constraints no longer hold).

Theorem 2.2

The data transfer problem is strongly NP-Hard for |R| ≥ 2.

Polynomial-time reduction

Consider an instance of 3-Sat (cf. Problem 2.2, page 15). From this instance we build an instance of Dt2r as follows.

Datum -We set u = s + 1 and D = {0, 1, . . . , s} (exceptionally, for the sake of simplicity, datum units are numbered starting with 0).

Nodes -

We consider the following nodes.

• For i ∈ {1, 2, . . . , p}, let a i and b i be respectively the number of occurrences of x i and of xi in the clauses of C. With every variable x i ∈ X, i ∈ {1, 2, . . . , p}, is associated set

L i = {β i , l 1 i , l 2 i , l 3 i , . . . , l 2a i i , l1 i , . . . , l2b i i , i } ⊆ V of 2(1 + a i + b i ) nodes in Dt2r (cf. Figure 2.2). Initially, these nodes possess no units -i.e. ∀x ∈ L i , O x = ∅. • With each clause c j ∈ C, j ∈ {1, 2, . . . , s}, is associated a node C j ∈ N in Dt2r with O C j = ∅ (cf. Figure 2.3). • Moreover four nodes α 1 , α 2 , ω 1 and ω 2 ∈ N are created in Dt2r with O α 1 = O ω 2 = {0}, O α 2 = O ω 1 = {1, . . . , s} (cf. Figures 2.

and 2.3).

• Finally the recipient nodes are R = {ω 1 , ω 2 }.

Therefore, exactly n = 4 + s + 2 p i=1 (1 + a i + b i ) = 4 + 2p + 7s nodes have been created (since there are three literals per clause).

β i l 1 i l1 i l 2 i l2 i l 3 i l3 i l 4 i l4 i l 2ai-1 i l 2bi-1 i l 2ai i l 2bi i i α 2

Sequence of contacts -

The sequence σ = σ 1 • σ 2 • σ 3 • σ 4 of
contacts is the concatenation of several subsequences built as follows.

• Subsequence σ 1 = σ 1,1,1 • σ 1,2,1 • σ 1,1,2 • σ 1,2,2 • • • • • σ 1,1,i • σ 1,2,i • • • • • σ 1,1,p • σ 1,2,
p is built such that for i ∈ {1, 2, . . . , p},

-we have σ 1,1,i j = (α 2 , l 2j-1 i ) with j ∈ {1, 2, . . . , a i }; -and σ 1,2,i j = (α 2 , l2j-1 i ) with j ∈ {1, 2, . . . , b i } (cf. Figure 2.2).
Therefore

σ 1 contains p i=1 (a i + b i ) = 3s contacts. • Next σ 2 is itself the concatenation of several subsequences. Let σ 2,i = [(β i , l 1 i ), (l 1 i , l 2 i ), (l 2 i , l 3 i ), . . . , (l 2a i -1 i , l 2a i i ), (l 2a i i , i ), (β 1 , l1 i ), ( l1 i , l2 i ), ( l2 i , l3 i ), . . . , ( l2b i -1 i , l2b i i ), ( l2b i i , i )]
be a subsequence of 2(a i + b i + 1) contacts associated with variable x i , and built as follows (cf. Figure 2.2):

-If a i = 0 (literal x i never occurs in C) then contact (β i , i ) occurs, else contact (β i , l 1 i ) occurs, followed in succession by the contacts (l j i , l j+1 i ), j ∈ {1, 2, . . . , 2a i -1}, and finally by contact (l 2a i i , i ). -Subsequently, if b i = 0, contact (β i , i ) occurs, else contact (β 1 , l1 i ) occurs, followed in succession by the contacts ( lj i , lj+1 i ), j ∈ {1, . . . , 2b i -1}, and finally by contact ( l2b i i , i ).

The overall sequence σ 2 is such that (cf. Figure 2.3):

σ 2 = [(α 1 , β 1 )] • σ 2,1 • [( 1 , β 2 )] • σ 2,2 • [( 2 , β 3 )] • . . . . . . • σ 2,p-1 • [( p-1 , β p )] • σ 2,p • [( p , ω 1 )]
First a contact occurs from α 1 to β 1 . Thereafter each subsequence σ 2,j , j ∈ {1, . . . , p}, is successively applied with a contact ( j , β j+1 ) between each pair of sequences (σ 2,j , σ 2,j+1 ), j ∈ {1 . . . , p-1}. Finally a contact occurs from p to ω 1 .

Therefore σ 2 contains 2 + p -1 + p i=1 2(a i + b i + 1) = 2 + 3p + 6s -1 contacts (recalling that there are three literals per clause).

• Subsequence σ 3 is built as follows. For the x th occurrence of literal x i (literal xi ), there is one contact from l 2x i ( l2x i ) to the node C j associated with the clause c j in which x i (x i ) occurs.

In Figure 2 Therefore, subsequence σ 3 contains 3s contacts.

• Subsequence σ 4 = [(c 1 , ω 2 ), (c 2 , ω 2 ), . . . , (c s , ω 2 )]. Thus subsequence σ 4
contains exactly s contacts (cf. Figure 2.3).

In total, a sequence of m = 13s + 3p + 1 contacts has been created.

For example, let us consider the 3-Sat instance defined in Section 2.1.1 -see page 17. The associated instance for Dt2r is (cf. Figure 2.4):

• u = 3 and D = {0, 1, 2};

• n = 4 + 2p + 7s = 24 and

N = { α 1 , α 2 , ω 1 , ω 2 , C 1 , C 2 , β 1 , β 2 , β 3 , 1 , 2 , 3 , l 1 1 , l 2 1 , l1 1 , l2 1 , l1 2 , l2 2 , l3 2 , l4 2 , l 1 3 , l 2 3 , l1 3 , l2 3 }; • O α 1 = O ω 2 = {0}, O α 2 = O ω 1 = {1, 2}, O i = ∅ for all other nodes; • m = 15 and σ = σ 1 • σ 2 • σ 3 • σ 4 with: -σ 1 = [(α 2 , l 1 1 ), (α 2 , l1 1 ), (α 2 , l1 2 ), (α 2 , l3 2 ), (α 2 , l 1 3 ), (α 2 , l1 3 )]; -σ 2 = [ (α 1 , β 1 ), (β 1 , l 1 1 ), (l 1 1 , l 2 1 ), (l 2 1 , 1 ), (β 1 , l1 1 ), ( l1 1 , l2 1 ), ( l2 1 , 1 ), ( 1 , β 2 ), (β 2 , 2 ), (β 2 , l1 2 ), ( l1 2 , l2 2 ), ( l2 2 , l3 2 ), ( l3 2 , l4 2 ), ( l4 2 , 2 ), ( 2 , β 3 ), (β 3 , l 1
3 ), (l 1 3 , l 2 3 ), (l 2 3 , 3 ), (β 3 , l1

3 ), ( l1 From a valid transfer plan to a truth assignment satisfying C

3 , l2 3 ), ( l2 3 , 3 ), ( 3 , ω 1 )]; -σ 3 = [(l 2 1 , C 1 ), ( l2 2 , C 1 ), ( l2 3 , C 1 ), ( l2 1 , C 2 ), ( l4 2 , C 2 ), (l 2 3 , C 2 )]; -σ 4 = [(C 1 , ω 2 ), (C 2 , ω 2 )]. α 1 {0} α 2 {1, . . . ,
1 {0} α 2 {1, 2} ω 2 {0} β 1 0 l 1 1 l 2 1 l1 1 l2 1 1 β 2 l1 2 l2 2 l3 2 l4 2 2 0 0 β 3 l 1 3 l 2 3 l1 3 l2 3 3 0 ω 1 {1, 2} 0 1 2 C 1 C 2 1 2 1 2
Suppose that there exists a valid transfer plan φ such that ∀i ∈ R, O m i = D for the Dt2r instance defined above. From this transfer plan, we can build a truth assignment that satisfies C as follows.

Node ω 1 needs to obtain datum unit 0, because initially it possesses only units {1, 2, . . . , s}. This can only occur where unit 0 is transmitted from α 1 to β 1 during contact (α 1 , β 1 ), and then from β 1 to ω 1 using some contacts of subsequence σ 2 . Thus, for i ∈ {1, . . . , p}, unit 0 is transmitted through:

[(β i , l 1 i ), (l 1 i , l 2 i ), (l 2 i , l 3 i ), . . . , (l 2a i -1 i , l 2a i i ), (l 2a i i , i )] or through [(β 1 , l1 i ), l1 i , l2 i ), ( l2 i , l3 i ), . . . , ( l2b i -1 i , l2b i i ), ( l2b i i , i )]
This means that at least one of these two subsequences is devoted exclusively to transmitting unit 0 (no other unit can then transit through these nodes). Unit 0 next uses contact

( i , β i+1 ) if i < p, or contact ( i , ω 1 ) if i = p.
Node ω 2 needs to obtain the subset {1, 2, . . . , s} of datum units, because initially it possesses only datum unit 0. Each unit must therefore be obtained from a different node C j , since there are exactly s contacts from these nodes to ω 2 . The datum unit k which is transmitted during contact (C j , ω 2 ) comes initially from node α 2 . It has transited either through some nodes from l 2x-1 i to l 2y i (x, y ∈ {1, 2, . . . , a i }, y > x), or through some nodes from l2x-1 i to l2y

i (x, y ∈ {1, . . . , b i }, y > x), so as finally to be transmitted to C j . Note that if datum unit k is transmitted to C j through a node l 2y i or a node l2y i ∈ L i with i > 1, then it cannot come from a node l 2x-1

z or l2x-1 z ∈ L z with 1 ≤ z < i (since datum unit 0 is always transmitted during contact ( i-1 , β i )).
Actually, the path of contacts used to transmit datum unit k to node C j makes it possible to identify the literal that makes clause c j true.

• If k is transmitted through nodes from l 2x-1 i to l 2y i (x, y ∈ {1, . . . , a i }, with y > x), then variable x i is set to true.

• Conversely, if k has been transmitted through from nodes l2x-1 i to l2y i (x, y ∈ {1, . . . , b i }, with y > x), then variable x i is set to false.

We should remember that unit 0 has transited using some of the contacts in subsequence σ 2i , and that x i obviously cannot be true and false at the same time. It should also be noted that the same literal can cause several clauses to be true. In this case, several units -one per true clause -transit through nodes of L i , using one disjoint path of contacts per unit. In other cases, none of the datum units in {1, . . . , s} transits through nodes of L i . It means that variable x i can be arbitrarily set to true or false.

Given that for each clause c j we have found exactly one literal that makes c j true, we can therefore conclude that there is a truth assignment for C.

For the previous example, cf. 2 ), ( l1 2 , l2 2 ), ( l2 2 , C 1 ), (C 1 , ω 2 )], while datum unit 2 can be transmitted through [(α 2 , l3

2 ), ( l3 2 , l4 2 ), ( l4 2 , C 2 ), (C 2 , ω 2 )] -making x 2 = falseand then making both c 1 and c 2 true. In addition unit 0 can be transmitted throughout sequence [(α 1 , β 1 ), (β 1 , l 1 1 ), (l

1 1 , l 2 1 ), (l 2 1 , 1 ), ( 1 , β 2 ), ( 2 , β 3 ), ( 2 , β 3 ), (β 3 , l 1
3 ), (l 1 3 , l 2 3 ), (l 2 3 , 3 ), ( 3 , ω 2 )]. Finally x 1 and x 3 can be set arbitrarily.

From a truth assignment satisfying C to a valid transfer plan

Let us assume there exists a truth assignment that satisfies C. We can build a corresponding valid transfer plan as follows.

First, unit 0 is transmitted during contact (α 1 , β 1 ), during every contact ( i , β i+1 ) with i ∈ {1, 2, . . . , p -1} and then during contact ( p , ω 1 ). For each i ∈ {1, . . . , p}, datum unit 0 is also transmitted through contacts:

[(β i , l 1 i ), (l 1 i , l 2 i ), . . . , (l 2a i -1 i , l 2a i i ), (l 2a i i , i )] if x i = true ; or through [(β i , l1 i ), ( l1 i , l2 i ), . . . , ( l2b i -1 i , l2b i i ), ( l2b i i , i )] otherwise.
Note that unit 0 is transmitted through contact (β i , i ) if x i is true and a i = 0 or if x i is false and b i = 0. Since datum unit 0 has been transmitted from α 1 to ω 1 , ω 1 possesses all datum units at the end of sequence σ.

In each clause c j , j ∈ {1, 2, . . . , s}, we choose the first true literal.

• Let us suppose that this literal is x i , i ∈ {1, 2, . . . , p}, and that it is the y th occurrence of literal x i in set C. Datum unit j is transferred during contacts (α 2 , l 2y-1 i ), (l 2y-1 i , l 2y i ), (l 2y i , C j ), and (C j , ω 2 ). • Let us now suppose that this literal is xi , i ∈ {1, . . . , p}, and that it is the y th occurrence of literal xi in C. Then datum unit j is transmitted during contacts (α 2 , l2y-1 i ), ( l2y-1 i , l2y i ), ( l2y i , C j ), and finally (C j , ω 2 ). In both cases, these contacts cannot have been used to transmit unit 0 since the contrary would mean that both literals x i and xi are true.

All other transfers can be set to ∅. Each unit j ∈ D has been transmitted from α 2 to ω 2 . Thus the transfer plan is such that ∀i ∈ R, O m i = D.

Polynomial-time cases

In this section, we first show that the data transfer problem can be solved in polynomial time if u = 1. This specific case is also called the one-datum-unit problem. Then we show that the data transfer problem can be polynomially solved if set R = {ω} is a singleton. This specific case is termed the delivery problem, and is to find a valid transfer plan φ minimizing λ ω (φ). Finally we show the case where u and |R| are both constant is also polynomial.

The one-datum-unit problem (u = 1)

In this problem, D = {1} (there is only one datum unit). If there is at least one transfer plan leading to the dissemination of the whole datum, then there is at least one optimal transfer plan where, for each contact σ c ∈ σ, we have

φ(c) = {1} if O c-1 rc = ∅ and O c-1 sc = {1} (if node r c
does not possess the unit, while node s c does). Indeed, there is no advantage to be gained in delaying the dissemination of the only datum unit. Thus it is sufficient to go through the sequence of contacts, and to enforce that every node obtains the datum as soon as possible. This process is summarized in Algorithm 2.1.

In short o[i]

Theorem 2.3

The dissemination problem can be solved in O(max(n, m)) time if u = 1 (if there is only one datum unit).

Chapter 2. Complexity results

Algorithm 2.1 -Solving the one-datum-unit problem

Require: An instance of the one-datum-unit problem ; 1:

2: # only the sources possess the datum unit from the outset. # the recipient node obtains the datum unit if possible.

3: N d ← 0 ; λ(φ) ← ∞ ; 4: for i : 1 → n do 5: o[c] ← O c ; 6: if O c = {1} and i ∈ R then N d ← N d + 1 ;
12:

if o[r c ] = ∅ and o[s c ] = {1} then 13: φ(c) ← {1} ; o[r c ] ← {1} ; 14: if r c ∈ R then N d ← N d + 1 ; 15: 16:
# the transfer is set to ∅ otherwise. # the procedure stops if every recipient possesses the datum. return "This instance is not feasible." ;

The delivery problem (|R| = 1)

Recall that this problem is similar to the dissemination problem, except that only one specified node ω ∈ N needs to obtain all the datum units.

Obviously, the delivery problem can be solved in O(max(n, m)) if u = 1 (with Algorithm 2.1). We will now show that the general case is polynomial as well. To this end, we show that solving the delivery problem is equivalent to solving max(u, m) separate maximum flow problems.

Theorem 2.4

The dissemination problem can be solved in O((nu+m) max(u, m)) time when |R| = 1 (when there is only one recipient).

Polynomial-time reduction

Let us consider an instance of the delivery problem. Let μ i = |{σ c ∈ σ such that r c = i}| denote the number of contacts where node i ∈ N is the receiver (note that even a source node may be the receiver of a contact).

We consider a transportation network G = (V, A, cap), built as follows:

• first we add a source vertex src ∈ V ;

• with each datum unit k ∈ D, we associate a vertex d k ∈ V ;

• for each node i ∈ N , we add a set of vertices {i 0 , . . . , i μ i } ⊂ V ;

• ∀k ∈ D, we add an arc (src, d k ) ∈ A with capacity cap(src, d k ) = 1;

• ∀i ∈ N and ∀k ∈ D -if datum unit k ∈ O i -we add an arc (d k , i 0 ) ∈ A with capacity cap(d k , i 0 ) = 1; • ∀i ∈ N , ∀x ∈ {1, . . . , μ i }, we add (i x-1 , i x ) with cap(i x-1 , i x ) = u;
• for each contact σ c = (i, j) ∈ σ -assuming that node i is the receiver of x contacts before σ c -and that σ c is the y th contact where node j is the receiver -we add an arc (i x , j y ) ∈ A of capacity cap(c x , j y ) = 1;

• finally we add an arc (ω μω , src) ∈ A with cap(ω μω , src) = u.

For example, let us consider the following instance of the delivery problem:

• n = 4 and N = {1, 2, 3, 4}; u = 2 and D = {1, 2};

• O 1 = {1, 2}, O 2 = {2} and O 3 = O 4 = ∅ ; ω = 4, i.e. R = {4};
• m = 5 and σ = [(1, 3), [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Balcioglu | Enumerating Near-Min S-T Cuts[END_REF], [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF], [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Balcioglu | Enumerating Near-Min S-T Cuts[END_REF], [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Balcioglu | Enumerating Near-Min S-T Cuts[END_REF]]. The associated transportation network is depicted in Figure 2.5. The arcs of capacity u model the capacity for each node to store data, whereas the arcs of unitary capacity represent possible transfers (first to initialize the sources, and then to model the contacts).

src d 2 d 1 1 0 2 0 3 0 3 1 3 2 4 0 4 1 4 2 4 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 u u u 1 1 1 u u 1 u 2
It is worth nothing that the maximum flow on arc (ω μω , src) cannot exceed its capacity u. The resulting transportation network contains 1 + u + n + m vertices and u

+ i∈N |O i | + 2m + 1 ≤ (n + 1)u + 2m + 1 arcs.
We show that solving the delivery problem (decision version) is equivalent to searching for a flow of value u in the associated flow network.

Proposition 2.1

Given any instance of the delivery problem, there exists a valid transfer plan such that the recipient node obtains the whole datum if and only if there exists a flow of value u in the associated flow network.

From a flow of value u to a valid transfer plan

Let us consider a flow f : A → D (in the associated flow network) satisfying capacity and conservation constraints, and such that the flow entering vertex src is equal to u. A valid transfer plan φ can be obtained as follows.

First we consider the amount of flow from each vertex d k (k ∈ {1, . . . , u}) to each vertex i 0 (i ∈ {1, 2, . . . , n}). If f (d k , i 0 ) = 1 then i 0 is the vertex that is considered to be the owner of datum unit k. Each datum unit is considered to be owned by at most one vertex, since the flow entering vertex d k cannot exceed 1. From now on, every unit of flow from one vertex to another in the transportation network is considered as a change of owner for a unit.

We consider the contacts in the order of the sequence. For each contact σ c = (i, j) ∈ σ, let (i s , j t ) ∈ A be the corresponding arc in the transportation network -i.e. i s ∈ V and j t ∈ V are the nodes such that i has already been the receiver of s contacts before contact σ c , and such that σ c is the t th (t > 0) contact in which j is the receiver.

• If f (j t-1 , j t ) = p, then j t becomes the owner of p datum units that j t-1 previously owned. Note that flow conservation constraints ensure that j t-1 was the owner of at least p datum units. If j t-1 was the owner of more than p units, the p units whose owner is changing can be chosen indifferently, e.g. the units with the smallest indices.

• If f (i s , j t ) = 1, then j t becomes the owner of one datum unit k that i s previously owned (arbitrarily chosen), and we set φ(c) = {k}.

• Finally, if f (i s , j t ) = 0, then we set φ(c) = ∅.

At the end of this step, note that every datum unit is still considered to be owned by only one vertex. The process is iteratively applied to each contact in sequence σ. Thereafter we look at the amount of flow through (ω μω , src).

If f (ω μω , src) = u, then we can conclude that vertex ω μω is the owner of all the datum units (and thus that the transfer plan is such that node ω obtains all these datum units during the sequence of contacts).

For example, in Figure 2.5 (cf. instance page 29), the flow corresponds to the transfer plan φ such that φ(1) = φ(5) = {1} and φ(2) = φ(4) = {2}.

From a valid transfer plan to a flow of value u Conversely, let us now consider a valid transfer plan φ, solution of the delivery problem. From the sequence of contacts, and from this transfer plan, we can compute the states O c i of each node i ∈ N after the different contacts σ c ∈ σ. Then we can build the flow function f : A → D as follows.

Initially the flow is null -i.e. ∀a ∈ A, f (a) = 0. Subsequently we consider vertex ω µω in the transportation network, and we assume that this vertex is the owner of all datum units. The procedure consists of searching iteratively for the different owners of each datum unit k ∈ D, until a vertex i 0 (i ∈ N ) becomes its owner.

To this end we consider a datum unit k that is initially owned by vertex i s = ω µω . We will assume s > 0 (if this were not the case, the process would terminate immediately, since ω would never be the receiver in a contact and would therefore have to own the whole datum at the outset). Let σ x be the s th contact whose i is the receiver, and thus let O x i be the set of datum units possessed by i after contact σ x .

• If k ∈ O x-1 i
, then vertex i s-1 becomes the new owner of datum unit k, and f (i s-1 , i s ) is incremented by one unit.

• Conversely, if k / ∈ O x-1 i
, then node i has received datum unit k during contact σ x . Let j be the sender in this contact, and let t ∈ {1, . . . , µ j } be the number of contacts occurring before σ c in which node j was the receiver. j t becomes the new owner of k, and we set f (j t , i s ) = 1.

Note that the flow values obtained always respect the capacity constraints of the flow network. Besides -by setting i s = i s-1 or i s = j t-1 according to the case -the process can be repeated until unit k is owned by a vertex i 0 .

At the end of each iteration there is only one owner of datum unit k, and the change of owner results in an increase in the flow on the arc linking the new owner to the previous owner (ensuring, this way, flow conservation). This operation is repeated for all of the units. At the end of this process we therefore know which vertex i 0 is the owner of each datum unit k, and we set f (d k , i 0 ) = 1 accordingly. For each In practice the flow network can be simplified by iteratively removing the vertices that have no successor or no predecessor, and through which the flow can only be null. Moreover the vertices representing the states of node ω can be merged into a single node (the resulting vertex ω * is the destination of all arcs entering a vertex ω x , and any arc going out of such a vertex is removed, apart from the one to src) -cf.

d k ∈ D, we set f (src, d k ) = 1. Finally we set f (ω µω , src) = u. src d 2 d 1 1 0 2 0 3 1 3 2 4 *

Optimizing the delivery length λ ω (φ)

Node ω needs at least u -|O ω | contacts to receive the whole datum. Thus, one way of finding a valid transfer plan φ that minimizes the delivery length λ ω (φ) is to build the flow network associated with the shortest subsequence of σ involving u-|O ω | contacts whose node ω is the receiver. If f (ω μω , src) = u, then the transfer plan φ associated with f is optimal. Otherwise, we complete the current subsequence of σ in such a way that it involves uf (ω μω , src) more contacts with node ω. So a new maximum flow can be computed (note that in practice the previous flow can be easily transformed to obtain a new starting flow). The procedure is repeated until f (ω μω , src) = u, or until the current sequence equals σ. If the procedure stops while f (ω μω , src) < u, then it means that the instance is infeasible. Using Ford-Fulkerson algorithm [START_REF] Ford | Maximal flow through a network[END_REF] or Edmonds and Karp algorithm [START_REF] Edmonds | Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems[END_REF] to compute the maximum flow of each transportation network that is considered, the overall procedure can run in O((nu + m) max(u, m)) time, given that each augmenting path can be found in O(|A|) time, and that we need to find at most max(u, m) such paths.

Upper bounded parameters

In this section we look at an instance of the dissemination problem in which both u and |R| are assumed to be upper bounded by given positive constant numbers

K 1 and K 2 , with K 1 ≥ u ≥ 2 and K 2 ≥ |R| ≥ 2.
We might be tempted to use the same kind of technique as in the previous section, but as |R| ≥ 2 this is no longer possible. In the case where |R| = 1, this worked because exactly u units were flowing through the transportation network, and each unit of flow was interpreted as the ownership of a datum unit. Note that the datum units did not need to be identified. Now, however, the datum units might need to be duplicated (in order to be transmitted to several nodes), which is prohibited by conservation constraints. In addition, taking one unit of flow per datum unit per recipient is not possible, because the units of flow are not identified (this could lead to transfer plans in which a recipient node gets the same datum unit twice).

Nonetheless, by taking one unit of flow per datum unit and per recipient, we can build Algorithm 2.2.

Theorem 2.5

The dissemination problem can be solved in polynomial time when the number of units and the number of recipients are upper bounded.

Throughout the procedure, a set of states States is managed, and exactly |R| copies of each datum unit are considered (because there is never a need to duplicate a unit more than |R| times). Every state S ∈ States is defined by a bidimensional array S.o, where S.o[k][z] designates the node owning the z th (z ∈ {1, . . . , |R|}) copy of unit k ∈ D, and by the transfer plan S.φ from which this state has arisen.

The procedure is started with only one state S (cf. lines 2-7) in which an imaginary node 0 owns all copies of all datum units, and where S.φ(c) = ∅, ∀c ∈ {1, 2, . . . , m}. The ownership of each copy z of each datum unit is then # the z th copy of datum unit k is distributed.

13:

States ← ∅ ; # the ownership of the z th copy of datum unit k distributed (cf. lines 9-19) among source nodes i with k ∈ O i . At the end of this phase, a node i can own several copies of the same datum unit (so that this datum unit can be transferred to several other nodes).

for all i ∈ N | k ∈ O i do 16: S ← copy(S) ; S .o[k][z] ← i ;
28: # is transferred to r c if possible -i.e. if the current 29: # owner of this copy is s c . 30: if S.o[k][z] = s c then 31: S ← copy(S) ; S .o[k][z] ← r c ; S .φ(c
Next, the ownership of datum unit copies is transferred through contacts (cf. lines [START_REF] Ferreira | On models and algorithms for dynamic communication networks: The case for evolving graphs[END_REF][START_REF] Ferreira | Building a reference combinatorial model for MANETs[END_REF][START_REF] Ferreira | Complexity of Minimum Spanning Tree in Evolving Graphs and the Minimum-Energy Broadcast Routing Problem[END_REF][START_REF] Ford | Maximal flow through a network[END_REF][START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF][START_REF] Handorean | Accommodating Transient Connectivity in Ad Hoc and Mobile Settings[END_REF][START_REF] Hay | Optimal routing and scheduling for deterministic delay tolerant networks[END_REF][START_REF]Instances of the dissemination problem[END_REF][START_REF] Jain | Routing in a delay tolerant network[END_REF][START_REF] Jamshidi | System of Systems Engineering: Principles and Applications[END_REF][START_REF] Jouglet | Dominance rules in combinatorial optimization problems[END_REF][START_REF] Juang | Energy-efficient computing for wildlife tracking[END_REF][START_REF] Lebrun | Bluetooth content distribution stations on public transit[END_REF][START_REF] Lindgren | Probabilistic Routing in Intermittently Connected Networks[END_REF][START_REF] Merugu | Routing in Space and Time in Networks with Predictable Mobility[END_REF][START_REF] Mongiovi | Efficient multicasting for delay tolerant networks using graph indexing[END_REF] We here assume that S is not considered if there exists another state with exactly the same ownership matrix (although not necessarily the same transfer plan). Note that instruction isSolution(S ) checks whether all recipient have received the whole datum (this can be done in polynomial time). If this is the case, the algorithm immediately stops and returns the computed transfer plan.

Time-complexity -Since the ownership of the z th copy, z ∈ {1, . . . , |R|}, of datum unit k ∈ D = {1, 2, . . . , u} can take n + 1 values, there are at most (n + 1) |R|u possible states. Therefore the overall algorithm runs in O(mn |R|u ) time -which is polynomial in m and n, since |R| and u are upper bounded by two positive constant numbers K 1 and K 2 (of course, this algorithm can only be used for small values of |R| and u).

Additional results

In this section, we discuss complementary results arising from what has been said so far. In particular, it will be shown that knowing whether there exist k mutually arc-disjoint branchings in an evolving graph -or whether there exist k mutually arc-disjoint Steiner trees in a directed graph without circuit -are strongly NP-Complete

Arc-disjoint branchings in an evolving graph

To address this problem, we first remind its statement and classical results for the more conventional case of directed graphs. Thereafter we show that these results no longer hold for evolving graphs, and establish that the problem is actually NP-Complete in this case (we reduce it to Dt).

Usual graphs

Let G = (V, A) be a directed multigraph.

• Given t ∈ V , a branching B rooted at t is a subgraph of G such that,
for every vertex v ∈ V , there is exactly one path in B from t to v.

• Given X ⊂ V , δ G (X) denotes the set of arcs (i, j) ∈ A such that i ∈ X and j ∈ V \X -i.e. the arcs "going out" of X. Such a set is commonly termed a cut in graph theory.

Theorem 2.6 -Edmonds 1972 [17]

There exist k mutually arc-disjoint branchings rooted at t if and only if for any

X ⊂ V such that t ∈ X and X = V , we have |δ G (X)| ≥ k. Let then c G (t) = min {X|t∈X,X =V } |δ G (X)|
be the maximum number of arc-disjoint branchings rooted at t in G. In fact, c G (t) can be regarded as the "outwards connectivity" of t -i.e. the minimum number of arcs that would need to be removed to make at least one vertex unreachable from t [START_REF] Shiloach | Edge-disjoint branching in directed multigraphs[END_REF]. c G (t) is actually the maximum number of mutually arc-disjoint paths from t to any other vertex in V . This well-known property is used by a number of polynomial algorithms that have been developed for finding k mutually arc-disjoint branchings in a multigraph, such as Shiloach's [START_REF] Shiloach | Edge-disjoint branching in directed multigraphs[END_REF] in

O(k 2 |V | × (|V | + |A|)).

Evolving graphs

As mentioned in Chapter 1, an evolving graph is a theoretical graph model, first introduced by Ferreira [START_REF] Ferreira | On models and algorithms for dynamic communication networks: The case for evolving graphs[END_REF], and designed to capture main characteristics of intermittently connected networks. It is a directed multigraph G(V, A, τ ) whose vertices represent nodes, and whose arcs represent links between these nodes. τ : A → I (I being the set of intervals which can be built over a given time horizon) indicates the interval on which links can be used. Thus an arc can represent a contact between two nodes. In its simplest version, τ is such that τ : A → N -i.e. the interval of time during which every link is active is reduced to a singleton. In this case, a path [a 0 , a 1 , a 2 , ..., a z ] (a j ∈ A) is such that ∀j ∈ {0, . . . , z -1}, we have τ (a j ) ≤ τ (a j+1 ). From now on such a path is termed a journey.

Surprisingly, unlike usual graphs, knowing whether there exists a strong connected component of a given size in an evolving graph (when considering journeys instead of usual paths) is NP-Complete [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF]. However, the minimum spanning trees (rooted at each vertex) in a strongly connected evolving graph can be polynomially computed. Some other algorithms in the literature can be polynomially generalized in evolving graphs. These include the search for foremost journeys (i.e. the journeys with the earliest arrival dates), shortest journeys (using the smallest number of arcs) and fastest journeys (with the smallest difference between departure and arrival times) from a source vertex to all other vertices [START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF].

We now turn to the problem of knowing whether there exist k mutually arc-disjoint branchings in an evolving graph. To our knowledge, this problem has never been investigated. Note first that Theorem 2.6 no longer holds for evolving graphs. This can be shown with the following counter-example (cf. Figure 2.7):

• G = (V, A, τ ); V = {t, a, b, c, d, e, f }; A = {a 1 , a 2 , . . . , a 12 }; • a 1 = (t, a), a 2 = (a, c), a 3 = (a, e), a 4 = (t, b), a 5 = (b, c), a 6 = (c, d), a 7 = (d, e), a 8 = (d, f ), a 9 = (b, f ), a 10 = (t, a), a 11 = (t, b), a 12 = (c, d); • τ : V → N; ∀i ∈ {1, 2, . . . , 12}, τ (a i ) = i;
Proof. We consider root t ∈ V . There are at least two arc-disjoint journeys from t to any other vertex v ∈ V \{t}, i.e. c G (t) ≥ 2. Now let us show there does not exist two mutually arc-disjoint branchings rooted at t.

First, let us assume there are two arc-disjoint branchings B 1 and B 2 rooted at t. Each branching has exactly 6 arcs. Thus, {B In fact knowing whether there exist k mutually arc-disjoint branchings in an evolving graph is NP-Complete. To prove this, let us consider the decision version of this problem, referred to below as Adbeg.

Problem 2.3 -arc-disjoint branchings in evolving graphs

Given an evolving graph

G = (V, A, τ ) • a root t ∈ V • an integer k with k ≤ |A|/(|V | -1) -are there k mutually arc-disjoint branchings rooted at t in G ? Theorem 2.7 Adbeg (Problem 2.3) is NP-Complete.

Polynomial-time reduction

Let us show that Dt is reducible to Adbeg in polynomial time. To this end, we consider an instance of Dt (cf. Problem 2.1, page 15), and we build the following instance of Adbeg.

Vertices -With each node i ∈ {1, . . . , n} in Dt, we associate a vertex i ∈ V in Adbeg. Then, with each datum unit k ∈ D in Dt, we associate a vertex

d k ∈ V in Adbeg. Finally, we add a vertex t ∈ V . Arcs -For each datum unit k ∈ D of Dt, we add one arc (t, d k ) ∈ A with τ (t, d k ) = 0 in Adbeg. Then, for each node i ∈ {1, 2, . . . , n} and each datum unit k ∈ D in Dt -iif. k ∈ O i -we add an arc (d k , i) ∈ A with τ (d k , i) = 0 in Adbeg. With each contact σ c ∈ σ in Dt, we associate an arc (s c , r c ) ∈ A with τ (s c , r c ) = c in Adbeg. Finally, for each node i ∈ R = N \R, we add u arcs (t, i) with τ (t, i) = m + 1.
An example is given in Figure 2.8. The Dt instance corresponds to the one of Figure 1.1 (page 11), with the addition of a non-recipient node.

Proof of equivalence

Suppose that there exist a set {B 1 , B 2 , . . . , B u } of u mutually arc-disjoint branchings in G = (V, A). The only way to reach a vertex i ∈ R from t is to first use an arc (t, d k ) with τ (t, d k ) = 0, and then to follow some arcs a j with 1 ≤ τ (a j ) ≤ m. Each branching is then associated with exactly one arc (t, d k ) (there are only u such arcs). Let B k denote the branching associated with arc (t, d k ).

We can build a valid transfer plan φ for Dt as follows.

• We initially set φ(c) = ∅ for c ∈ {1, 2, . . . , m}.

• Next, for each branching B k , k ∈ {1, 2, . . . , u}, and for each arc a ∈ B k with 1 ≤ τ (a) ≤ m, we set φ(τ (a)) = {k}. Note that since the different branchings are mutually arc-disjoint, and since there is exactly one arc a ∈ A associated with a contact in σ, we never try to set several values to the same transfer φ(c).

In each branching B k , and for each i ∈ R, there is a journey [a 0 , a 2 , . . . , a x ] such that a 0 = (t, d k ), a 1 = (d k , z) with k ∈ O z , and for all j ∈ {3, 4, . . . , x}, 1 ≤ τ (a j ) ≤ m and τ (a j-1 ) < τ (a j ). Consequently it corresponds to a list of contacts which enable datum unit k to be transmitted from source node z to node i. Thus, at the end of σ, all i ∈ R are such that O m i = D.

(a) an instance of the data transfer problem [START_REF] Bertsimas | The Price of Robustness[END_REF], (6, 1), [START_REF] Bertsimas | The Price of Robustness[END_REF][START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF], [START_REF] Akyildiz | InterPlaNetary Internet: state-of-the-art and research challenges[END_REF][START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF], [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF], . . . , [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF][START_REF] Bertsimas | The Price of Robustness[END_REF], ( 4

⎧ ⎨ ⎩ N = {1, 2, . . . , 7}; R = N \{7}; D = {1, 2}; O 1 = {1, 2}; O 2 = {1}; O 3 = O 4 = O 5 = O 6 = O 7 = ∅ ; σ = [(1,
B k = (V, A B k = {(t, d k )}). Next, for each node i ∈ N such that k ∈ O i , we add arc (d k , i) in A B k . Then, for each c ∈ {x | φ(x) = k}, we add arc (s c , r c ) in A B k .
Note that for any list of transfers enabling datum unit k to be transmitted from a node z ∈ N with k ∈ O z to node i ∈ N , there is a corresponding journey from t to i in B k . In particular, it holds for any node i ∈ R. Moreover, the nodes i ∈ V \R for which there is no path from t to i cannot be connected to another node in B k . For such nodes, we add an arc (t, i) ∈ A B k with τ (t, i) = m + 1. This is always possible since there exist u arcs of this kind. Thus subgraph B k is a branching. It must finally be noted that B 1 , B 2 , . . . , B k are mutually arc-disjoint by construction.

Arc-disjoint Steiner trees in a digraph

The problem of packing arc capacitated directed Steiner trees is a well known problem [START_REF] Cheriyan | Hardness and approximation results for packing steiner trees[END_REF]. It is stated as follows.

Problem 2.4 -Steiner tree packing problem

Let us consider a directed graph G = (V, A, cap) with positive capacities (cap : A → N + ), a set T ⊆ V of terminals, and a root t ∈ T . A directed Steiner tree rooted at t is a directed subgraph of G (a tree) that contains a path from t to every terminal v ∈ T . The Steiner tree packing problem is to find the maximum number of Steiner trees rooted at t, such that for every arc a ∈ A, the total number of Steiner trees containing a is at most cap(a). [START_REF] Cheriyan | Hardness and approximation results for packing steiner trees[END_REF] established that the problem of knowing whether there are two arc-disjoint Steiner trees in a graph with unit capacities and only three terminals is NP-Complete. The proof is based on the following reduction -given two pairs of vertices (x 1 , y 1 ) and (x 2 , y 2 ) ∈ V 2 , are there two arc-disjoint paths, one from x 1 to y 1 , and the other from x 2 to y 2 ?

Cheriyan and Salavatipour

In fact, it can be shown that this problem is NP-Complete even if there are three terminals and the graph is without circuit. Indeed, as discussed in Section 2.1.2, the data transfer problem is NP-Complete in the strong sense, even if |R| = 2 (i.e. Dt2r).

In addition, with an instance of Dt2r, we can associate a directed graph G = (V, A, cap) similar to the one we built for the delivery problem (Section 2.2.2 and Figure 2.5).

• first we add a source vertex src ∈ V ;

• with each datum unit k ∈ D, we associate a vertex d k ∈ V ;

• for each node i ∈ N , we add a set of vertices {i 0 , . . . , i µ i } ⊂ V ;

• ∀k ∈ D, we add an arc (src,

d k ) ∈ A with capacity cap(src, d k ) = 1; • ∀i ∈ N and ∀k ∈ D -if datum unit k ∈ O i -we add an arc (d k , i 0 ) ∈ A with capacity cap(d k , i 0 ) = 1; • ∀i ∈ N , ∀x ∈ {1, . . . , µ i }, we add (i x-1 , i x ) with cap(i x-1 , i x ) = u;
• for each contact σ c = (i, j) ∈ σ -assuming that node i is the receiver of x contacts before σ c -and that σ c is the y th contact where node j is the receiver -we add an arc (i x , j y ) ∈ A of capacity cap(c x , j y ) = 1;

• note that we no longer consider the "return" arc (ω µω , src).

Thus, knowing whether there is a valid transfer plan O m i = D (∀i ∈ R) with |R| = 2 becomes equivalent to knowing whether there exist two arc-disjoint Steiner trees rooted at src with terminals T = {src}∪R in the corresponding transportation network. Here it should be noted that this network is always without circuit (by construction).

Conclusion

In this chapter, we highlighted several polynomial cases for the dissemination problem, i.e. the latter is solvable in polynomial time when there is only one datum unit, or only one recipient, or when both the number of datum units and the number of recipients are upper bounded by a given constant.

However, we also proved the general case is strongly NP-Hard. Therefore, non-polynomial algorithms can be investigated in order to solve the problem in the general case, like branch-and-cut/branch-and-bound procedures.

Dominance rules, preprocessings, and integer linear programming

N ow that the NP-Completeness of the dissemination problem has been established, it seems interesting to propose non-polynomial algorithms (such as branchand-bound procedures) to solve it. With this aim in view, in this chapter we are going to propose a number of dominance rules for this problem. These yield conditions on which a subset of the search space considered to solve the problem can be ignored (cf. Section 3.1). Thereafter, we will propose algorithms which make use of these rules to deduce additional constraints, and this way, eliminate dominated solutions -i.e. solutions which can be ignored according to the dominance rules. The algorithms rely on a graph model, called the transfer graph (cf. Section 3.2), aiming at capturing knowledge about admissible transfer plans. Finally, all of this will be tested and incorporated into preprocessing procedures (cf. Section 3.3). These will aim to strengthen an integer linear program modelling the problem (cf. Section 3.4).

Contents

Dominance rules

The solving techniques discussed in the present thesis are based on a number of dominance rules (see [START_REF] Jouglet | Dominance rules in combinatorial optimization problems[END_REF] for a comprehensive paper on that topic) which dramatically improve performances of any enumeration algorithm. All these dominance rules will be defined in this first section. These results will form the basis for additional constraints and deduction algorithms to be presented in the following sections.

Firstly, it will be remarked that more than one transmission of the same unit to the same receiving node might occur during the same valid transfer plan. From an operational point of view, resources are wasted, while from a computational point of view, taking such solutions into account significantly enlarges the search space we consider -which makes it desirable to disallow redundant transfers.

Hence the definitions below and the ensuing dominance rule.

Definition 3.1

The transfer occurring at time c ∈ {0, 1, . . . , m} in transfer plan φ is said to be null if and only if no datum unit is transmitted during contact σ c , i.e. φ(c) = ∅.

Definition 3.2

The transfer occurring at time c ∈ {0, 1, . . . , m} in transfer plan φ is said to be improving if and only if the receiving node r c obtains a new datum unit during contact σ c , i.e.

|O c-1 rc | < |O c rc |.

Definition 3.3 -minimal transfer plan

A transfer plan φ is said to be minimal if and only if all its transfers are either null or improving, i.e. no node receives the same datum unit more than once.

Proposition 3.1

The set of minimal transfer plans is dominant.

Proof. Let φ be a valid non-minimal transfer plan. Therefore there exists at least one transfer which is neither null nor improving, i.e. ∃c ∈ {1, 2, . . . , m} such that φ(c) = {k} ⊆ O c-1 rc . The transfer plan φ -obtained by copying φ and by setting φ (c) = ∅ -has the same dissemination length than φ, that is λ(φ ) = λ(φ). This process is to be repeated as long as the new transfer plan is not minimal.

The idea behind minimal transfer plans may be further reinforced by only considering the minimal transfer plans during which any non-recipient node forwards any datum unit it receives at least once. From an operational point of view, this means avoiding transferring data to a non-recipient node which is not able to contribute to a better dissemination of the datum.

Formally, it gives the following dominance rule.

Definition 3.4 -strictly-minimal transfer plan

A transfer plan φ is said to be strictly-minimal if and only if it is minimal and every non-recipient node forwards at least once all the datum units it receives.

Proposition 3.2

The set of strictly-minimal transfer plans is dominant. The process is to be repeated as long as the transfer plan is not strictly-minimal.

Unfortunately, in practice, this dominance rule is found to be less efficient than the minimality rule introduced above. Our numerical tests even showed that it is beneficial to schedule improving transfers as possible, rather than trying to reduce their number at a high computational cost.

Therefore we propose the following dominance rule.

Definition 3.5

A transfer plan φ is said to be active if and only if there exists no contact σ c ∈ σ in which a datum unit k ∈ D is transmitted from s c to r c , where the same transmission could have been done earlier making better use of a non-improving transfer φ(c ). Formally,

∀c ∈ {2, 3, . . . , m} such that |O c-1 rc | < |O c rc |, ∃c ∈ {1, . . . , c -1} with r c = r c , φ(c) ⊆ O c -1 s c and O c -1 r c = O c r c Proposition 3.3
The set of active transfer plans is dominant.

Proof. Let φ be a non-active transfer plan. There exist c, c ∈ {1, 2, . . . , m}

and k ∈ D such that c < c, r c = r c , k ∈ O c -1 s c , k / ∈ O c -1 r c , O c -1 r c = O c r c
, and φ (c) = {k}. Let us consider φ , the transfer plan obtained first by copying φ and then by setting φ (c ) = {k}. The dissemination length of transfer plan φ is better than or equal to the dissemination length of φ, i.e. λ(φ ) ≤ λ(φ). The process is repeated until φ is active. φ (c) can also be set to ∅ (at each iteration) if minimality properties have to be maintained.

In an active transfer plan, an improving transfer might still be ignored in favour of another non-improving or null transfer. In particular, there might be c ∈ {1, . . . , m -1} and k

∈ D with k ∈ O c -1 s c , k / ∈ O c r c , and O c -1 r c = O c r c , if r c / ∈ R and ∀c ∈ {c , . . . , m} | r c = r c , φ(c) = {k}.
The dominance rule below strengthens the idea of an active transfer plan by ensuring that a fruitless transfer can never be preferred to an improving transfer.

Definition 3.6

A transfer plan φ is said to be strictly-active if and only if all transfers are improving when possible, i.e. ∀c ∈ {1, 2, . . . , m},

if ∃k ∈ D such that k ∈ O c-1 sc and k / ∈ O c-1 rc , then |O c-1 rc | < |O c rc |.

Proposition 3.4

The set of strictly-active transfer plans is dominant.

Proof. Let φ be a non-strictly-active transfer plan, i.e. ∃σ c ∈ σ and ∃k ∈ D

such that k ∈ O c-1 sc , k / ∈ O c-1 rc , and O c-1 rc = O c rc .
Then, let φ be the transfer plan obtained by copying φ, and by setting φ (c) = {k}. The dissemination length of φ is necessarily better than or equal to that of φ, i.e. λ(φ ) ≤ λ(φ). The process is repeated until φ is strictly-active.

Remark 3.1

A strictly-active transfer plan is active (by definition). Moreover we can show that the sets of minimal-active and minimal-strictly-active transfer plans are both dominant (by combining the above proofs).

The remainder of the chapter will focus on algorithms designed to identify the non-minimal or the non-strictly-active transfer plans. Beforehand we will illustrate how these dominance rules can help us to solve the problem.

To this end, we consider the instance depicted in Figure 1.1 (on page 11):

• dominance-rule-based deductions -First node 1 initially possesses all units, whereas node 6 starts with an empty buffer, i.e. O 1 = {1, 2} and O 6 = ∅. Thus, φ(1) = ∅ holds in every strictly-active transfer plan, i.e. φ(1) = {1} ∨ φ(1) = {2}. It also means that node 6 possesses either datum unit 1 or datum unit 2 afterwards. Since node 1 possesses these two units from the start, then φ( 2) is null in all minimal strictly-active transfer plans. Therefore, in practice, contact σ 2 can be removed from the instance before any computation is done. With the same approach, it can be shown that φ(3) = φ(1) and φ(8) = {2} hold in any minimal strictly-active transfer plan. Figure 3.1 illustrates the results that can be collected by applying these methods over each contact (in the order of the sequence). Five contacts are seen to have been set.

• delivery-requirement-based deductions -A feasible transfer plan has still to be found. It needs to be decided how to continue the process, e.g. by deciding φ(1) = {1} or, conversely, φ(1) = {2}. Let us assume that φ(1) = {2}. There exists only one possibility for delivering datum unit 1 to nodes 6 and 5, with φ(4) = φ(5) = φ(7) = φ(10) = {1}. Next, to transfer datum unit 2 to node 4, the only remaining possibility is to set φ(6) = {2}, cf. Figure 1.1. It should be remarked that a symmetric solution can be found with φ(1) = {1}. These transfer plans are both minimal, strictly-active and optimal.

In fact, the methodology described above is applied within any branching algorithm, e.g. a branch-and-bound or a branch-and-cut algorithm. Decisions and backtracks constitute the branching stage (i.e. generation and selection of nodes), with local deductions performed at every node of the search tree to filter dominated solutions, e.g. through constraint propagation or cuts. [START_REF] Bertsimas | The Price of Robustness[END_REF] 5

1

{1, 2} 3 2 {1} 4 φ ( 8 ) = { 2 } φ(1)
φ( 4) φ( 10) The following two sections describe how these deduction techniques have been implemented. Thereafter, Section 3.4 focuses on a particular branching procedure (based on integer-linear programming) that we proposed to solve the dissemination problem.

9 φ(5) = φ(4) φ(7) = φ(4) 12 13 φ(6) φ(2) = ∅ φ(11) φ(3) = φ(1) φ(1) ∈ {{1}, {2}} • φ(2) = ∅ • φ(3) = φ(1) • φ(4) ∈ {{1}, {2}} φ(5) ∈ {φ(4), ∅} • φ(6) ∈ {φ(1), φ(4)} • φ(7) ∈ {φ(4), ∅} • φ(8) = {2} φ(9) = ∅ • φ(10) = {{1}, {2}} • φ(11) ∈ {φ(1), φ(10)} • φ(12) = ∅ • φ(13) = ∅

Transfer graph

In this section, we propose a graph model -the transfer graph -which enables a set of valid transfer plans to be represented, i.e. a subset of the search space associated with the dissemination problem. It is the data structure that forms the basis for some deduction algorithms that will be subsequently proposed (Section 3.3). These procedures update the transfer graph so that the search space is dynamically reduced. These techniques will be applied to pre-process the instances (to reduce their size), and within an integer-linear-programming framework, i.e. within a branch-and-cut procedure (cf. Section 3.4).

About the transfer graph

First, let us recall that each state O t i ⊆ D with i ∈ N and t ∈ {0, 1, . . . , m} contains the subset of units possessed by node i after the first t contacts of the sequence. Let us also recall that a transfer plan is valid if nodes transmit only datum units that they have possessed from the outset, or that they have obtained as a result of previous transfers. Hence the following assertion:

∀c ∈ {1, 2, . . . , m}, O c-1 sc = O sc ∪ ⎛ ⎜ ⎝ t∈{1,...,c-1} rt=sc φ(t) ⎞ ⎟ ⎠
the units obtained as a result of former transfers

From now on we will be looking at a graph -the transfer graph -designed to take account of dependencies between transfers. It is defined as follows.

Definition 3.7 -transfer graph

Let us consider an instance of the dissemination problem. The associated transfer graph is a directed acyclic graph

G φ = (V, A) with V = V D ∪ V T , A = A 1 ∪ • • • ∪ A m ⊆ V T × V
, where V and A are built as follows: [START_REF] Alonso | A Linear Programming Formulation of Flows over Time with Piecewise Constant Capacity and Transit Times[END_REF][START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF], [START_REF] Altman | Decentralized Stochastic Control of Delay Tolerant Networks[END_REF][START_REF] Balcioglu | Enumerating Near-Min S-T Cuts[END_REF], (4, 1)] k ∈ O sc . Similarly, an arc between two vertices v φ(c) and v φ(t) ∈ V T models the possibility that node s c will forward during σ c a unit that it has received during σ t , as t < c and r t = s c .

1. V D = { v {k} | k ∈ D} -where vertex v {k} is associated with datum unit k; 2. V T = { v φ(c) | c ∈ {1, 2, . . . , m}} -where vertex v φ(c) is associated with transfer φ(c); 3. ∀c ∈ {1, 2, . . . , m}, A c = {( v φ(c), v {k}) | k ∈ O sc } corresponds to the units initially possessed by sc ∪ {( v φ(c), v φ(t)) | t ∈ {1, . . . , c
⎨ ⎩ N = {1, 2, 3, 4}; R = {1}; D = {1, 2, 3}; O 1 = {1, 2}; O 2 = {2, 3}; O 3 = ∅ ; O 4 = {3}; σ = [(1, 3),
(b) its evolving graph 1 {1, 2} 2 {2, 3} 3 4 {3} 1 2 3 4 (c) the corresponding transfer graph v {1} v {2} v {3} v φ(1) φ(1) = ∅ v φ(2) v φ(3) v φ(4) φ ( 3 ) = φ ( 2 ) φ(4) = φ(3) φ ( 2 ) = { 3 } V D V T

Remark 3.2

The transfer graph contains no circuits, and is polynomial in size of the instance with which it is associated (there are exactly u + m vertices and O(mu + m 2 ) arcs).

Remark 3.3

The vertices in V D are termed unit vertices, and those in V T are termed transfer vertices. As we shall see below, the distinction between the unit vertices and the transfer vertices is rarely required. We frequently need to refer to the unit φ(c) that is transmitted during a contact σ c , without knowing precisely which unit k ∈ D it corresponds to, or even whether anything has really been transmitted. To clarify our notations, such an element is termed a transfer value. While a vertex v {k} ∈ V D represents a datum unit and a vertex v φ(c) ∈ V T represents a transfer, we will use the notation v z ∈ V to refer to any kind of vertex.

These definitions are illustrated in Figure 3.2. The set of unit vertices is

V D = { v {1}, v {2}, v {3}}, and the set of transfer vertices is V T = { v φ(1), v φ(2), v φ(3), v φ(4)}. The set of transfer values is then {{1}, {2}, {3}, φ(1), φ(2), φ(3), φ(4)}
The arcs going out of vertex v φ( 4) are ( v φ(4), v {3}) (because s 4 has possessed unit 3 from the outset) and ( v φ(4), v φ( 3)) (because contact σ 3 occurs before contact σ 4 and the receiver r 3 of that contact is s 4 ).

Transfer graph and subsets of transfer plans

By construction, the set A c of arcs going out of each vertex v φ(c) ∈ V T defines the set of all values that transfer φ(c) can take in a valid transfer plan. Thus, a path Thus a transfer plan can equally be defined as a subgraph of the transfer graph made up of u vertex-disjoint anti-branchings that are each rooted on a different unit vertex. It corresponds to a spanning subgraph of the transfer graph containing at most one arc going out of each vertex. This constraint originates from the fact that at most one unit can be transmitted during each contact. Therefore selecting an arc ( v φ(c), v {k}) is interpreted as φ(c) = {k}, while selecting an arc ( v φ(c 2 ), v φ(c 1 )) ensures that the unit transferred during contact σ c 1 is transmitted during contact σ c 2 , that is φ(c 1 ) = φ(c 2 ). In short, in this subgraph, transfer φ(c) is either considered to be null if no arc out of vertex v φ(c) has been selected, or equal to {k} if vertices v φ(c) and v {k} are linked by a path. For example, in Figure 3.2 the bolded arcs define a way to transmit datum unit 3 to node 1. Moreover, the anti-branchings associated with vertices v {1} and v {2} contain no arcs, because these datum units are never transmitted.

[ v φ(c p ), . . . , v φ(c 2 ), v φ(c 1 ), v {k}] (of p + 1 arcs) from a transfer vertex v φ(c p ) ∈ V T to a unit vertex v {k} ∈ V D

Remark 3.4

Such a subgraph does not really need to be the union of anti-branchings. It prevents situations where a subgraph includes an arc ( v φ(c 2 ), v φ(c 1 )), but does not include an arc going out of vertex v φ(c 1 ) (the path starting from v φ(c 2 ) does not end on a unit vertex). The meaning of this paththat is φ(c 2 ) = φ(c 1 ) = ∅ -can already be expressed by not selecting arc ( v φ(c 2 ), v φ(c 1 )) at all. Taking such sets into account would therefore not enhance the expressiveness of the transfer graph, but would dramatically increase the number of subsets to be explored.

Remark 3.5

In Figure 3.2, it is worth nothing that the same transfer plan is obtained by selecting arc ( v φ(4), v {3}) rather than arc ( v φ(4), v φ(3)) ∈ A. This is because the transfer plan represented by these subgraphs is not minimal (cf. Definition 3.3). Node 4 receives unit 3 during contact σ 3 even though it has possessed this unit from the outset. Therefore, during contact σ 4 , node 4 can send either the unit it has possessed from the outset, or the new copy it has just received. Fortunately, a minimal transfer plan has a unique corresponding subgraph, and consequently we never address this case in practice.

To represent a particular subset of transfer plans, we need to be able to arbitrarily disallow certain arcs or, alternatively, stipulate that certain arcs must be used. To this end we introduce function χ A : A → P({true, false}), whose role is to indicate which arcs are allowed to be selected when a set of u anti-branchings (a transfer plan) is constructed. So,

∀( v φ(c), v z) ∈ A, -χ A ( v φ(c), v z) = {true} means that arc ( v φ(c), v z
) must be selected and that node s c must transmit transfer value z during contact σ c ;

(a) the transfer graph and some of its properties -χ A ( v φ(c), v z) = {false} means that arc ( v φ(c), v z) cannot be selected and that s c must not transmit transfer value z during contact σ c ; -χ A ( v φ(c), v z) = {true, false} means that no decision has been taken yet, i.e. there is no additional constraint upon this transfer.

v {1} v {2} v {3} v φ(1) χ D ( v φ(1), 1) = 0 v φ(2) v φ(3) v φ(4) { t r u e } χ A ( v φ(4), v φ(3)) = {true, false} { f a l s e } { t r u e } (b) additional vertex properties -χ φ ( v {3}) = {{3}} -χ D ( v {1}, 3) = ∞ -χ φ ( v φ(1)) = {∅} -χ D ( v {2}, 1) = 0 -χ φ ( v φ(2)) = {{2}} -χ D ( v {3}, 3) = 2 -χ φ ( v φ(4)) = {∅, {3}} -χ D ( v {3}, 3) = ∞ (c) the

two transfer plans represented by this transfer graph

φ 1 : ⎧ ⎨ ⎩ φ 1 (1) = ∅ φ 1 (3) = φ 1 (2) = {3} φ 1 (4) = ∅ φ 2 : ⎧ ⎨ ⎩ φ 2 (1) = ∅ φ 2 (3) = φ 2 (2) = {3} φ 2 (4) = φ 2 (3) = {3}
As shown in Figure 3.3, this function can represent various constraints.

• For example, χ A ( v φ(3), v φ(2)) = {true} expresses φ(3) = φ(2). • whereas χ A ( v φ(1), v {1}) = {false} ∧ χ A ( v φ(1), v {2}) = {false} force transfer φ(1) to be null, i.e. φ(1) = ∅.
Below, in the light of Remark 3.4, a transfer φ(c) (c ∈ {1, 2, . . . , m}) will be considered as null if and only if all arcs a ∈ A leaving or entering v φ(c) ∈ V T are such that χ A (a) = {false}.

Additional graph properties and complex subsets of transfer plans

The transfer graph, or more specifically function χ A , represents a set of valid transfer plans. If all arcs a ∈ A are such that χ A (a) = {true, false}, that is the whole transfer graph is retained, then all valid solutions are represented.

On the other hand, if χ A includes constraints, e.g. some arcs cannot or must be selected, then some transfer plans can no longer be built, and in this case only a subset of transfer plans is represented.

Nevertheless, it remains impossible to represent more complex subsets of transfer plans, e.g. the transfer plans such that φ(3) = {2} (since there is no arc between vertices v φ(3) and v {2}), or the set of transfer plans such that a given node receives a given datum unit between two given dates (since time windows are not represented in the graph).

However, these sets of transfer plans are all defined by sets of constraints which can easily be represented with the additional properties we introduce below:

• χ φ : V → P(T φ ) (recalling that T φ = {∅, {1}, . . . , {u}}) : this property specifies the domain of every transfer value -that is the set of values that transfer values are allowed to have, e.g. χ φ ( v φ(c)) = {∅, {1}, {2}} indicates that transfer φ(c) must either be null, equal to {1}, or equal to {2}. In short,

-∀ v φ(c) ∈ V T , χ φ ( v φ(c))
is the domain of φ(c) and φ(c) ∈ χ φ ( v φ(c)) must hold. Thus χ φ ( v φ(c)) = {∅} means that φ(c) has to be null, while ∅ / ∈ χ φ ( v φ(c)) means that φ(c) cannot be null.

-

∀ v {k} ∈ V D , χ φ ( v {k}) = {{k}} by convention.
This property is used to represent various kinds of constraints. Looking back at Figure 3.3, χ φ ( v φ(1)) = {∅} ensures that transfer φ(1) is null, while χ φ ( v φ(4)) = {∅, {3}} enforces that transfer φ( 4) is either null or equal to {3}. Transfer φ(2) has been set to {2}. Note that this property is used when a transfer is shown to be improving in all minimal strictlyactive solutions represented by the transfer graph.

• χ D and χ D : V × N → {0, . . . , m, ∞} : these two properties specify an earliest and a latest date at which each node is allowed to receive each transfer value (∞ = m + 1 in practice):

-∀ v z ∈ V , ∀i ∈ N , χ D ( v z, i) forbids node i to receive transfer value z too soon, i.e. ∀t ∈ {0, . . . , m}, if t < χ D ( v z, i), then z ⊆ O t i ; -∀ v z ∈ V , ∀i ∈ N , χ D ( v z, i) imposes a deadline on node i to obtain transfer value z, i.e. ∀t ∈ {0, . . . , m}, if t ≥ χ D ( v z, i), then z ⊆ O t i must hold.
Node i is allowed to receive transfer value z during contacts occurring between dates χ D ( v z, i) and χ D ( v z, i). If we look back at the example in Figure 3.3, node 1 is constrained to possess φ(1) from the outset as χ D ( v φ(1), 1) = 0 -i.e. φ(1) ⊆ O 1 must hold, regardless of the value of φ(1) (the fact that φ( 1) is null as a result of χ φ does not matter here).

In addition, node 3 is not allowed to receive unit 3 before contact σ 2 , since χ D ( v {3}, 3) = 2, and is even not required to possess this unit at the end of a transfer plan as χ D ( v {3}, 3) = ∞.

Remark 3.6

The properties focus on different aspects of the problem. Although linked by constraints, the different properties have their particular features and are not interchangeable. Redundancy is not really a problem in practice, but deduction algorithms must take account of it, for example in ensuring that ∀c ∈ {1, . . . , m}, all arcs a ∈ A leaving or entering a transfer vertex v φ(c) ∈ V T are such that χ A (a) = {false} when χ φ ( v φ(c)) = {∅} -and vice versa... Altogether, the transfer graph shown in Figure 3.3, (cf. the instance given in Figure 3.2) represents the set {φ 1 , φ 2 } of transfer plans where the transfer arising during contact σ 1 is null, and where datum unit 3 is transmitted from node 2 to node 4 during contacts σ 2 and σ 3 . Then, the fourth transfer must either be null, i.e. φ 1 (4) = ∅, or improving, i.e. φ 2 (4) = φ 2 (3) = φ 2 (2) = {3}. Transfer plan φ 2 is seen not to be a solution, since it does not fulfil delivery requirements (datum unit 3 is not transmitted to recipient node 1).

What represents what -

Using the transfer graph

The transfer graph (and its properties) can be used to represent a state in a branching algorithm which searches for a valid transfer plan. The properties can be used to separate a set of transfer plans during the branching stagee.g. given a unit k ∈ D and a contact σ c ∈ σ, the branches χ φ ( v φ(c)) = {{k}} and {k} / ∈ χ φ ( v φ(c)) separate the transfer plans according to whether or not φ(c) = {k}. The properties are always initialized with the constraints of the problem only, so that the whole set of valid transfer plans (the whole search space) is represented when the solving procedure starts. For example, for all datum units k ∈ D and all nodes i ∈ N -assuming that α refers to the first contact where i = r α -we set:

• χ D ( v {k}, i) = χ D ( v {k}, i) = 0 if k ∈ O i ; • χ D ( v {k}, i) = α and χ D ( v {k}, i) = m if k ∈ O i and i ∈ R; • χ D ( v {k}, i) = α and χ D ( v {k}, i) = ∞ otherwise.
Besides, the transfer graph can also be used to apply deductive elements locally. The properties can be updated to express new knowledge, e.g. value ∅ can be removed from set χ φ ( v φ(c)) if it is shown that transfer φ(c) cannot be null in a dominant solution. This enables dominated solution to be removed where possible.

Deductive elements

In this section we propose several elements of deduction (based either on the dominance rules discussed in Section 3.1, or on the problem itself). Given a transfer graph, we would like to update its properties (χ A , χ φ , χ D and χ D ) to reduce the search space it represents (so that dominated solutions can be ignored during the search for an optimal valid transfer plan).

Finding non-minimal transfer plans

Let us first consider the following proposition.

Proposition 3.5

Let k ∈ D be a datum unit and σ c ∈ σ be a contact.

1.

[minimality] Node r c cannot receive multiple copies of unit k in a minimal solution, which means that it is not necessary to consider the transmission of unit k to node r c during σ c if it is known that r c already possesses k when σ c occurs, i.e. c > χ D ( v {k}, r c ) implies that {k} / ∈ χ φ ( v φ(c)).

[validity]

The validity constraint ensures that node s c possesses the unit it sends, i.e.

c ≤ χ D ( v {k}, s c ) implies {k} ∈ χ φ ( v φ(c)). 3. [earliest-date] Node r c can receive datum unit k only if it is allowed to possess unit k, i.e. c < χ D ( v {k}, r c ) implies {k} / ∈ χ φ ( v φ(c)).
These statements can be generalized to any transfer value. For example, in a minimal transfer plan, transfer value φ(c), whatever its value, cannot be forwarded to a node that already possesses this element.

Hence the following corollary.

Corollary 3.1

Let σ c ∈ σ be a contact, and ( v φ(c), v z) ∈ A be an arc out of v φ(c),

1. [minimality] c > χ D ( v z, r c ) =⇒ χ A ( v φ(c), v z) = {false} 2. [validity] c ≤ χ D ( v z, s c ) =⇒ χ A ( v φ(c), v z) = {false} 3. [properties] c < χ D ( v z, r c ) =⇒ χ A ( v φ(c), v z) = {false}
The following deduction rules aim to refine the domain χ φ of each transfer, by using the information we have about other transfers. Figure 3.4 illustrates the propositions below. Definition 3.8 is introduced for the sake of clarity.

(a) Proposition 3.6 -

v z 2 v z 1 v z 3 v φ(c) {k} / ∈ χ φ ( v z 1 ) {k} / ∈ χ φ ( v z 2 ) {k} / ∈ χ φ ( v z 3 ) {k} / ∈ χ φ ( v φ(c)) (b) Proposition 3.7 v z 1 v z 2 χ φ ( v z 1 ) = {{1}, {2}} χ φ ( v z 2 ) = {{3},
∀ v φ(c) ∈ V T , Γ( v φ(c)) = { v z ∈ V such that arc ( v φ(c), v z) ∈ A and true ∈ χ A ( v φ(c), v z)};
-and ∀ v {k} ∈ V D , we set Γ( v {k}) = ∅ by convention.

Proposition 3.6

Given a datum unit k ∈ D and a contact σ c ∈ σ, transfer φ(c) cannot be equal to value {k} if none of the transfer values that may be transmitted during contact σ c can have that value, i.e.

[∀ v z ∈ Γ( v φ(c)), {k} / ∈ χ φ ( v z)] implies {k} / ∈ χ φ ( v φ(c)).

Proposition 3.7

For any contact σ c ∈ σ and any transfer value z that may be transmitted during that contact -i.e. such that v z ∈ Γ( v φ(c)) -transfer φ(c) cannot be equal to z if the domains of these transfer values are conflicting, i.e.

χ φ ( v z) ∩ χ φ ( v φ(c)) ⊆ {∅} implies χ A ( v φ(c), v z) = {false}.
These propositions are the basis for all the deduction algorithms discussed hereafter in this chapter. The aim will usually be to make use of bounds χ D , χ D and Corollary 3.1 to remove arcs (to set χ A -properties to {false}) in the transfer graph, so as to reduce the domain of transfers (to remove elements in χ φ -properties) using Proposition 3.6. We try to show that some transfers are necessarily null in a dominant transfer plan, by proving that the recipient nodes always possess all the transfer values that the sending nodes are able to transmit in such a transfer plan.

The practical procedure for applying these deductive elements is described in Algorithm 3.1 -whose effectiveness will depend on the quality of bounds χ D and χ D . We shall therefore devote the following subsection to consistency procedures designed to strengthen these bounds.

Elementary reasonings

In this subsection we propose algorithms designed to strengthen bounds χ D and χ D . This will enable us to show that some transfers are always null in a dominant solution (cf. Subsection 3.3.1).

Bottom-up deductive reasoning

In this paragraph, we aim to make use of knowledge related to earlier contacts (corresponding to the vertices at the bottom of the transfer graph) in order to deduce information about later contacts (corresponding to the vertices at the top of the transfer graph).

Proposition 3.8

Let i ∈ N be a node and t ∈ {0, 1, 2, . . . , m} a time index. Let v φ(c) ∈ V T be a transfer vertex, and v z 1 , . . . , v z α ∈ Γ( v φ(c)) its successors (transfer values z 1 , . . . , z α ∈ T φ therefore correspond to what node s c may transmit to node r c during contact σ c ). If i possesses z 1 , z 2 , . . . , and z α at time t, then it necessarily possesses φ(c) at time t. Whatever the value chosen for transfer φ(c) from among z 1 , . . . , z α , or ∅, node i possesses that element at time t.

Thus [∀ v z ∈ Γ( v φ(c)), t ≥ χ D ( v z, i)] implies χ D ( v φ(c), i) ≤ t.
if [c > χ D ( v {k}, r c )] ∨ [c < χ D ( v {k}, r c )] ∨ [c ≤ χ D ( v {k}, s c )] 5:
then remove {k} from χ φ ( v φ(c)) ; 6: # consistency rules in accordance with Corollary 3.1. 28: # this contact is "removed" from the model if possible.

7: # R is the union over v z ∈ Γ( v φ(c)) of sets χ φ ( v z) -
14: if [c > χ D ( v φ(c), r c )] ∨ [c > χ D ( v z, r c )] ∨ [c < χ D ( v z, r c )] 15: ∨ [c ≤ χ D ( v z, s c )] then set χ A ( v φ(c), v z) = {false} ;
29: if [Γ( v φ(c)) = ∅] ∨ [χ φ ( v φ(c)) = ∅] then 30:
set φ(c) = ∅ ; and update the transfer graph:

31:

• set χ φ ( v φ(c)) = {∅} ; 32: • for all i ∈ N do set χ D ( v φ(c), i) = χ D ( v φ(c), i) = 0 ; 33:
• for all a ∈ A leaving or entering v φ(c) do 34: From a practical point of view, this leads to Algorithm 3.2. This algorithm visits a transfer vertex v φ(c) ∈ V T and tries to strengthen bounds χ D ( v z, r c ), v z ∈ Γ( v φ(c)), associated with the recipient node r c of transfer φ(c) and each transfer value z ∈ T φ that node s c could send during that transfer. If it can be shown that node r c necessarily possesses a transfer value z at time c -1

set χ A (a) = {false} ; 35: v z 1 . . . v z k . . . v z α . . . v z k1 v z kβ v φ(c) ⊆ O c-1 rc ⊆ O c-1 rc ⊆ O c-1 rc ⊆ O c-1 rc ⊆ O c-1 rc ⊆ O c-1 rc [c -1 ≥ χ D ( v z kβ , r c )]
(if c -1 ≥ χ D ( v z, r c )), then Corollary 3.1 enables us to remove arc ( v φ(c), v z) by setting χ A ( v φ(c), v z) = {false}.
Note that if all arcs going out of vertex v φ(c) can be removed in this way, then it proves that transfer φ(c) is null in any dominant solution.

The bounds are strengthened in accordance with Proposition 3.8 within function bottom-up, with i = r c and t = c-1. v z refers to the vertex whose bounds must be refined. The function returns true if node i possesses v z at time t and puts a mark on all visited nodes to avoid redundant calculations. If the best known bound χ D ( v z , r c ) of a vertex z ∈ Γ(z) is greater than c -1 (if a condition to deduce that c -1 ≥ χ D ( v z , r c ) is not fulfilled), we attempt to refine it recursively (line 18). This algorithm is depicted in Figure 3.5.

Remark 3.7

Although Algorithm 3.2 traverses vertices in depth-first, information is propagated from lower to upper vertices. The same outcome might also be achieved by calling function bottom-up with transfer vertices v φ(1), v φ(2), . . . , v φ(c) in the order of the sequence. However, this would compel us to visit all the vertices "below" v φ(c), whatever the situation. # the recursive procedure is performed over each successor. # it has been proved that φ(c), is possessed by r c at time c -1. 9:

apply χ D ( v φ(c), r c ) ≤ c -1 ; 10: 1: 2: function bottom-up ( v z ∈ V, i ∈ N , t ∈ {0, . . . , m}) : boolean 3: 4: if t ≥ χ D ( v z, i) then 5:
return true ; 6: 7:

if v z ∈ V D then 8:
put a mark on v z ; and return false ;

for all v z ∈ Γ( v z) such that t < χ D ( v z , i) do 11: 12: if v z is marked then 13:
# the procedure has already failed to prove that node i 14:

# possesses z at time t. # the procedure attempts to prove that i possesses z at time t.

18:

else if v z is not marked and bottom-up

( v z , i, t) = false 19:
then put a mark on v z ; and return false ; # according to Proposition 3.8, i possesses z at time t.

24:

apply χ D ( v z, i) ≤ t ; and return true ; 25:

Top-down deductive reasoning

In this paragraph, we aim to make use of knowledge related to later contacts (and therefore shown at the top of the transfer graph) to deduce information about earlier contacts (located at the bottom of the transfer graph).

For example, let us consider the case where a node i ∈ N is the receiver in only two contacts σ c1 = (s1, i) and σ c2 = (s2, i) (cf. Figure 3.6). Then let us assume that sending nodes s1 and s2 possess two units 1 and 2 ∈ D, i.e.

O c1-1 s1 = O c2-1 s2
= {1, 2}, and that node i did not possess any datum units at the outset, i.e. O i = ∅. Note that a datum unit is always transmitted during σ c1 in a strictly-active transfer plan, and that χ φ ( v φ(c1)) = {{1}, {2}} in the transfer graph. This remark also holds for contact σ c2 . As the datum units transmitted to node i are always different in a minimal transfer plan, we can deduce that node i necessarily possesses datum units 1 and 2 after these two contacts in a strictly-active minimal transfer plan, i.e. χ D ( v {1}, i) ≤ c2 and χ D ( v {2}, i) ≤ c2. We have actually shown that node i possesses at least two datum units from among subset Z = {1, 2} after contact σ c2 in any dominant solution. Thus, φ(c1

) ∪ φ(c2) = {1, 2} and Z ⊆ O c 2
i . The approach can be generalized to any set of transfer values.

Definition 3.9

Given a set v Z ⊆ V of vertices in the transfer graph, a node i ∈ N , and a time index t ∈ {0, 1, . . . , m}, min-card( v Z, i, t) corresponds to a lower bound on the smallest number of transfer values z ∈ Z that node i have after the t first contacts in any minimal strictly-active transfer plan, i.e. the smallest number of transfer values z ∈ Z such that z ⊆ O t i in such a transfer plan.

In Section 3.3.3 we will discuss how min-card may be evaluated.

Proposition 3.9

Let v Z ⊆ V be a set of vertices, i ∈ N a node, and let t ∈ {0, 1, . . . , m} denote a time index. If min-card( v Z, i, t) = | v Z| (i.e. if node i possesses at least | v Z| transfer values from among a set of | v Z| transfer values at time t), then node i possesses all the transfer values in Z at time t -i.e.

[∀ v z ∈ v Z, χ D ( v z, i) ≤ t] necessarily holds.
s1 s2 i φ(c1) φ(c2) = O c1-1 s1 = {1, 2} O c2-1 s2 = {1, 2} O c2 i = {1, 2}
(b) the same reasoning in the corresponding transfer graph From a practical point of view, this leads to Algorithm 3.3. The procedure visits a transfer vertex v φ(c) ∈ V T and tries to prove that transfer φ(c) is null in any dominant solution. With this aim in view, it attempts once again to prove that any transfer value which could be transmitted during contact σ c is already possessed by node r c at time c -1 in all dominant transfer plans -that is r c ). This can sometimes be achieved using Proposition 3.9 with v Z = Γ( v φ(c)), i = r c and t = c-1, which involves evaluating min-card(Γ( v φ(c)), r c , c -1).

v {1} v {2} v φ(c1) v φ(c2) χ D ( v {1}, i) ≤ c2 χ D ( v {2}, i) ≤ c2 χ D ( v φ(1), i) ≤ c2 χ D ( v φ(2), i) ≤ c2 min-card({ v {1}, v {2}}, i, c2) = 2
∀ v z ∈ Γ( v φ(c)), c -1 ≥ χ D ( v z,
The algorithm is quite straightforward. It should be noted, however, that strengthening the bound χ D ( v z, r c ) of a vertex v z ∈ V might enable a better lower bound min-card(Γ( v z), r c , c -1) to be computed, and therefore enable Proposition 3.9 to be applied on child vertices -with v Z = Γ( v φ(c)), i = r c , and t = c -1. In fact, the same deductive steps are repeated, from the upper to the lower vertices -the aim being to find matches between the subset of transfer values which are possessed by node r c at time c-1 and other subsets of transfer values (corresponding to former contacts), or ideally to subsets of datum units.

Algorithm 3.3 -Top-Down consistency

Require: transfer graph G φ = (V, A, χ A , χ φ , χ D , χ D ) ; Require: the vertex v φ(c) to which we apply these deduction rules ; 1:

2: procedure top-down ( v φ(c) ∈ V T , i ∈ N , t ∈ {0, 1, . . . ,
if bound = | v Z| then 9:
# node i possesses all transfer values v z ∈ v Z at time t. 10:

∀ v z ∈ v Z, apply χ D ( v z, i) ≤ t ; 11: ∀ v z ∈ v Z ∩ V T , top-down ( v z, i, t) ;
∀ v z ∈ v Z, apply χ D ( v z, i) ≤ c ; 16: ∀ v z ∈ v Z ∩ V T , top-down ( v z, i, c) ;

Strict-activity-based deductive reasoning

Let us now turn to the strict-activity-based deduction rule. First recall that a transfer plan is strictly-active iif. no transfer that might have been improving is not improving (cf. Definition 3.6). This means that a transfer is necessarily improving if the sending node possesses a unit that the receiving node does not possess. For example, if we look back at Figure 3.2b (given on page 53), transfer φ(3) is improving in a strictly-active minimal transfer plan, because node 3 possesses at least two units from among {1, 2, 3} in such a solution, whereas node 4 only possesses unit 3 when contact σ 3 occurs.

Algorithm 3.4 -Strict-Activity consistency

Require: transfer graph G φ = (V, A, χ A , χ φ , χ D , χ D ) ; Require: the vertex v φ(c) to which we apply these deduction rules ; This leads to the following definition and the ensuing proposition.

Definition 3.10

Given a set v Z ⊆ V of vertices in the transfer graph, a node i ∈ N , and a time index t ∈ {0, . . . , m}, max-card( v Z, i, t) corresponds to an upper bound on the greatest number of transfer values z ∈ Z that node i have after the t first contacts in any minimal strictly-active transfer plan, i.e. the greatest number of transfer values z ∈ Z such that z ⊆ O t i in such a transfer plan. In Section 3.3.3 we will discuss how max-card may be evaluated.

Proposition 3.10

Let σ c ∈ σ be a contact, and v Z ⊆ V a set of vertices. If node s c always possesses more units than node r c when contact σ c occurs (in a minimal strictly-active transfer plan), then transfer φ(c) is necessarily improving (in such a transfer plan). min-card

( v Z, s c , c-1) > max-card( v Z, r c , c-1) therefore implies ∅ / ∈ χ φ ( v φ(c)).
This condition is tested with v Z = V D in practice, cf. Algorithm 3.4.

Delivery-requirement-based deductive reasoning

This paragraph looks at enforcing the delivery constraint, which states that every node j ∈ N has to obtain every unit k ∈ D before time t = χ D ( v {k}, j)} (except where t = ∞). To this end, we can utilize contacts σ c = (i, j) which occur before time t between a node i ∈ N and j. For φ(c) = {k} to be valid, other conditions have also to be fulfilled:

• c > χ D ( v {k}, i) (node i possess unit k when contact σ c occurs); • χ D ( v {k}, j) ≤ c ≤ χ D ( v {k}, j) (j is allowed to obtain k at time c); • {k} ∈ χ φ ( v φ(c)) (transfer φ(c) = {k} is allowed).
In consequence, if node j does not possess unit k from the outset, and if only one node i ∈ N is able to transfer k to node j on time, then an implicit constraint forces node i to obtain k, and this early enough to transmit it to node j on time. For example, in Figure 3.7, node 3 is the only one that can send datum unit 1 to recipient node 4 within time interval {χ D ( v {1}, 4) = 2, . . . , χ D ( v {1}, 4) = 3}. So, node 3 has to obtain datum unit 1 during contact σ 1 at the latest. This can be formulated as follows.

Proposition 3.11

Let k ∈ D be a datum unit, and j ∈ N a node that is required to obtain k during the transfer plan -i.e. k / ∈ O j and χ D ( v {k}, j) ≤ m. Let then

N j,k = { i ∈ N | ∃σ c = (i, j) ∈ σ with c > χ D ( v {k}, i), c ≥ χ D ( v {k}, j), c ≤ χ D ( v
{k}, j) and {k} ∈ χ φ ( v φ(c)) } denotes the set of nodes that can transmit datum unit k to node j in a valid transfer plan. If N j,k = {i} is a singleton (i.e. if only one node i can send unit k to node j), then

χ D ( v {k}, i) < χ D ( v {k}, j) and χ D ( v {k}, i) < χ D ( v {k}, j)
hold. On the other hand, if N j,k = ∅ (if there are no nodes able to send unit k to node j), then there is no solution fulfilling the set of constraints represented by the transfer graph.

For instance, in Figure 3.7a, Proposition 3.11 is applied with k = 1, j = 4, and i = 3. The only predecessor of node 4 is N 4,1 = {3}. Thus, χ D ( v {1}, 3) can be adjusted to χ D ( v {1}, 4) = 3. Thereafter, as shown in Figure 3.7b, the proposition is applied with k = 1, j = 4, and i = 1. Contact σ 4 is no longer consistent with χ D ( v {1}, 3), and node 2 then becomes the only node able to transmit datum unit 1 to node 3. Transfer φ(1) can even be set to {1}, since only one contact σ 1 = (1, 3) ∈ σ exists.

χ D ( v {1}, 4) = 2 χ D ( v {1}, 4) = 3 χ D ( v {1}, 3) = 1 χ D ( v {1}, 3) = & & ∞ 3 {1} {1} 4 1 2 3
(b) Thus σ 4 occurs too late and transfer φ(1) = {1} is necessary. From a practical point of view, this leads to Algorithm 3.5. The procedure ensures that bounds χ D and χ D are consistent -in the sense of Proposition 3.11 -for a given unit k ∈ D and all the nodes in N . Note that S is a stack containing the pair of nodes (i, j) ∈ N 2 such that N j,k = {i}, i.e. the nodes { j ∈ N such that k / ∈ O j and χ D ( v {k}, j) ≤ m } whose bounds χ D ( v {k}, j) and χ D ( v {k}, j) might need to be strengthened. Instruction fail notifies the calling function that there is no transfer plan fulfilling the set of constraints represented by the transfer graph. Therefore, if Delivery-Requirements is used within a branching algorithm, it prunes the current branch and then triggers a backtrack.

2 1 3 4 χ D ( v {1}, 4) = 2 χ D ( v {1}, 4) = 3 χ D ( v {1}, 3) = 1 χ D ( v {1}, 3) = 3 {1} {1} ¡ 4 φ(1) = {1}

Global deductive elements

The deduction procedures described above are heuristically orchestrated in Algorithm 3.6. The vertices of the transfer graph are sequentially processed to reduce the domain of possibilities χ φ associated with each transfer. If the domain of a transfer becomes a singleton, then it means that the transfer has been decided. If it becomes empty, or if the other properties are inconsistent, e.g. if

∃ v z ∈ V, ∃i ∈ N | χ D ( v z, i) > χ D ( v z, i),
then it means that no transfer plan fulfils the constraints represented by the transfer graph.

Algorithm 3.5 -Delivery-Requirements consistency

Require: transfer graph G φ = (V, A, χ A , χ φ , χ D , χ D ) ; Require: the vertex v φ(c) to which we apply these deduction rules ; 1: 2: # the set of nodes whose bounds have to be checked is stored in stack S. (i, j) ← S.back() ; S.pop() ; 9:

apply χ D ( v {k}, i) < χ D ( v {k}, j) and χ D ( v {k}, i) < χ D ( v {k}, j) ; 10: 11:
# unique transfers are even forced.

12: update N i,k ; and push (z, i) if N i,k = {z} ; or fail if N i,k = ∅ ; During each iteration c ∈ {1, 2, . . . , m}, there is first an attempt to refine the bound χ D ( v z, r c ) of every successor v z ∈ Γ( v φ(c)) of vertex v φ(c) in the transfer graph (using both bottom-up and top-down deductions). This aims to prove that some transfer values which can be transferred by node s c during contact σ c are possessed by node r c when the contact occurs (in any minimal and strictly-active transfer plan). Subsequently, the minimality consistency algorithm is charged with updating χ A and χ φ . The strict-activity-and the delivery-requirement-based consistency algorithms are run independently. This way, we can often show that some transfers are null in any dominant transfer plan. The procedure can be repeated as long as changes are occurring in Delivery-Requirements. Nevertheless, this is seen to be inefficient in practice (most of the transfers being fixed from the first call). We have tested Algorithm 3.6 as a preprocessing procedure aiming at detecting and removing fruitless contacts, so that the size m of sequence σ can be reduced before the problem is solved. Moreover, we have tested it as a propagation procedure, whose goal is to set variables during each branching stage of a branch-and-cut algorithm (during the solving of an integer-linear-programming model which will be described in Section 3.4). However, before going any further, we must discuss how bounds min-card and max-card are computed in practice.

if ∃!σ c = (i, j) ∈ σ | c > χ D ( v {k}, i), c ≥ χ D ( v {k}, j),

Algorithm 3.6 -Global-Consistency -heuristic

Require: transfer graph G φ = (V, A, χ A , χ φ , χ D , χ D ) ; 1:

2: # the main loop aims to find which transfers are necessarily null. # are also possessed by node r c when contact σ c occurs.

7: Bottom-Up (G φ , v φ(c)) ; Top-Down (G φ , v φ(c)) ; 8: 9:
# the strict-activity consistency procedure is run independently. # with the minimality rule.

Evaluating min-card and max-card

In this section, we will look at how to evaluate an upper and a lower bound on the number of transfer values possessed by a given node at a given time (cf. Definitions 3.9 and 3.10). The input data will always be one instance of the dissemination problem, one transfer graph (one subset of transfer plans), one subset v Z ⊆ V of its vertices, one node i ∈ N , and finally one time index t ∈ {0, . . . , m}. With regard to max-card, note that only the case v Z = V D will be considered, i.e. we will have to find an upper bound of the number of datum units possessed by node i at time t (cf. Algorithm 3.4).

How to compute max-card

Let us consider the problem of evaluating max-card(V D , i, t). We recall that the different datum units (represented by V D ) that a node i ∈ N can receive before time t ∈ {0, . . . , m} are associated with as many vertex-disjoint paths in the transfer graph. Each path has to start at a transfer vertex v φ(c) ∈ V T (c ≤ t) where r c = i, and end at a unit vertex v {k} ∈ V D . These paths must also fulfil the constraints which result from functions χ A , χ φ , χ D and χ D (cf. the summary given on page 58). Therefore, by relaxing the constraints expressed with functions χ φ , χ D and χ D , the problem in hand can be reformulated as the problem of finding the greatest number of arc-and vertex-disjoint paths from a transfer vertex v φ(c) ∈ V T such that c ≤ t and r c = i to a unit vertex v {k} ∈ V D . Of course the search is limited to the subgraph defined by χ A (i.e. the arcs a ∈ A such that true ∈ χ A (a)). To solve this problem, we compute a maximum flow in a transportation network G = (X, U, cap) comprised of the following elements (cf. Figure 3.8, instance Figure 3.2, page 53):

1. we consider a source vertex src ∈ X and a sink vertex snk ∈ X;

2. with each vertex v z ∈ V in the transfer graph, we associate two vertices z s and z e ∈ X and an arc (z s , z e ) ∈ U between these two vertices in the transportation network;

3. with each arc a = ( v x, v y) ∈ A such that true ∈ χ A (a) in the transfer graph, we associate an arc (x e , y s ) ∈ U in the flow network;

4. we add an arc from the source node src to any vertex z s ∈ X which is associated with a transfer value possessed by node r c at time t (where χ D ( v z, i, t) ≤ t in the transfer graph);

5. we add an arc from each unit vertex {k} e ∈ X to the sink node snk; 6. the capacity of each arc a ∈ U is finally set to cap(a) = 1;

{1} s {1} e {2} s {2} e {3} s {3} e φ(1) e φ(1) s φ(2) e φ(2) s src snk max-card( v Z = V D , i = 3, t = 2) = 2 1/1 1/1 0/1 1/1 1/1 1/1 1/1
7. note that any node z ∈ X that is not descendant of src, nor ascendant of snk can be removed.

Flows represent arc-disjoint paths (as all capacities are set to 1), and define a valid assignment of the transfer values possessed by node i at time t. Note that the value of each transfer φ(c), c ∈ {1, . . . , m} is unambiguous because at most one unit can flow out of each vertex φ(c) e ∈ V (the paths are vertex disjoint). The constraints expressed by χ A are fulfilled by construction.

Hence the following proposition.

Proposition 3.12

Let f M be the maximum flow through G. f M = max-card (V D , i, t) is an upper bound on the greatest number of units that node i ∈ N possesses after the first t contacts.

Finally, it is worth nothing that strict-activity and minimality constraints can be disregarded when computing max-card( v Z, i, t) -because redundant and postponed transfers can only lead to a reduction in the number of datum unit received by node i.

What about min-card ?

Let us now turn to the problem of computing min-card( v Z, i, t) (the smallest number of transfer values z ∈ Z possessed by node i at time t in a dominant transfer plan). It might be tempting to use the same approach and to try to transform the smallest cardinal bound problem into a well-known flow-based problem. Unfortunately this does not work. The optimal solution will always be the null transfer plan in which no datum units are transferred at all, and therefore the lower bound will always be null. To get tight bounds, solutions must be required to be minimal strictly-active transfer plans (which prevents unjustified null transfers occurring). Unfortunately this constraint cannot be introduced into a flow problem. Note that it can be proved that computing an exact value min-card( v Z, i, t) -i.e. the precise number of transfer values in v Z that node i possesses at time t in the worst case -is strongly NP-hard if solutions have to be strictly-active.

We were unable to find a satisfactory heuristic for the problem. Thus we have proposed a procedure for polynomially transforming an instance of the smallest cardinal bound problem, where v Z ⊆ V D does not necessarily hold, into another instance where v Z ⊆ V D holds, i.e. where datum units only need to be considered. In this case, the integer-linear-programming model defined in Section 3.4 can be adapted to our needs (with minor changes). Evaluating the exact value of min-card in the transformed instance gives rise to a lower bound of min-card( v Z, i, t) in the original instance.

Unfortunately, the transformation is not always relevant and the method is then limited to some cases that we describe below.

v {1} v {2} v {3} v {4} v {5} v φ(1) v φ(3) v φ(5) v φ(11) v φ(2) v φ(7) v φ(6) v φ(4) v φ(10) v φ(8) v φ(9)

How to perform this transformation

Let us consider the instance depicted in Figure 3.9. We would like to compute min-card({ v φ(1), v φ(3)}, 5, 6), that is the smallest number of transfer values from among set Z = {φ(1), φ(3)} possessed by node i = 5 after the first t = 6 contacts in a dominant solution.

As we stated above -in order to evaluate min-card (using integer linear programming) -we wish to reduce the original problem to an easier problem where v Z ⊆ V D . With this goal in mind, we propose adding a virtual datum unit {A} to represent transfer value φ(1) ∈ Z. Like φ(1), {A} is transmitted to node 1 at time 1 via a fictitious source node s 1 , while contact σ 1 is removed from the instance. Transfer φ(3) ∈ Z is then replaced by virtual datum unit {B} in the same way. Finally, any contact (resp. node) whose representative arc (resp. vertex) does not belong to a journey to node i = 5, or which occurs after contact σ t = σ 6 , is removed from the instance, since it cannot help i to obtain new units on time. This instance is depicted in Figure 3.10a.

In fact, min-card({ v φ(1), v φ(3)}, 5, 6) in the original instance is equal to min-card({ v {A}, v {B}}, 5, 6) = 2 in the new instance (we can compute this value since we are only considering datum units). Node 2 receives unit {A} instead of transfer value φ(1) (during σ 1 ), but both represent one datum unit in the set {{1}, {2}}. Next node 4 receives {B} instead of transfer value φ(3) (during σ 3 ), but both represent one unit in the set {{3}, {4}}. As the rest of the instance is not changed, units {A} and {B} play the same role as transfer values φ(1) and φ(3) ∈ Z in the original instance. Consequently, φ(1) ⊆ O 6 5 and φ(2) ⊆ O 6 5 hold in all dominant solutions. In the general case, thanks to the transfer graph, the transformation can be automated using the following procedure. 1. To "replace" a transfer φ(c) by a virtual unit, it is sufficient to remove all descendants of vertex v φ(c) in the original transfer graph, so that it becomes a leaf in the new transfer graph (i.e. a vertex that represents a datum unit). This virtual datum unit thus aggregates the choices that must be made regarding the removed vertices. This operation is to be repeated for all the vertices v z ∈ v Z ∩ V T . In this way, all the transfer values in v Z are units in the new instance.

2. Thereafter, the deletion of the irrelevant entities consists in removing the contacts occurring too late (i.e. { v φ(c) ∈ V T | t < c}), together with the transfer values whose representative vertex is not a descendant of a vertex associated with node i in the transfer graph (i.e.

{ v z ∈ V such that ∃ v φ(c ) ∈ V T , c ≤ t, r c = i and v z is a descendant of v φ(c ) }).
v {1} v {A} v {2} v {3} v {B} v {4} v {5} v φ(1) v φ(3) v φ(5) v φ(11) v φ(2) v φ(7) v φ(6) v φ(4) v φ(10) v φ(8) v φ(9)

The limits of our approach

In some cases, not all of the successors of a vertex are removed. For example, in Figure 3.11b, the successor v {4} of vertex v φ( 5) is removed to transform φ(3) into {B}, while vertex v {5} is kept. In a such situation, the evaluation of min-card in the transformed instance is not a lower bound of min-card in the original instance. Extra transformations are required, because the set of choices concerning these transfers has been implicitly reduced. Some transfer plans might thus be ignored.

In this example, it would imply that φ(5) = φ(7) = {5}, and consequently that φ(8) = φ [START_REF] Bocquillon | Minimizing the dissemination length in the one-datum-unit data transfer problem[END_REF]. We would therefore find φ(9) = {A}, φ(10) = {B}, or vice versa, and finally conclude that min-card({ v φ(1), v φ(3)}, 7, 11) = 2. Yet the minimal strictly-active transfer plan φ such that - In fact, for the bound to be computed consistently, transfer φ( 5) needs to be transformed into a fourth virtual unit {D} by removing the remaining descendant v {5} of vertex v φ [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF]. In practice, such cases are never addressed, since they generally lead to complex transformations (triggered in chain) and poor bounds. Each transformation is actually a relaxation of some minimality constraints, in the sense that dependent sets of choices are being assimilated to independent units. For example, the transformation of transfers φ(3) and φ(11) ⊆ {3, 4} into virtual datum units {B} and {C} implicitly allows that φ(3) = φ [START_REF] Bocquillon | Modeling elements and solving techniques for the data dissemination problem[END_REF], although r 3 = r 11 = 10.

φ(1) = φ(2) = φ(8) = {1}, φ(3) = φ(10) = {3}, φ(5) = φ(7) = {4}, φ(9) = {5},
The case where some transfer values in v Z have hierarchical relationships is not addressed either. Transforming ancestors implies deleting descendants, so that the target value min-card( v Z, i, t) = | v Z| becomes unattainable from the beginning.

Proposition 3.13

Let v Z T be the set of (virtual) datum units in the transformed instance (corresponding to the set of transfer values v Z in the original problem). Let min-card T ( v Z T , i, t) refer to the smallest number of transfer values in Z T that node i possesses at time t in a dominant transfer plan (computed in the transformed instance). min-card T ( v Z T , i, t) = min-card( v Z, i, t) is a lower bound of the smallest number of transfer values possessed by node i after the first t contacts in the original instance. In the following section we propose an integer-linear-programming model designed to solve the dissemination problem. Note that it is quite similar to the model we use in practice to compute min-card T ( v Z T , i, t).

v {1} v {A} v {2} v {3} v {B} v {4} v {5} v {C} v φ(1) v φ(3) v φ(5) v φ(11) v φ(2) v φ(7) v φ(6) v φ(4) v φ(10) v φ(8) v φ(9)

Solving the dissemination problem

In Section 3.1 we proposed several dominance rules which enable the search space to be reduced. Deduction procedures based on these results were then discussed in Sections 3.2 and 3.3. In this section we propose an integer-linearprogramming model to solve the problem.

Integer linear programming

The integer-linear-programming model we propose is quite straightforward, and is based on a set of time-indexed boolean variables describing a transfer plan. For each node i ∈ N , we define T i = {0} ∪ {c ∈ {1, 2, . . . , m} | r c = i}, the set of time indexes at which the state of node i can change, i.e. at which node i can receive a datum unit. Subsequently, ∀t ∈ {0, 1, . . . , m}, we define T i (t) = max {t ∈ T i | t ≤ t}. Thus, T i (t) refers to the last contact occurring before time t where node i is the receiver.

The variables are defined as follows:

• ∀k ∈ D, ∀c ∈ {1, . . . , m}, x k,c = 1 if datum unit k is transmitted from node s c to node r c during contact σ c , and x k,c = 0 otherwise.

• ∀i ∈ N , ∀k ∈ D, and ∀t ∈ T i , y i,k,t = 1 if node i possesses unit k after contact σ t , and y i,k,t = 0 otherwise.

• ∀t ∈ {0, 1, . . . , m}, z t = 1 if there is a node i ∈ R which is not entirely served after the first t contacts, and z t = 0 otherwise.

Remark 3.8

y-variables are indexed with sets T i instead of set {0, 1, . . . , m}. However, we may easily know whether a node i ∈ N possesses a datum unit k ∈ D at any index t ∈ {0, 1, . . . , m}. Indeed, y i,k,T i (t) = 1 if and only if node i possesses datum unit k after the first t contacts.

The model thus contains um x-variables, u.(2m + n) y-variables and m + 1 z-variables.

Minimizing the dissemination length leads to the following objective.

λ * = min m t=0 z t (3.1)
Given a time index t ∈ {0, 1, . . . , m}, variable z t is null if and only if all the recipient nodes have been served at time t, i.e. ∀i ∈ R, ∀k ∈ D, y i,k,T i (t) = 1.

Hence the following constraints.

∀i ∈ R, ∀t ∈ T i , ∀k ∈ D, z t ≥ 1 -y i,k,t (3.2)
Equations (3.2) can be aggregated in different ways:

∀t ∈ {0, . . . , m}, ∀i ∈ R, z t ≥ 1 - 1 u k∈D y i,k,T i (t) (3.2-a)
and/or ∀t ∈ {0, . . . , m}, ∀k ∈ D,

z t ≥ 1 - 1 |R| i∈R y i,k,T i (t) (3.2-b)
and/or ∀t ∈ {0, . . . , m}, z t ≥ 1 -

1 u.|R| i∈R k∈D y i,k,T i (t) (3.2-c)
The efficiency of the variants will be discussed in Section 3.5.

Other constraints bind the x-variables (the decision variables) to the y-and the z-variables (the auxiliary variables). They ensure that each constraint is respected (e.g. the transfer plan must be valid):

• All recipients have to be served before the end of the time horizon:

z m = 0 (3.3)
• Each node i ∈ N initially possesses a subset O i of datum units:

∀i ∈ N , ∀k ∈ D | k ∈ O i , y i,k,0 = 1 (3.4) ∀i ∈ N , ∀k ∈ D | k / ∈ O i , y i,k,0 = 0 (3.5)
• The transfer plan must be valid (sending nodes must possess the datum units that they transfer):

∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, x k,c ≤ y sc,k,T i (c-1) (3.6)
• Nodes possess a datum unit from the time they receive it:

∀k ∈ D, ∀c ∈ {1, . . . , m}, y rc,k,c ≤ y rc,k,T i (c-1) + x k,c (3.7) ∀k ∈ D, ∀c ∈ {1, . . . , m}, y rc,k,c ≥ 1 /2 y rc,k,T i (c-1) + x k,c (3.8)
• At most one datum unit can be transferred during each contact: ∀c ∈ {1, . . . , m}, k∈D x k,c ≤ 1 (3.9)

Additional constraints

Together, constraints (3.7) and (3.8) ensure that variable y rc,k,c is equal to 1 if y rc,k,T i (c-1) = 1 or x k,c = 1, and to 0 otherwise -i.e. node r c possesses unit k after contact σ c if it already possessed k after contact σ c-1 , or if it received the unit during contact σ c . Yet, if we seek a minimal transfer plan, as both conditions cannot be true at the same time, constraints (3.7) and (3.8) can be replaced by the following constraint:

∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, y rc,k,T i (c-1) + x k,c = y rc,k,c (3.10)
It is possible to strengthen the model such that transfer plans are active, but this unfortunately leads to complex equations and poor numerical results in practice. However, it is quite easy to guarantee that solutions are strictlyactive. This can be achieved by ensuring that transfer plans are minimal and that any transfer φ(c) cannot be null if the sending node s c possesses at least one datum unit that the receiving node r Below we discuss the effectiveness of preprocessing procedures, cf. Section 3.3, and we compare the different models proposed in this Section.

Computational results

In this section, experimental results are reported and discussed. First of all, in Section 3.5.1, the random process used to generate the benchmark will be described. Instance classes are built with respect to the number of nodes n and the number of datum units u (the number of contacts m is chosen such that most of the instances are feasible). The models described in Section 3.4 are assessed in Section 3.5.2, while the preprocessing procedures proposed in Sections 3.2 and 3.3 are discussed in Section 3.5.3.

About the benchmarks

In this section, we describe a destruction/construction algorithm to generate difficult instances for the dissemination problem. The instances are available on our website [START_REF]Instances of the dissemination problem[END_REF].

Random instances are generally easy to solve. That is why we developed a procedure which attempts to increase the "hardness" of an existing instance by iteratively renewing the least relevant contacts (the contacts removed by a trivial preprocessing procedure). Usually starting with a random instance, the process is intended to generate harder and harder instances by removing irrelevant contacts, in such way that new ones can be added elsewhere in the sequence, without increasing the size of the problem (specifically the number of contacts). Note that a few random contacts are also renewed to introduce more diversity in the instances visited during the process.

At each iteration, the instance is solved by a given solver (in practice we can use the branch-and-cut algorithm defined in Section 3.4.1). After a given number of iterations, the instance that has required the most CPU-time to be solved is returned (this is assumed to be the most "difficult" instance).

The generated instances were classified by difficulty, with respect to the number of nodes n and the number of datum units u. The number of contacts m was chosen accordingly. Next the instances were solved using a variety of solvers, e.g. a MIP-based solver with and without a preprocessing procedure, and the union of the twenty hardest instances obtained for each solver was retained (except that the instances which could not be solved by at least one of these solvers were ignored). 184 instances were selected in this way, resulting in eight classes (named 3u10n, 4u20n, 4u50n, 4u100n, 5u50n, 10u10n, 50u10n, and 100u10n). These classes are described by the number nbinst of instances they contain, the number u of datum units and the number n of nodes characterizing these instances. The average number rec of recipients i ∈ R, the average number src of sources i ∈ N | O i = ∅, and the average number m of contacts of these instances are reported below. Thereafter, the eight classes were grouped by difficulty. The first group contains the easiest instances. The second and the third group contain the instances having many nodes but few datum units, or few nodes but many datum units, respectively. In the following subsections, we provide and discuss some computational results that show the efficiency of our algorithms. These computations were performed on a server equipped with 16 × 6 cores (each running at 2.67Ghz) and 1TB RAM. All the algorithms are implemented in C++. MILP are solved by CPLEX, the commercial solver developed by IBM-ILOG. Multithreading features proposed by this library are deactivated, since the use of concurrent optimizers led to unstable results. More specifically, several executions of the same computation sometimes led to different results (in terms of CPU time), which prevents us making reliable analyses. Consequently, all instances were solved by an exact, sequential, and deterministic algorithm, within a one-hour time-limit.

The same information is to be found in all tables of results, namely:

1. solved (-%) indicates the ratio of instances solved by the solver.

feas (-%) indicates the ratio of instances that remained unsolved but for

which the solver found at least one feasible solution within the one-hour time-limit.

Therefore 100%solvedfeas (-%) indicates the ratio of instances for which the solver neither found a feasible transfer plan, nor showed the instance to be infeasible.

3. gap (-%) is the average relative gap between the best lower bound and the best feasible solution which have been computed during the search (this metric concerns only the feas% of the instances which remained unsolved but for which the solver found at least one feasible solution).

4. cpu (-s) indicates the average solving time for the given solver, including all instances and thus all time-limits. cpu therefore tends to 3600s when solved tends to 0.0%.

Remark 3.9

In each section, different sets of parameters are compared, and the best strategies selected. In our opinion, such a selection should be made with respect to the three groups rather than the eight classes. In this way the benchmark cannot be learned by heart. There is no clear dominance between these four models. In every group, one notes that the best results per class are obtained with a different model (the impact of each constraint appears to be random at first glance). However we decided to use constraint (3.2-a) in the following, because it leads to the best results on average, i.e. across all classes. Dominance rules -Model std can be refined. If transfer plans are required to be minimal, constraints (3.7)+(3.8) can be replaced by constraint (3.10), giving rise to a new model denoted as min. If transfer plans are required to be strictly-active too, constraint (3.11) can be added to model min. It gives rise to a third model, termed min+st/act. The numerical results obtained with these two models are reported in Table 3

About the models

Models

.2.
Model min+st/act is seen to outperform both std and min in the first group, while model min dominates the two others on bigger instances. None of them, however, gives convincing results, and limits appear as the number of nodes and, more importantly, the number of units increases.

As we will confirm below, the difficulty of an instance is better explained by the number of datum units than by the number of nodes. With a solving rate greater than 90% for all solvers, the instances in group 2 (characterized by many systems but few units) seem manageable whereas, instances of the third group (few systems but many units) seem out of reach for the moment. This being said, we could state that min is the best model out of the three, because it is the only one that successfully solves some of the most difficult instances. However, this model's disappointing results when dealing with the easier classes (namely 3u10n and 4u20n), make us reluctant to make such a categorical statement.

These three options (std, min and min+st/act with constraint (3.2-a)) will therefore continue to be considered in the next section. The superiority of model min will then be clearly established.

About the preprocessing procedures

The main conclusion of the previous section is probably that standard solvers show their limits quite soon for this kind of problem.

Fortunately the deduction algorithms proposed in Section 3.3 significantly improve efficiency of solvers when applied within a preprocessing procedure whose role is to remove useless contacts or, conversely, to detect unavoidable transfers. To show this, we will now investigate different procedures that are based on Algorithm 3.6, cf. Section 3.3.2.

Let us recall that Algorithm 3.6 is based on a model known as the transfer graph that encapsulates knowledge about each transfer φ(c), c ∈ {1, . . . , m}, and each state O t i , i ∈ N , t ∈ {0, . . . , m}. We are then able to apply different dominance-rule-based propagation algorithms to deduce new knowledge, and in particular to reveal the transfers that are always null (or improving) in a minimal strictly-active transfer plan. The routine processes all transfers φ(c), c ∈ {1, 2, . . . , m}. First, it calls Bottom-Up and Top-Down to determine which units possessed by node s c have been received by node r c . Thereafter procedure Minimality+Validity uses the eponymous dominance rules to avoid fruitless transfers. Strict-Activity and Delivery-Requirements also detect transfers that are necessary, or impossible. The knowledge, thus enriched, can finally be passed on to the mathematical model. Some variables can be fixed at the root node -e.g. if transfer φ(c) is shown to be null in all dominant solutions, then ∀k ∈ D, x k,c = 0.

As usual, a tradeoff has to be found between the time spent running the preprocessing procedure, and the time saved in the branch-and-cut procedure as a result of the preprocessing. Actually, this is particularly true for routines Top-Down and Strict-Activity, since both often consume a significant amount of time computing min-card (cf. Section 3.3.3). To empirically find the compromise, we propose five more or less aggressive strategies, which are labelled minimal, light, normal, aggressive and maximal. The strategies are built with the intuitive idea that consistency algorithms are more efficient on earlier contacts than on later ones, because min-card problems involving few transfers are much smaller. Therefore we just vary the number of contacts after which the most computationally costly routines are skipped.

These strategies are characterized by the maximum amount pre.tl of time which can be spent in the preprocessing procedures, the ranges td.range and sa.range of contacts to which routines Top-Down and Strict-Activity will respectively be applied, and the maximum number dr.limit of times the while-loop of routine Delivery-Requirements can be run. The functions evaluating min-card and max-card are limited in time by parameters minc.tl and maxc.tl, respectively. Bottom-Up and Minimality+Validity can be used without any restriction.

The five strategies are described below. Note that td.range = 0.25 means that top-down deductive reasoning is applied to the first quarter of transfers (from c = 0 to c = 0.25 × m ). The experimental results obtained using the different strategies are reported in Tables 3.3 through 3.7. The two columns rem and fcd (-%) indicate the average percentages of contacts that have been removed (shown to be null in all dominant solution), or alternatively forced (compelled to be improving or even fixed). In this way rem and fcd measure the efficiency of the procedures. They must be considered together with prep, the average amount of time required to execute the procedures. /rem(max.) (×100)

• Δ fcd = fcd(prep.)
/fcd(max.) (×100)

• Δ prep = prep(prep.)
/prep(max.) (×100)

Table 3.8 -The best preprocessing strategies.

Remark 3.10

The most aggressive strategymaximal -is characterized by a specific propagation algorithm, which is executed before procedure Bottom-Up for all contact indexes, that is at the beginning of Algorithm 3.6's main loop. It attempts to prove that node r c has necessarily obtained all the units (the whole datum) in accordance with Proposition 3.9, by testing whether min-card(V D , r c , c-1) = u. If so -combined with Bottom-Up and Minimality+Validity -this results in the deletion of contact σ c . Although this procedure is inefficient in practice, we retained it as part of maximal, because it is only designed to upper-bound the number of deductions that can be done with our approach.

Minimal -In this strategy, only the most basic procedures are run, e.g. no transfer can be forced (since Strict-Activity is deactivated). The number of null transfers detected is low. Although the amount prep of time required to preprocess the instance is insignificant, and almost linear with respect to the number of contacts, this strategy does not improve the behaviour of the solver (the results reported in Tables 3.1/3.2 and 3.3 are similar). In fact we may suppose that CPLEX's preprocessing engine already makes such kinds of deductions from the MILP model.

Light/Normal/Aggressive -The effects of the preprocessing procedures become significant when Top-Down and Strict-Activity are acting, e.g. if we look at the first class in Table 3.4, almost half of the contacts have been removed and about 5% of the transfers have been forced in only 0.4 seconds. The efficiency of the preprocessing procedures is remarkable on the first two groups, but unfortunately collapses when the number of datum units is large (rem and fcd drop when u is greater than 4 or 5).

This behaviour may be explained by the fact that both Top-Down and Strict-Activity need strongly NP-Hard problems (evaluating min-card) solved (which is far from straightforward). These problems are characterized by fewer contacts, some datum units, and only one recipient. In fact, we try to solve smaller problems in order to deduce information about the original master problem. Unfortunately, these problems are much more difficult when the number of units is larger (for all transfers, there are too many options), and the CPU time required to run preprocessing procedures explodes -e.g. see column prep in Table 3.7.

Maximal -This strategy is really much too aggressive. The computational overhead of the overall preprocessing procedure is unjustified. This remark is highlighted in Table 3.8, where the experimental results of the best strategies are summarised. In the three last columns are given different ratios between these strategies and maximal. Thus, if we consider class 5u50n, almost all contacts removed (resp. about 60% of the contacts forced) by maximal, are also removed (resp. forced) by strategy light, with a computational cost that is around 30 times less. So strategy maximal should not be used.

Note in addition that model min is clearly dominant when preprocessing procedures are used -except for 10u10n which is better solved with model min+st/act.

Conclusion

First it will be remarked that the dissemination problem can be solved more efficiently by using the deductive elements proposed in Section 3.3. We have shown how these can be used within a preprocessing procedure designed to simplify the instances. Given the positive results achieved, we also attempted to apply these deduction rules dynamically, by propagating the constraints during the branching stage, as a constraints-programming engine would do. However, this gave poor results that are not worth reporting here.

Such an approach falls within the well-known framework called constraint propagation, a powerful tool of constraint programming that is unsuitable for linear programming. Implementing Algorithm 3.6 with linear programming seemed unnatural and excessively complex. Typically, matching the variables of our model and the properties of the transfer graph (χ A , χ φ , χ D and χ D ) is not at all a straightforward matter. This prevents us from making full use of the information obtained using the deduction procedures in the modele.g. what kind of relationships is it that binds the arcs of the transfer graph (or more specifically function χ A ) and the x-variables ?

In addition, while the notion of minimal transfer plan is seen to be well integrated into the model (through constraint (3.10)), the concept of strictlyactive transfer plan continues to yield disappointing results. To tackle these problems, we now propose a new constraint-programming-based model.

Constraint programming

I nteger linear programming has been seen to be an unsuitable framework for taking full advantage of the dominance rules proposed in Chapter 3. In particular, formulating the concept of strictly-active transfer plan in the linear program has yielded mitigated numerical results (as opposed to the notion of minimal transfer plan, which has already produced promising results). To address this issue, we propose to use constraint programming in hope that constraint propagation mechanisms will enable every dominance rule to be leveraged more effectively. First we will propose a new program modelling the dissemination problem, and then a branching algorithm for obtaining a solution (cf. Section 4.1). Next we will propose additional features to refine this procedure (cf. Section 4.2).

Contents

Modelling the dissemination problem

In this section, we first propose a constraint programming model for solving the dissemination problem, and then a branching algorithm for finding valid transfer plans (this procedure will be refined in Section 4.2).

Constraint programming model

The model proposed below is directly inspired by the linear model described in Section 3.4. However, since non-linear expressions can now be used, many constraints will be significantly simplified.

As a reminder, for each node i ∈ N is defined T i , the set of time indexes at which the state of i can change, i.e. T i = {0} ∪ {c ∈ {1, 2, . . . , m} | r c = i}. In addition, ∀t ∈ {0, 1, . . . , m}, we refer by T i (t) to the last contact occurring before time t where node i is the receiver, i.e.

T i (t) = max {t ∈ T i | t ≤ t}.
The variables are defined as follows:

• ∀k ∈ D, ∀c ∈ {1, . . . , m}, x k,c = 1 if datum unit k is transmitted from node s c to node r c during contact σ c , and x k,c = 0 otherwise.

• ∀i ∈ N , ∀k ∈ D, and ∀t ∈ T i , y i,k,t = 1 if node i possesses unit k after contact σ t , and y i,k,t = 0 otherwise. See Remark 3.8 on page 82.

• ∀c ∈ {1, 2, . . . , m}, a c = 1 if transfer φ(c) is improving (something new is transmitted to node r c ), and a c = 0 otherwise.

• ∀i ∈ N , ∀k ∈ D, variable λ i,k represents the delivery length associated with datum unit k and node i -i.e. the date from which node i stores datum unit k. Its domain is T i ∪ {∞}. Note that λ i,k = ∞ means that node i does not recover unit k during the transfer plan. In practice we can take ∞ = m + 1.

• ∀i ∈ R, variable λ i = max k∈D {λ i,k } then represents the delivery length of recipient node i -i.e. the date from which node i stores all the datum units. Its domain is T i (because i has to be served).

• Finally, variable λ = max i∈R {λ i } represents the dissemination length of the transfer plan. Its domain is therefore i∈R T i ⊆ {0, 1, . . . , m}.

Minimizing the dissemination length leads to the following objective.

λ * = min λ (4.1)
The constraints are written as follows:

• Each node i ∈ N initially possesses a subset O i of datum units:

∀i ∈ N , ∀k ∈ D | k ∈ O i , y i,k,0 = 1 (3.4) ∀i ∈ N , ∀k ∈ D | k / ∈ O i , y i,k,0 = 0 (3.5)
• The transfer plan must be valid (sending nodes must possess the datum units that they transmit):

∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, x k,c ≤ y sc,k,T i (c-1) (3.6)
• Nodes possess a datum unit from the time they receive it:

∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, y rc,k,T i (c-1) + x k,c = y rc,k,c (3.10)
• At most one datum unit can be transferred during each contact:

∀c ∈ {1, 2, . . . , m}, k∈D x k,c = a c (4.2)
• λ i,k is the delivery length associated with datum unit k and node i:

∀i ∈ N , ∀k ∈ D, ∀t ∈ T i , y i,k,t = 0 ⇐⇒ λ i,k > t y i,k,t = 1 ⇐⇒ λ i,k ≤ t (4.3)
• The transfer plan must be strictly-active:

∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, if [ y sc,k,Ts c (c-1) > y rc,k,Tr c (c-1) ] then [ a c = 1 ] (4.4)

Remark 4.1

As a reminder, constraint (3.10) ensures that node r c possesses a datum unit k after contact σ c if it possessed k after contact σ c-1 , or if it received k during contact σ c . Nevertheless, the constraint prevents both of these conditions being true at the same time, and so ensures that the solution is minimal.

Altogether, the model thus contains um x-variables, u.(2m + n) y-variables, nu + |R| + 1 λ-variables, m a-variables, and un + m + 5um constraints.

The model is solved by a branch-and-bound procedure. The efficiency of such an algorithm is heavily dependent on the "branching variables" that are selected, as well as on the quality of the bounds computed at every node of the search tree. For this reason we propose a branching heuristic in the next section. Lower bounds for the problem will be introduced in Section 2.3.

Branching algorithm

In order to prune branches as early as possible and obtain a fast convergence, it is necessary to find good upper bounds quickly. To this end, priority should be given to the most promising branches, so that the better solutions (whose values are upper bounds) are visited sooner. This is why we propose setting transfers sequentially and heuristically, i.e. the x-variables are set from x k,1 (∀k ∈ D) to x k,m . This also makes it easy to develop ad hoc procedures that reduce the size of enumerations (cf. Sections 4.2.1 and 4.2.2).

In practical terms, at each node of the search tree, the solver selects the smallest index c ∈ {1, 2, . . . , m} for which the value of transfer φ(c) has not yet been decided, then creates one branch per possible value -i.e. it creates one branch for each unit k ∈ D such that variable x k,c is not fixed, then sets x k,c = 1 and x k ,c = 0 for all k ∈ D\{k}. If variable a c is not fixed to 1, then an extra branch is created for the null transfer. To this end the whole set of x k,c variables (∀k ∈ D) is set to 0.

Therefore, except for the branch corresponding to the null transfer, each branch is associated with exactly one datum unit k ∈ D, and can be referred to as B k unambiguously.

The order in which these branches are visited is heuristic (and the result of many empirical tests conducted by A. Groud, L. Leichtnam, and myself).

1. First of all, we seek to identify the most "critical" transfers in terms of feasibility. In particular -as the fewer the remaining opportunities for node r c to receive a datum unit k ∈ D, the more urgent the transfer of k becomes -we give priority to the branches B k for which criterion |{ t ∈ {c, . . . , m} such that r t = r c and x k,t is not set to 0 }| is the lowest.

2.

In case of a tie, we seek to balance the dissemination of all the datum units. Therefore we prioritize the branches B k whose criterion |{ t ∈ {1, 2, . . . , m} such that r t = r c and x k,t is not set to 0 }| is the highest. This criterion is actually based on the heuristic proposed by Belblidia et al. in [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF].

3. If there is one, the branch corresponding to the null transfer is always considered as a last resort.

In practice, this heuristic has given promising results. It unfortunately fails on some instances of medium and large size. When the number of backtracks starts to soar, we therefore switch to the solver's built-in algorithm1 and start the search again from scratch. The default algorithm seems better to prove the optimality of a solution -i.e. to "close" the nodes in the search tree.

These failures occur because pure depth-first searches (like ours) generally yield an initial solution quite fast -but do not move easily from one area of the search space to another, since they are often unable to recover sufficiently quickly from bad decisions made early on in the process. For this reason we devote the following sections to ad hoc methods designed to counterbalance this familiar drawback of depth-first searches. Note that the implementation of these ad hoc methods is significantly facilitated by the fact that transfers are set sequentially.

Additional features

In this section, we propose additional features that can easily be integrated into the branching algorithm proposed in Section 4.1.2. We first propose two lower bounds for the problem, then we describe three techniques for breaking the symmetries that are inherent in our approach.

Lower bounds

In this subsection we propose some lower bounds of the delivery length λ i (φ) corresponding to the different recipient nodes i ∈ R, and consequently some lower bounds of the dissemination length λ(φ) of a transfer plan φ.

Let us first consider the following proposition.

Proposition 4.1

Let i ∈ R be a recipient node and α = u -|O i | be the number of datum units that node i has to obtain during a transfer plan. Let σ x ∈ σ be the α th contact σ c = (s c , i) ∈ σ during which a datum unit k ∈ D\O i can be transferred to node i -i.e. such that variable x k,c is not set to 0. If this index does not exist (e.g. if it remains less than α contacts fulfilling the condition), we consider that x = ∞. x is a valid lower bound for λ i (φ) and λ(φ) -i.e. λ ≥ λ i ≥ x.

This lower bound can be enhanced by checking whether a valid assignment between available transfers and required datum units exists. This point may be illustrated by considering a recipient node i ∈ R that must receive units 1, 2, 3 (α = 3) and for which the following contacts are available:

domains σ c x 1,c x 2,c x 3,c σ 3 = (s 3 , i) {0, 1} {0, 1} {0, 1} → φ(3) ∈ {∅, {1}, {2}, {3}} σ 5 = (s 5 , i) {0, 1} {0} {0} → φ(5) ∈ {∅, {1}} σ 8 = (s 8 , i) {0, 1} {0} {0} → φ(8) ∈ {∅, {1}} σ 9 = (s 9 , i) {0} {0, 1} {0, 1} → φ(9) ∈ {∅, {2}, {3}}
Any contact σ c , c ∈ {3, 5, 8, 9}, is such that there exists a unit k ∈ D\O i for which variable x k,c is not set to 0. Thus Proposition 4.1 states that delivery length λ i (φ) ≥ 8. However, it is clear that there is no transfer plan enabling node i to receive datum units 1, 2 and 3 using only contacts σ 3 , σ 5 and σ 8 . In the best case, node i receives one unit from among {2, 3} during contact σ 3 and unit 1 during contact σ 5 or σ 8 . Even so, node i still has to receive at least one datum unit from among {2, 3} during contact σ 9 . In fact, delivery length λ i (φ) is necessarily greater than or equal to 9, since there is no valid assignment of transfers φ(3), φ [START_REF] Belblidia | PACS: Chopping and shuffling large contents for faster opportunistic dissemination[END_REF] and φ [START_REF] Bocquillon | Data Transfer in Delay-Tolerant Networks[END_REF] enabling node i to receive datum units {1, 2, 3}, cf. Let i ∈ R be a recipient, and σ i ⊆ σ be the subsequence of contacts that is built by considering only contacts σ c = (s c , i) ∈ σ during which a unit k ∈ D\O i can be transferred to node i (such that variable x k,c is not yet fixed to 0). Let σ x ∈ σ i denote the first contact from which -by adding the contacts of σ i one after the other -there exists an assignment of the transfers which leads to the delivery of all the units to node i. If such an index x does not exist, then we consider that x = ∞. x is a lower bound for λ i (φ) and λ(φ), i.e. λ ≥ λ i ≥ x.

The computational investment required to compute this lower bound gives a particularly good return when the number of datum units is high, but the weaker bound defined in Proposition 4.1 usually gives good results too -cf. Section 4.3 for a comprehensive comparison between these lower bounds.

Another lower bound can be derived from the proof of polynomiality that we proposed in Section 2.2.2 for the case -called the delivery problem -where there is only one recipient node, i.e. |R| = 1. Given a recipient node i ∈ R, the optimal solution which can be computed for the problem where node i is the unique recipient, is a lower bound for delivery length λ i (φ) in the original problem. Unfortunately this lower bound is weak in practice. Transforming the problem into a flow problem implies relaxing the "identity" of the datum units (a unit of flow is not associated with a specific unit). This prevents us using information collected during the search (e.g. the values of the variables) to constrain the admissible flows.

Symmetry-breaking techniques

The efficiency of the search can be improved by breaking the symmetries that are inherent in our approach. The search space we consider contains a large number of equivalent transfer plans that should be ignored. For this purpose we propose new dominances rules.

Symmetric transfer plans

Let us consider the example on the top of Figure 4.2. At time t = 3, datum units 1 and 2 share the same sources (nodes 1, 2 and 3) -i.e. ∀i ∈ N , 1 ∈ O 3 i if and only if 2 ∈ O 3 i . Thus, the role of these datum units can be swapped in the rest of the sequence, as shown in the bottom half of the figure. In other words, the sub-branchings (in the evolving graph) corresponding to units 1 and 2, and associated with the contacts occurring after σ 3 , can be swapped. The dissemination length is not affected by this operation. So it is sufficient to consider one option (φ(4) = {1} or φ(4) = {2}) out of the two to solve the dissemination problem, e.g. we can arbitrarily decide to transmit the datum unit with the lowest index first. This can be formalized as follows.

Definition 4.2 -extension of a partial transfer plan

Let φ t be a partial transfer plan of length t ∈ {0, 1, . . . , m}, and X refer to its domain. The extension Λ(φ t ) of φ t denotes the set of valid transfer plans φ such that ∀c ∈ X, φ(c) = φ t (c).

Proposition 4.3

Let t ∈ {0, 1, . . . , m} be a time index, and φ t be a partial transfer plan of length t. Let k 1 and k 2 ∈ D be two datum units (such that k 1 < k 2 ). If k 1 and k 2 are possessed by the same nodes after the first t contactsi.e. k 1 ∈ O t i (φ t ) if and only if k 2 ∈ O t i (φ t ) for all nodes i ∈ N -then the set Φ 1 of transfer plans φ 1 ∈ Λ(φ t ) such that φ 1 (t + 1) = {k 1 } dominates the set Φ 2 of transfer plans φ 2 ∈ Λ(φ t ) such that φ 2 (t + 1) = {k 2 }.

Proof. Let φ 2 be a valid transfer plan in Φ 2 . We prove there exists a transfer plan better than or equivalent to φ 2 in subset Φ 1 . To this end, we consider a copy φ 1 of φ 2 , where we set φ 1 (c) = {k 1 } for all c ∈ {t, . . . , m} | φ 2 (c) = {k 2 }, and φ 1 (c) = {k 2 } for all c ∈ {t, . . . , m} | φ 2 (c) = {k 1 }. Transfer plan φ 1 thus belongs to Φ 1 (the role of k 1 and k 2 have been swapped after σ t ). Let us now prove that φ 1 has the same dissemination length as φ 2 . First, it will be noted that k ∈ O c i (φ 2 ) and k ∈ O c i (φ 1 ) are obviously equivalent for any other unit k ∈ D\{k 1 , k 2 }, any node i ∈ N , and at any time c ∈ {0, . . . , m}. We would like to show that

k 1 ∈ O c i (φ 2 ) is equivalent to k 2 ∈ O c i (φ 1 )
. This is obvious in the case of c ≤ t. We then assume it holds at a time c > t, and we consider the situation at time c + 1.

If

i = r c+1 , then k 1 ∈ O c+1 i (φ 2 ) ⇒ k 1 ∈ O c i (φ 2 ) ⇒ k 2 ∈ O c i (φ 1 ) ⇒ k 2 ∈ O c+1 i (φ 1 ). 2. If i = r c+1 , then k 1 ∈ O c+1 i (φ 2 ) ⇒ k 1 ∈ O c i (φ 2 ) ∪ φ 2 (c + 1
) and so:

(a) if k 1 ∈ O c i (φ 2 ), then k 2 ∈ O c i (φ 1 ) ⇒ k 2 ∈ O c+1 i (φ 1 ); (b) if {k 1 } = φ 2 (c + 1), then {k 2 } = φ 1 (c + 1) ⇒ k 2 ∈ O c+1 i (φ 1 ).
In the same way, we can prove that

k 2 ∈ O c+1 i (φ 1 ) ⇒ k 1 ∈ O c+1 i (φ 2 )
-which demonstrates the result by recurrence. Finally we can prove that

k 2 ∈ O c i (φ 2 ) is equivalent to k 1 ∈ O c i (φ 1 ). Therefore O λ i (φ 1 ) = O λ i (φ 2
) always holds at time λ = λ(φ 2 ) and consequently λ(φ 1 ) = λ(φ 2 ).

In practice -Proposition 4.3 can be applied at each node of the search tree. Given a sequential branching algorithm like that described in Section 4.1.2, every node defines one partial transfer plan φ t of size t (t being the number of transfers that have been set during the search, from the root to the node we consider in the search tree). Thus, if T = { k ∈ D | x k,t+1 is not set to 0 } denotes the set of units that could be transferred during contact σ t+1 , we can check whether two units k 1 and k 2 ∈ T (with k 1 < k 2 ) have the same source nodes. If so, the proposition allows us to remove k 2 from T (variable x k 2 ,t+1 can be set to 0). As the branch where x k 1 ,t+1 = 1 (i.e. the subset of transfer plans Φ 1 ⊆ Λ(φ t ) such that φ(t + 1) = {k 1 }) will be explored, we can ignore the branch where x k 2 ,t+1 = 1 (the set of transfer plans Φ 2 ⊆ Λ(φ t ) such that φ(t + 1) = {k 2 }) can be ignored.

Remark 4.2

In the trivial case where only one source node s ∈ N possesses the whole datum at the outset -i.e. O s = {1, 2, . . . , u} and ∀i ∈ N \{s}, O i = ∅this proposition means we only need to consider one transfer plan out of u! during the search. For each transfer plan, that is for each subset of u arc-disjoint branchings of the evolving graph, we can find u! symmetrical transfer plans by permuting the assignments of each datum unit to the branchings. Proposition 4.3 ensures that the branchings are assigned to the units according to their indexes (other permutations are ignored).

Consecutive transfers

Let us now turn to the example shown on the left half of Figure 4.3. Node 3 is the recipient in contacts σ 1 = (1, 3) and σ 2 = (2, 3), but has no opportunity to transmit data to a third node between these contacts. Therefore, the order in which datum units are sent to node 3 during these contacts is not relevant (if we assume that both are improving) -i.e. O 3 2 = {1, 2} if φ(1) = {1} and φ(2) = {2}, or if φ(1) = {2} and φ(2) = {1}. So, to prevent such symmetries from expanding the search space, we propose considering only transfer plans where the datum units are transmitted in the order of their indexes, i.e. such that φ(1) = {1} and φ(2) = {2}. This can be formalized as follows.

Proposition 4.4

Let i ∈ N be a node. Let k 1 , k 2 ∈ D denote two datum units such that k 1 < k 2 . One assumes there are two contacts σ x1 and σ x2 ∈ σ (x1 < x2) with r x1 = r x2 = i, between which node i has no opportunity to transfer data, i.e. ∃y ∈ {x1, . . . , x2} with s y = i. Among the valid transfer plans such that Proof. Let φ 2 ∈ Φ 2 be a transfer plan such that

k 1 ∈ O x1-1 s x1 ∩ O x2-1 s x2 \O x2-1 r x2 and k 2 ∈ O x1-1 s x1 ∩ O x2-1 s x2 ,
k 1 ∈ O x1-1 s x1 ∩ O x2-1 s x2 \O x2-1 r x2 ; k 2 ∈ O x1-1 s x1 ∩ O x2-1 s x2 ; φ 2 (x1) = {k 2 }; and φ 2 (x2) = {k 1 }.
We build a transfer plan φ 1 ∈ Φ 1 by copying φ 2 , and by setting φ

1 (x1) = {k 1 } and φ 1 (x2) = {k 2 }. Note that φ 1 is valid, since φ 2 is valid, k 1 ∈ O x1-1 s x1 and k 2 ∈ O x2-1 s x2 . Moreover, we have λ(φ 1 ) = λ(φ 2 ) ≥ x2 since k 1 / ∈ O x2-1 r x2 .
In is also necessary for that transfer to be minimal.

(x1) = {k 2 }), transfer φ(x2) = {k 1 } can be blocked if k 2 ∈ O x2-1 s x2 . 3 1 2 {1, 2} {1, 2} O 2 3 = {1, 2} 3
1 2 {1, 2} {1, 2} 1 4 2 3 {2, 3} {1, 2, 3} 5
{1, 2, 4} {1, 3} φ(3) ∈ {{1}, & & {2}, {4}} φ(4) ∈ { & & {1}, & & {3}} → ∅ φ(1) = {1} φ(2) = {2} φ(1) = {2} φ(2) = {1} φ(1) = {2} φ(2) = {3}
This can be automated simply by adding the following constraint in each of these branches:

∀k 1 ∈ {1, 2, . . . , k 2 -1} ∩ T, [ y s,k 2 ,t = 1 =⇒ x k 1 ,x2 = 0 ] (with s = s x2 and t = T s (x2 -1))
The use of such constraints cannot be avoided, since the state

O x2-1 s x2
is not fixed when the value of transfer φ(x1) is being decided. Moreover, when several contacts σ x2 fulfil the above conditions, we need to post the constraints for each possibility. If we look at the instance shown on the half right of Figure 4.3, x2 = 3 and x2 = 4 both need to be considered when we set φ(2) = {3}. Finally, note that the case where φ(3) = {1} cannot be ignored, because no swap will be possible between transfers φ(2) and φ(3) (node 3 will not be in possession of datum unit 3 when σ 3 will occur).

Further research could include trying to detect other symmetry patterns, e.g. we could attempt to detect that the transfer plans such that φ(1) = {2}, φ(2) = {1}, φ(3) = {4} and φ(4) = {3} maximize the number of datum units received by node 5 throughout these four contacts, while ensuring that as far as possible the units are transferred in the order of their indexes. This way, more transfers could be arbitrarily set, and fewer transfer plans would need to be considered during the search.

Nogood recording

The final technique for breaking symmetries that we propose in this chapter involves registering the state of the nodes visited throughout the search. This enables branches to be pruned by detecting dominance relationships among transfer plans.

(c) = φ 2 (c). It is assumed that O t i (φ 2 ) ⊆ O t i (φ t 1 ) = O t i (φ 1 )
for all the nodes i ∈ N . We thus consider that O c i (φ 2 ) ⊆ O c i (φ 1 ) for a time index c ∈ {t+1, . . . , m -1}, and let us examine the situation at index c + 1.

1. If i = r c+1 , then O c+1 i (φ 2 ) = O c i (φ 2 ) ⊆ O c i (φ 1 ) = O c+1 i (φ 1 ). 2. If i = r c+1 , then O c+1 i (φ 2 ) = O c i (φ 2 ) ∪ φ 2 (c + 1) ⊆ O c i (φ 1 ) ∪ φ 1 (c + 1) = O c+1 i (φ 1 ).
Consequently, we have proved by recurrence that O c i (φ 2 ) ⊆ O c i (φ 1 ) holds for all indexes c ∈ {t, . . . , m}. The validity of φ t 1 and φ 2 therefore results in the validity of φ 1 . Moreover -since t ≤ λ(φ t 1 ) -we also have t ≤ λ(φ 1 ) = λ and O λ r (φ 2 ) ⊆ O λ r (φ 1 ) for all the recipient nodes r ∈ R. So, λ(φ 1 ) ≤ λ(φ 2 ).

In practice -at every node of the search tree, and after having set the new transfer φ t 2 (t), we also save the corresponding global-state ).

S curr t = {O t i | i ∈ {1,
Such a symmetry-breaking technique falls within the well-known nogood recording framework, which was first introduced by Schiex and Verfaillie [START_REF] Schiex | Nogood Recording for static and dynamic constraint satisfaction problems[END_REF]. The major drawback of such an approach is the huge number of global states that can be generated, and thus recorded. An easy way of managing this is to implement lists L t as truncated heaps sorted according to the "cardinal" |S t | = i∈N |O t i (S t )| of the states S t ∈ L t . The intuitive idea is to prioritize the global states that are most likely to include other global states.

Remark 4.3

If the global states are represented with bit vectors, testing whether two sets S 1 t and S 2 t are such that S 1 t ⊆ S 2 t is trivial using boolean operations. This computational efficiency makes it possible to store several thousand global states in each list L t , t ∈ {1, . . . , m}, and thereby to improve the performances of the solver drastically, cf. Section 4.3 for more details.

Three methods have been proposed to break symmetries inherent in our approach. The first two techniques can be qualified as proactive, as both are intended to avoid generating symmetric solutions during the search, whereas the third is more reactive insofar as it aims to detect (and prune) symmetric branches after they have been generated.

Computational results

In this section numerical results are reported and discussed. All experiments were performed in the same conditions as for Chapter 3 (the same instances, the same machine, the same criteria, and still with a one-hour time limit), cf. Section 3.5.1. We used CP-Optimizer, the constraint-programming engine developped by IBM-ILOG. Note that the best results achieved with integer linear programming will serve as a reference for subsequent comparisons.

The model described in Section 4.1 is discussed in Section 4.3.1, and the features proposed in Section 4.2 are evaluated in Section 4.3.2.

About the model

Let us discuss the computational results reported in Table 4.1. These results were obtained using three different algorithms. First min consists in solving the constraint programming model defined by constraints (3.4) through (4.3) (the transfer plan is therefore required to be minimal). Then, min+st/act follows the same approach, but by also considering constraint (4.4) (here the transfer plan is required to be strictly-active, in addition of being minimal). Finally, procedure prep+min+st/act consists in calling the preprocessing procedure defined in Chapter 3 (we only consider the strategies reported in Table 3.8, page 93), followed by min+st/act.

The experimental results reported in Table 4.1 may appear disappointing at first glance, especially compared to those reported in Table 3.8. However, it should be remarked that there is a significant gap between the two model min and min+st/act. This shows that we were successful in implementing the dynamical deduction procedures that were discussed in the conclusion of Chapter 3 -i.e. we managed to integrate fully into the solver the concept of strictly-active transfer plan. This was made possible through the addition of a-variables, and through non-linear constraints (4.4).

Moreover, there is also a clear gap between algorithms min+st/act and prep+min+st/act, showing that the preprocessing procedures we proposed outperform the consistency algorithms implemented in CP Optimizer.

The additional features

In fact, to get the most out of constraint programming, a custom branching algorithm often needs to be implemented. The strategy proposed in Section 4.1.2 is quite easy to implement with CP-Optimizer. As a reminder, transfers are set in the order of the sequence. The search is guided in accordance with a heuristic. If the number of backtracks starts to become unreasonably large, the search is restarted from scratch with the built-in algorithm. In this case, the solver is notified that the x-variables are the decision variables and that they should be given priority during the branching. Experimental results are reported in Table 4.2, columns none. Note that the proportion of instances successfully solved is significantly better, but is still not comparable to results obtained with integer linear programming.

To obtain competitive results, we must consider the ad hoc tools described in Section 4.2 -namely the weak (wlb) and the strong (slb) lower bounds, the proactive symmetry-breaking techniques (sym) and/or the nogood-recording (ngr), cf. Tables 4.2 through 4.4.

Lower bounds -wlb and slb have positive effects on the efficiency of our algorithm. They enable the solver to prune some branches earlier. The weak lower bound provides better results for the first two groups -i.e. the smallest instances -than for the third group; and, conversely, the strong lower bound provides better results for the third group -i.e. the hardest instances -than for the first two groups. As is often the case, there is a balance to be struck between on the one hand heavy computations but tight bounds, and on the other light computations but weak bounds.

Symmetry-breaking techniques -ngr and sym enable the search space to be significantly reduced at a low computational cost. The numerical results show that both operate well across all classes.

In summary, algorithm sym+ngr+wlb should be used on the first two groups. sym+ngr+slb is more suitable for large instances, cf. 4.5 -The algorithms that obtained the best results with CP Optimizer.

Conclusion

In this chapter we proposed an algorithm based on constraint programming for solving the dissemination problem. It outperforms our previous algorithm, with a better heuristic branching algorithm and some extensions -i.e. some lower bounds and some symmetry breaking techniques.

Table 4.6 shows the best computational results achieved so far, for every class and across Chapters 3 and 4.

In the next chapter we plan to investigate several methods for solving the dissemination problem in an uncertain context. This implies studying robust optimization in order to find transfer plans which remain valid when not all transfers are successful.

Robust optimization

R obust optimization is an approach to optimization problems affected by uncertainty. In this chapter one will seek a transfer plan which ensures the delivery of each datum unit to all recipients when a given number Γ ≤ m of transfers might fail. First we will formalize this new problem, focusing particularly on the differences with the original problem (cf. Section 5.1). Thereafter we will propose a necessary and sufficient condition for a transfer plan to be "robust". This will finally lead to a branching algorithm (cf. Section 5.2), implemented in practice with constraint programming (cf. Section 5.3). In the previous chapters, the dissemination problem has been addressed for the case where transfers cannot fail. We now propose to tackle a variant where failures might occur. We would like to find transfer plans during which every datum unit is correctly delivered to all recipient nodes, regardless the failures scenario. Of course, by "failure" we mean anything which prevents a transfer to terminate successfully -e.g. link problems, battery depletions, ... In this way, we hope to cover a wide range of real applications. In practice, we will assume that at most Γ ∈ N transmissions can fail during a scenario, following the well known approach proposed by Bertsimas and Sim [START_REF] Bertsimas | The Price of Robustness[END_REF].

The present chapter is organized as follows. In Section 5.1, we extend the formulation of dissemination problem to the robust optimization case. Then, in Section 5.2, we propose an enumeration algorithm to find all valid robust solutions. This algorithm is integrated into a constraint-programming solver (like in Chapter 4) in Section 5.3, and finally assessed in Section 5.4.

The robust dissemination problem

In this section, we generalize the formulation of the dissemination problem to the case where one considers failures. In addition, we show that these two problems (the robust and the non-robust problems) are different.

Formal description

The robustness criteria may depend on numerous parameters (the intended applications, the environment, ...). In this chapter, we consider a parameter, Γ ∈ N, to characterize the minimum "level" of robustness the solution has to guarantee. The problem is to compute a "Γ-robust" transfer plan minimizing the dissemination length, i.e. a transfer plan ensuring that the recipient nodes are served if at most Γ failures occur.

Formally, a scenario of Γ failures is a function S : {1, 2, . . . , m} → {0, 1} such that m c=1 S(c) = Γ. In fact, S(c) = 1 indicates that contact σ c ∈ σ has failed. Therefore, given a scenario S and a transfer plan φ, we can compute the realization of the states O t i (S, φ) (for all nodes i ∈ N and all time indexes t ∈ {0, 1, . . . , m}) as follows:

( (5.1)

1) ∀i ∈ N , O 0 i = O i , (2) ∀c ∈ {1, 2, ..., m} | S(c) = 1, ∀i ∈ N , O c i = O c-1 i , (3) ∀c ∈ {1, 2, ..., m} | S(c) = 0, O c rc = O c-1 rc ∪ [ φ(c) ∩ O c-1 sc ], (
Consequently state O t i (S, φ) denotes the set of datum units possessed by node i at time t when transfer plan φ is used during scenario S.

The delivery length λ Γ i (φ) of node i ∈ N must now indicate the smallest time index at which one can guarantee that i possesses all the datum units, regardless the contacts that fail. Thus, we will now consider:

λ Γ i (φ) = min { t ∈ {0, 1, . . . , m} | O t i (S, φ) = D for any scenario S of at most Γ failures }
In this way, the dissemination length λ Γ (φ) = max i∈R {λ Γ i (φ)} indicates the time index at which we can guarantee that all the recipient nodes possess all the datum units (regardless the contacts that fail).

The robust dissemination problem is to find a transfer plan φ minimizing the dissemination length λ Γ (φ). Note that a transfer plan φ is Γ-robust when λ Γ (φ) = ∞. Only such solutions are admissible for the robust dissemination problem, so an instance can be feasible with a given value of Γ, but infeasible with a greater value of that parameter. In particular, some feasible instances of the dissemination problem (Γ = 0) may become infeasible with respect to the robust dissemination problem (Γ ≥ 1). However, Γ-robust transfer plans are always p-robust for all 0 ≤ p ≤ Γ.

The robust dissemination problem is NP-Hard in the strong sense, since the dissemination problem (a strongly NP-Hard problem) is a special case of the robust dissemination problem where Γ = 0.

Robustness and evolving graphs

Instances of both problems (the dissemination and the robust dissemination problems) can be described by evolving graphs. Let us remind that these are multigraphs whose vertices represent nodes and whose arcs represent a set of connections between these nodes. Each arc is labelled with time intervals which indicate when the corresponding link is active. To appropriately take account of time constraints, the notion of path must be replaced by the notion of journey, i.e. an ordered set of arcs having increasing labels. For our needs, each contact is thus represented by an arc whose label is given by its position in the sequence -cf. Actually, a set of arc-disjoint branchings (in the evolving graph) that are rooted on the source nodes of a given unit k ∈ D, and which globally covers all the recipient nodes, defines a possible store-forward routing to disseminate unit k. For example, in Figure 1.1, the bold arcs form a set of branchings to disseminate datum unit 1 from nodes 1 and 2 to all the other nodes. In the following, such a set of branchings is just named a covering branching, since this actually is one branching if we consider a virtual root node to transmit unit k to the source nodes (1 and 2) at time 0. Therefore -as shown in Section 2.3.1 -solving the dissemination problem (Γ = 0) can be seen as finding u arc-disjoint such covering branchings -i.e. one per datum unit (see the branchings with bold and double arcs).

An intuitive extension to the robust case consists in searching for exactly Γ + 1 arc-disjoint covering branchings per datum unit. The resulting transfer plan (built from the (Γ + 1) × u covering branchings) is Γ-robust. It defines how Γ + 1 copies of each datum unit can be routed (along independent and contact-disjoint journeys) to the recipient nodes. This way, Γ failures cannot be enough to prevent a given node to receive a given datum unit.

However, it is worth nothing that this approach is over protective and the existence of (Γ + 1) × u covering branchings is a sufficient, but not necessary, condition for a Γ-robust solution to exist.

Proposition 5.1

The existence of (Γ + 1) × u mutually-arc-disjoint covering branchings in the evolving graph (i.e. Γ + 1 branchings per datum unit) is a sufficient, but not necessary, condition for a Γ-robust transfer plan to exist.

Proof. The condition is sufficient, since Γ failures are not enough to invalidate Γ + 1 arc-disjoint branchings. To prove it is not necessary, we then consider the evolving graph depicted in Figure 2.7 on page 39. We assume that there is only one datum unit, whose the only source is node t, and that all nodes are recipient -i.e.

R = N = {t, a, b, . . . , f} ; D = {1} ; O t = {1} ; and ∀i ∈ {a, b, . . . , f}, O i = ∅.
The valid transfer plan φ such that ∀c ∈ {1, . . . , 12}, φ(c) = {1} is 1-robust -i.e. no single failure can prevent the correct delivery of unit 1. Yet we have already shown that there does not exist two arc-disjoint covering branchings rooted at node t (the source) in this evolving graph.

Note that this proposition justifies the present chapter. Solving the robust case is not equivalent to solve the initial problem by considering Γ + 1 times more datum units.

Robust optimization

In this section, we propose a branching algorithm to enumerate all Γ-robust transfer plans. This procedure is based on a necessary and sufficient condition that will be discussed in the first place. Moreover, we propose a polynomialtime algorithm to check that a given transfer plan is Γ-robust. This branching algorithm will be incorporated into a branch-and-bound procedure described in Section 5.3 (and developed with a constraint programming approach).

Necessary and sufficient condition for a

transfer plan to be Γ-robust

In the worst case, all the failures prevent the same node r ∈ R to receive the same datum unit k ∈ D, i.e. the failures break all the journeys enabling r to receive k. Therefore, to prove that a given valid transfer plan φ is Γ-robust, one can show that for all datum units k ∈ D, and all recipient nodes r ∈ R, the minimum number of contacts which must fail to prevent r from receiving unit k, is strictly-greater than Γ. To this end, for each datum unit k ∈ D and each node r ∈ R, we consider the transportation network G(φ, k, r) = (X, U ) built as follows:

1. First, we add a source vertex src ∈ X and a sink node snk ∈ X.

2.

For each node i ∈ N , we add µ i + 1 nodes {i 0 , i 1 , . . . , i µ i } ⊆ X, where

µ i = |{ σ c ∈ σ | r c = i
}| is the number of contacts whose receiver is i.

3. Next, we add one arc (src, i 0 ) ∈ U for each source node i ∈ N | k ∈ O i , and one arc (r µr , snk) ∈ U . All those arcs have an infinite capacity.

4.

For each node i ∈ N , we add arcs {(i 0 , i 1 ), (i 1 , i 2 ), . . . , (i µ i -1 , i µ i )} with infinite capacities.

5.

For each contact σ c = (i, j) ∈ σ such that φ(c) = {k} -assuming that node i is the receiver of x ∈ {0, . . . , c -1} contacts before σ c -and that σ c is the y th (y ∈ {1, 2, . . . , m}) contact where node j is the receiverwe add an arc (i x , j y ) ∈ U of capacity 1.

Such a graph has been proposed in Section 2.2.2 to prove that the non-robust dissemination problem with one recipient is polynomial and can be reduced to the solving of a max-flow problem. The graph has been slightly simplified as we only consider one datum unit at a time. In Figure 5.1b, we report the flow network G(φ, k = 1, r = 5) associated with the transfer plan φ described in Figure 5.1a. Of course this network can be simplified using the procedure defined on page 33 (cf. Figure 2.6).

Following the proof of Section 2.2.2, we can prove that a src-snk flow in G(φ, k, r) describes a set of arc-disjoint journeys to transmit unit k, from one or several sources, to node r. These journeys are obtained from the saturated arcs representing a contact -i.e. the arcs having a flow and a capacity of 1. Each unit of flow entering vertex snk actually correspond to a journey from a source node to r. Thus, we can assert that Γ failures cannot be enough to prevent node r from receiving unit k during transfer plan φ if the maximum amount of flow traversing G(φ, k, r) is greater or equal to Γ + 1 -i.e. if there are at least Γ + 1 arc-disjoint journeys to deliver unit k to node r.

Formally, this results in the following proposition.

Proposition 5.2

Let φ be a valid transfer plan. φ is Γ-robust if and only if, for all datum units k ∈ D, and all recipient nodes r ∈ R, there exists a src-snk flow of value Γ + 1 in transportation network G(φ, k, r).

Proof. In this proof, we assume that the maximum flow is finite. Indeed, the maximum flow is infinite (and then greater than Γ + 1) if and only if node r is a source (k ∈ O r ) -i.e. if and only if even an infinite number of failure is not sufficient to prevent r to possess k at the end of the sequence.

The condition is obviously sufficient, since Γ failures cannot be sufficient to invalidate the Γ + 1 journeys enabling r to receive k which correspond to a flow having a value of Γ + 1. To show the condition is necessary, we apply the max-flow/min-cut theorem, which states that the maximum amount of flow passing from src to snk in G(φ, k, r) is equal to the minimum capacity of a src-snk cut. Only arcs representing a contact (with a capacity of 1) can belong to such a cut (others have an infinite capacity). Thus, if the capacity of the minimum cut does not exceed Γ, then it exists a scenario with at most Γ failures during which node r will not be able to receive unit k. The failures are given by the minimum cut. Removing all these arcs prevents any flow to pass from src to snk -i.e. this breaks all the journeys enabling r to receive unit k in the evolving graph.

On a practical level, Proposition 5.2 comes to a polynomial time algorithm to check whether a transfer plan is Γ-robust. For each datum unit and each recipient, we solve a max-flow problem in order to verify that there exist at least Γ + 1 mutually arc-disjoint journeys linking a source of this datum unit to this recipient. This test runs in O(u.|R|.(Γ + 1).(n + m)) time. For each pair (k, r) ∈ D × R we need to find Γ + 1 augmenting paths in a graph that contains at most 1 + n + 2m arcs. This result is the basis of the enumeration procedure that we propose in the following section. It enumerates the transfers plans where Γ + 1 journeys link the sources and each recipient node.

Enumeration procedure

The most naive method to enumerate the set of all Γ-robust transfer plans, consists in enumerating the set of all valid transfer plans, and in keeping only Γ-robust solutions -i.e. the transfer plans which guarantee that every node receives the whole datum in any scenario of at most Γ failures. To this end, we can use the branching algorithm proposed in Section 4.1.2 (on page 100). Transfers are set in the order of the sequence σ, from φ(1) to φ(m). At each node of the search tree, the first transfer φ(c) that is not yet set is selected, and one branch is created for each possible value -i.e. one branch for each unit k ∈ O c-1 sc , and one branch for the null transfer. The algorithm proposed in Section 5.2.1 is finally used to filter non-robust solutions.

Unfortunately, such an approach compels us to explore the whole search space. To avoid this, we propose to generalize the dominance rules proposed in Section 3.1 (on page 46).

Robust-minimal transfer plans

In Chapter 3, a 0-robust transfer plan φ is said to be minimal if every transfer φ(c) is either improving (node r c receives a new datum unit, |O c-1 rc | < |O c rc |) or null (no datum unit is transmitted, φ(c) = ∅) -i.e. if no node receives the same datum unit more than once. The set of such transfer plans was shown to be dominant where Γ = 0. Although this dominance rule no longer holds where Γ > 0, it can be generalised. Note that the main idea is still to avoid fruitless transfers.

Definition 5.1

Transfer φ(c) = {k}, c ∈ {1, 2, . . . , m}, k ∈ D, is robust-improving if and only if it improves the "level" of robustness associated with datum unit k and node r c -i.e. the minimum number of failures required to prevent node r c from receiving datum unit k -without, however, exceeding Γ.

In practice, a transfer φ(c) = {k} is then robust-improving if and only if:

1. the maximum amount of flow passing from src to snk in transportation network G(φ, k, r c ) is larger when we consider transfer φ(c), than when we only consider the c -1 first contacts (i.e. when the capacity of the arcs which correspond to a contact σ t with t ≥ c, is set to 0); 2. the value of such a flow does not exceed Γ + 1.

Of course, an improving transfer is also robust-improving.

Definition 5.2 -robust-minimal transfer plan

A transfer plan φ is robust-minimal if all its transfers are null or robustimproving.

In Figure 5.1, transfer φ( 6) is robust-improving, since it "opens" the first journey to node 5. Transfer φ( 7) is not robust-improving, because adding or removing arc (4 1 , 5 2 ) does not increase the amount of flow that can traverse G(φ, 1, 5). If we set φ(7) = ∅, φ becomes robust-minimal. It remains robustminimal if we consider φ(9) = {1} (since φ( 9) is robust-improving).

Proposition 5.3

The set of robust-minimal transfer plans is dominant.

Proof. Let φ be a valid non-robust-minimal transfer plan. So there exists at least one transfer φ(c) which is neither null, nor robust-improving. Therefore the transfer plan φ -obtained by copying φ and by setting φ (c) = ∅ -has the same dissemination length than φ -i.e. λ Γ (φ ) = λ Γ (φ). This process is to be repeated as long as the new transfer plan is not robust-minimal.

Robust-strictly-active transfer plans

Given the definition of a robust-improving transfer, the concept of strictlyactive transfer plan can be generalised straightforwardly. The idea remains to prevent postponement of improving (robust-improving) transfers.

Definition 5.3 -robust-strictly-active transfer plan

A transfer plan φ is robust-strictly-active if and only if all transfers are robust-improving when possible -i.e. ∀c ∈ {1, . . . , m}, if ∃k ∈ O c-1 sc such that φ(c) = {k} is robust-improving, then φ(c) is robust-improving.

Proposition 5.4

The set of strictly-active transfer plans is dominant.

Proof. Let φ be a non-robust-strictly-active transfer plan -i.e. there exist a non-robust-improving transfer φ(c), c ∈ {1, . . . , m}, and a datum unit k ∈ D such that φ(c) = {k} would be robust-improving. Let then φ be the transfer plan obtained by copying φ, and by setting φ (c) = {k}. The dissemination length of φ is always better than or equal to the dissemination length of φi.e. λ Γ (φ ) ≤ λ Γ (φ). Of course, this process must be repeated as long as the new transfer plan is not robust-strictly-active.

Proposition 5.5

The set of robust-minimal and robust-strictly-active transfer plans is also dominant (by combining the above proofs).

Enumerating robust transfer plans

Proposition 5.5 states that enumerating robust-minimal and robust-strictlyactive transfer plans is sufficient to solve the robust dissemination problem (i.e. other transfer plans can be ignored). Therefore -if we use a sequential branching algorithm -we can skip all the branches that correspond neither to a null transfer, nor to a robust-improving transfer.

At each node of the search tree, the earliest transfer φ(c) that is not yet set is selected, and one branch is created for each possible transfer φ(c) = {k} (k ∈ O c-1 sc ) that "opens" a new journey from a source of k to node r c . If no such a transfer exists, then φ(c) is set to ∅. A transfer plan then is Γ-robust as soon as every recipient node has received Γ + 1 copies of each unit.

If we keep the flows (used to check that all transfers are robust-improving) from one node to another during the search, testing whether a given transfer is robust-improving then takes O(n + m) time, because only one iteration of the Ford-Fulkerson [START_REF] Ford | Maximal flow through a network[END_REF] algorithm is required. At most one new journey can be found. Indeed, a single transfer cannot enable two or more new journeys to be found at the same time.

Remark 5.1

In practice, we store only one flow network in memory. The graph defined in Section 5.2.1 has a structure that essentially depends on the instance we consider. In particular, only the capacities vary between two graphs G(φ 1 , k 1 , r 1 ) and G(φ 2 , k 2 , r 2 ) (the capacities only depends on the partial transfer plan, the datum unit and the node we consider). Therefore only the capacities -associated with each unit k ∈ D and each node i ∈ Nand the resulting flows must be stored in a reversible (i.e. backtrack-able) data structure. The structure of the graph itself can be static.

A constraint programming approach

In this section, we implement the scheme proposed in Section 5.2 for solving the robust dissemination problem. We use constraint programming, and take advantage of pre-implemented tools to easily develop a complete branch-andbound procedure. Moreover, we propose ad hoc methods (e.g. lower bounds) to speed up the solving of the problem.

Model

The model proposed below is an update of the model proposed in Chapter 4 for the case Γ = 0. All transfers are required to be robust-improving. Thus, every recipient node r ∈ R must receive exactly Γ + 1 copies of each datum unit k ∈ D. At the outset, we assume that r possesses Γ + 1 (resp. 0) copies of k if k ∈ O r (resp. k / ∈ O r ).

As a reminder, for each node i ∈ N is defined T i , the set of time indexes at which the state of i can change, i.e. T i = {0} ∪ {c ∈ {1, 2, . . . , m} | r c = i}. In addition, ∀t ∈ {0, 1, . . . , m}, we refer by T i (t) to the last contact occurring before time t where node i is the receiver, i.e. T i (t) = max {t ∈ T i | t ≤ t}.

The variables of our model are defined as follows:

• ∀k ∈ D, ∀c ∈ {1, . . . , m}, x k,c = 1 if datum unit k is transmitted from node s c to node r c during contact σ c , and x k,c = 0 otherwise.

• ∀i ∈ N , ∀k ∈ D, ∀t ∈ T i , y i,k,t indicates the number of copies of datum unit k possessed by node i after contact σ t . Thus, the domain of these variables is {0, 1, . . . , Γ + 1}. See Remark 3.8 on page 82.

• ∀c ∈ {1, . . . , m}, a c = 1 if transfer φ(c) is robust-improving, and a c = 0 otherwise.

• ∀i ∈ N , ∀k ∈ D, variable λ i,k represents the delivery length associated with datum unit k and node i -i.e. the date from at node i possesses Γ + 1 copies of datum unit k. Its domain is T i ∪ {∞}. λ i,k = ∞ means that node i does not recover unit k during the transfer plan. In practice we consider that ∞ = m + 1.

• ∀i ∈ R, variable λ i = max k∈D {λ i,k } then represents the delivery length of recipient node i -i.e. the date from which node i possesses all datum units in any scenario of at most Γ failures. Its domain is T i (because i has to be served).

• Finally, variable λ = max i∈R {λ i } represents the dissemination length of the transfer plan. Its domain is therefore i∈R T i ⊆ {0, 1, . . . , m}.

Minimizing the dissemination length leads to the following objective.

λ * = min λ (

The constraints are written as follows (note that these constraints alone are not sufficient to ensure that the transfer plan is Γ-robust):

• Each node i ∈ N initially possesses a subset O i of datum units: • λ i,k is the delivery length associated with datum unit k and node i: is not yet fixed -is selected.

∀i ∈ N ,
2. Next, one branch is created for each robust-improving transfer -i.e. for each datum unit k ∈ O c-1 sc , if transfer φ(c) = {k} is robust-improving, then one adds a branch where x k,c = 1 and ∀p ∈ D\{k}, x p,c = 0.

3. If no robust-improving transfers have been found, then φ(c) is set to ∅ -i.e. ∀k ∈ D, we set x k,c = 0.

To check whether a given transfer is robust-improving, we use the test defined in Section 5.2.2. Note that the capacities of the transportation network are given by the x-variables for transfers occurring before φ(c), and must be set to 0 for other transfers.

In this way, we ensure that the transfer plan is Γ-robust (because other constraints ensure that each recipient receives Γ + 1 copies of each unit).

In addition, this approach ensures that the transfer plan is robust-minimal (every transfer is either null or robust-improving), and robust-strictly-active (because robust-improving transfers cannot be postponed).

Remark 5.2

A transfer φ(c) = {k} is necessarily robust-improving if there exist more arc-disjoint journeys from a source of datum unit k to node s c than from a source of k to node r c . Consequently, in such a case, no flow has to be computed and one can set a c = 1. In practice, note that constraint (4.4) can be used (cf. page 100).

Additional features

As regards the robust dissemination problem, key concepts and models have been discussed. However, like in Section 4.2, ad hoc algorithms can speed up the solving process. Below we propose an additional propagation procedure, and adaptations of the techniques developed for the case where Γ = 0.

Look-ahead

In some circumstances, the propagation engine can reveal necessary transfers even before the sequential branching algorithm have to chose a value for those transfers (by combining some constraints of the model). The corresponding x-variables are then set to 1. For example, on Figure 5.2a, the solver might deduce that φ(6) = {1} and φ(9) = {1} at the start (since there are only two contacts left for sending the two required copies of unit 1 to node 6).

In the following, we study such a situation. Formally, we assume the first t ∈ {0, . . . , m -1} transfers have been set. Thus, φ(t + 1) is the first unfixed transfer. We then consider a transfer φ(c) = {k}, c ∈ {t + 2, . . . , m}, k ∈ D, that has been set by a third propagation procedure.

Unfortunately, we cannot guarantee, at this stage, that transfer φ(c) will necessarily be robust-improving, or even that a dominant solution such that transfers φ(c) is robust-improving exists. This may depend on some transfers φ(x), x ∈ {t + 1, . . . , c -1}, which are not yet set. However, we can already check that φ(c) has a chance of being robust-improving. To this end, we use the transportation network G(φ, k, r = r c ) (cf. Section 5.2.1) restricted to:

1. all contacts σ x , x ≤ t, such that x k,x = 1, i.e. such that φ(x) = {k}; 2. contacts σ x , x ∈ {t + 1, . . . , c}, such that r x = r c and x k,x = 1 (because we must show that these contacts can be robust-improving);

3. contacts σ x , x ∈ {t + 1, . . . , c -1}, such that r x = r c and x k,x is not set to 0, i.e. such that φ(x) might/must be equal to {k}.

In fact, we consider the transportation graph associated with the hypothetical transfer plan φ where all the available contacts are leveraged for transmitting unit k. Obviously, if we cannot find enough arc-disjoint journeys with such a transfer plan -that is, if we cannot find one augmenting path in this flow network for each contact σ x , x ∈ {1, 2, . . . , c}, such that r x = r c and x k,x = 1 -then no dominant solution can be computed (developed) from this node of the search tree (the transfers towards node r c cannot all be robust-improving at the same time). If so, a backtrack must be triggered immediately.

If we look back at Figure 5.2a, the corresponding transportation network is given in Figure 5.2b. Contacts σ x , x ∈ {1, 2, 3, 4, 5, 7, 8}, may be used for transferring unit 1 to node 6, so the capacity of the arcs associated with these contacts is 1. Conversely, contact σ 10 will be used for sending datum unit 2 to node 5, so the capacity of arc (3 1 , 5 2 ) is set to 0 (this arc is removed from the flow network). We can find an augmenting path for transfer φ( 6) and for transfer φ(9) (the two transfers fixed in advance) : [ src, 1 0 , 2 3 , 4 1 , 6 1 , 6 2 , snk ] and [ src, 1 0 , 2 1 , 2 2 , 2 3 , 5 1 , 6 2 , snk ]. Thus we cannot prune this branch.

Remark 5.3

Note that contacts σ x , x ∈ {t+1, . . . , c-1}, such that r x = r c and x k,x is still free (neither set to 0, nor set to 1), are ignored (we set the capacity of the corresponding arcs to 0). In fact, considerings these contacts would over-constrain the flow, because we would have to find augmenting paths for transfers that are not required to be robust-improving.

In practice, it may be hard to prune a node in such a way, because there may be many available contacts, and therefore potentially many augmenting paths. Nevertheless, computing these maximum flows also provides valuable information regarding the possible transfers. More specifically, any arc that belongs to a minimum cut in the transportation network described above is necessary for the flow to be maximum -i.e. for the transfers fixed in advance to be robust-improving.

In Figure 5.2b, the minimum cut given by the hatched vertices -namely {(2 3 , 4 1 ), (2 3 , 5 1 )} -reveals that we must use contacts σ 5 and σ 7 to transmit datum unit 1 to nodes 4 and 5 respectively. Thus, x 1,5 = 1 and x 1,7 = 1.

Proposition 5.6

Let M = |{ σ x ∈ {1, . . . , c} such that r x = r c and x k,x = 1 }| refer to the required value of a maximum flow in G(φ, k, r c ) (when only considering the contacts listed above).

1. The flow value cannot exceed M (by construction).

2. If the value of a maximum flow is M , then every arc belonging to a minimum cut of G(φ, k, r c ) corresponds to a contact during which datum unit k must be transmitted.

3. Finally, if the value of a maximum flow is lower than M , then the current branch cannot lead to a dominant solution.

Proof. (item.2) Let C be a minimum cut in G(φ, k, r c ). Let a ∈ C be an arc of that cut. We assume that there exists a dominant transfer plan (developed from the current node in the search tree) such that the contact corresponding to arc a is not leveraged for transferring datum unit k. Therefore, there is a flow of value M in G(φ, k, r c ) -{a} (i.e. the graph obtained after removing arc a in G(φ, k, r c )). This flow is maximum. Yet, C -{a} is a cut of capacity M -1 in graph G(φ, k, r c ) -{a} -which contradicts the max-flow/min-cut theorem.

In practice, we enumerate the minimum cuts with the recursive algorithm proposed by Balcioglu and Wood [START_REF] Balcioglu | Enumerating Near-Min S-T Cuts[END_REF]. Therefore, this propagation procedure runs in O (M (n + m) + K(n + m) 2 ) time, with M = |{ σ x ∈ {1, . . . , c} such that r x = r c and x k,x = 1 }|. K denotes the number of maximum cuts in the flow network. As K may be huge, recursion depth should be limited.

Lower bounds and symmetry-breaking techniques

Almost all ad hoc methods proposed in Section 4.2 can be generalised to the robust case straightforwardly. Actually, almost all proposed methods remain applicable on condition that we consider the datum units and their copiesi.e. on condition that we correctly take into account that each recipient has to receive Γ + 1 copies of each datum unit, instead of one.

For example, the first lower bound becomes: Proposition 5.7

Let i ∈ R be a recipient node, and α = (Γ+1)×(u-|O i |) be the number of datum units (including copies) that i has to receive during a transfer plan. Let σ x ∈ σ denote the α th contact σ c = (s c , i) during which a unit k ∈ D\O i can be transferred to node i (i.e. such that variable x k,c is not set to 0). If this index does not exist (if it remains less than α contacts fulfilling the condition), we consider that x = ∞. x is a lower bound for λ Γ i (φ) and λ Γ (φ) (λ ≥ λ i ≥ x in the model).

For further details, we refer to Section 4.2 at page 102. Note that one can still use the lower bound defined in Proposition 4.1; the lower bound defined in Proposition 4.2; the symmetry-breaking technique defined in Proposition 4.3; and the nogood-recording technique defined in Propositon 4.5 -that is everything but the symmetry-breaking technique defined in Proposition 4.4 (cf. In Proposition 4.4, page 108, we study the situation where a node is the receiving node in several contacts, without having any possibility to send data to a third node between these contacts. We propose to enforce that datum units are transferred, in such a situation, in order of their index. For instance, in does not lead to the same state -because transfer φ(6) = {1} no longer is robust-improving (the two journeys associated with node 5 and datum unit 1 relies on contact σ 1 ).

Preliminary results

In this section, experimental results are reported and discussed. First of all, we describe our benchmark. The latter is built from the instances generated for the non-robust dissemination problem. Next we study the results obtained with the different algorithms described in Section 5.3. All experiments were performed in the same conditions as for Chapters 3 and 4 -i.e. on the same machine, with the same parameters and the same one-hour time limit.

About the benchmark

In order to generate hard instances, we used the instances generated for the dissemination problem, cf. Section 3.5.1 at page 85. Given Propositions 5.1 and 5.2, one can expect an instance of the robust dissemination problem to be as difficult as an instance of the dissemination problem characterised by about Γ times more units (if we keep constant the number of nodes and the number of contacts). Consequently, we propose to reuse the instances generated for the dissemination problem, by reducing the number of datum units in such a way that the old number of datum units is of the same order of magnitude as (Γ + 1) × u in the new instance. Actually, we must find a well-known compromise:

1. between a larger value of (Γ + 1) × u -feasible transfer plans are harder to be found, but proofs of infeasibility are usually easier;

2. and a smaller value of (Γ + 1) × u -feasible transfer plans are easier to be found, but proofs of infeasibility may be harder.

This compromise must ensure that it is difficult to prove that a transfer plan is optimal.

The new benchmark is described in Table 5.1. As a reminder, the classes are characterised by the number nbinst of instances it contains, the required level of robustness Γ, the number of datum units u, and the number of nodes n of these instances. The average number rec of recipients i ∈ R, the average number src of source nodes i ∈ N such that O i = ∅, and the average number m of contacts in every class are also reported. In column from, we indicate the classe(s) (originally used for the dissemination problem) from which the new instances are built (for the robust dissemination problem). Table 5.1 -The benchmark generated for the robust dissemination problem.

Conclusion

In this chapter, we addressed the problem of finding a Γ-robust transfer plan, i.e. a valid transfer plan which guarantees that the recipient nodes correctly receive all datum units, even if some transfers (at most Γ) fail. We hope that this approach will manage to cover a wide range of constraints that are to be found in real applications.

We proposed an algorithm based on constraint programming. This relies on a necessary and sufficient condition for a transfer plan to be Γ-robust, cf. Proposition 5.2. Note, moreover, that this algorithm is an adaptation of the procedure proposed in Chapter 4 for the original dissemination problem.

Finally, promising results were reported. It appeared that specific ad hoc propagation algorithms -e.g. some lower bounds -are required for the model to be efficiently solved (even more than before).

Contents 1 . 1 2 1. 2 3 1. 3 6 1. 4

 11223364 Challenged internets . . . . . . . . . . . . . . . . Delay-tolerant networks . . . . . . . . . . . . . . Systems of systems . . . . . . . . . . . . . . . . . The dissemination problem . . . . . . . . . . . . 8

Figure 1 . 1 -

 11 Figure 1.1 -The dissemination problem (an example).

Figure 2 . 1 -

 21 Figure 2.1 -The Dt2u instance associated with the 3-Sat instance given on page 17.

Figure 2 . 2 -

 22 Figure 2.2 -The set of nodes L i (associated with variable x i ), node α 2 , and the corresponding contacts.

Figure 2 . 3 -

 23 Figure 2.3 -The Dt2r instance built from a 3-Sat instance.

  α

Figure 2 . 4 -

 24 Figure 2.4 -The Dt2r instance associated with the 3-Sat instance given on page 17.

Figure 2 . 4 ,

 24 datum unit 1 can be transmitted through contacts [(α 2 , l1

7 : 8 :

 78 c ← 1 ; 9: while c ≤ m and N d < |R| do 10: 11:

20 : 25 :

 2025 if N d = |R| then λ(φ) ← c ; if N d < |R| then 26:

27 : 28 : 31 : 32 :

 27283132 # the remaining transfers are set to ∅. 29: while c ≤ m do 30: φ(c) = ∅ ; c ← c + 1 ; return φ and λ(φ) ;

Figure 2 . 5 -

 25 Figure 2.5 -The transportation network associated with the given instance of the delivery problem.

1 uFigure 2 . 6 -

 126 Figure 2.6 -The simplified transportation network associated with the instance of the delivery problem given on page 29.

  Figure 2.6.

Algorithm 2 . 2 - 5 :

 225 Solving the dissemination problemRequire: An instance of the dissemination problem ; 1: 2: # computation of the initial state. 3: S ← newState() ; 4: for k ← 1 to u do for z = 1 to |R| do S.o[k][z] ← 0 ; 6: for c ← 1 to m do S.φ(c) ← ∅ ; 7: States ← {S} ; 8: 9: # datum unit copies are distributed to initial owners. 10: for k ← 1 to u do 11: for z = 1 to |R| do 12:

14 :

 14 for all S ∈ States do15:

  the ownership of unit copies is transferred through contacts. 22: for c ← 1 to m do 23: States ← ∅ ; 24: for all S ∈ States do 25: for k ← 1 to u do 26: for z = 1 to |R| do 27:

  . At the end of each iteration c ∈ {1, . . . , m}, States contains one state for each possible situation that can arise from contacts [σ 1 , . . . , σ c ]. For this purpose a new set of states States is computed from the set States obtained at the end of the previous iteration. For each S ∈ States and each copy z of each datum unit k, if S.o[k][z] = s c (if a transfer is possible), a new state S ∈ States is created by copying S, and by transferring the ownership of copy z of unit k to node r c (see S .o[k][z] ← r c ). It corresponds to transfer φ(c) = {k}, i.e. S .φ(c) ← {k}.

Figure 2 . 7 -

 27 Figure 2.7 -This counter-example shows Theorem 2.6 no longer holds for evolving graphs.

Figure 2 . 8 -

 28 Figure 2.8 -An instance of the data transfer problem (Dt) and the corresponding Adbeg instance.

  Proof. Let φ be a minimal, non-strictly-minimal, transfer plan. There exists at least one transfer φ(c), c ∈ {1, 2, . . . , m} | r c ∈ N \R, such that φ(c) = {k} (k ∈ D) and ∀c ∈ {c + 1, . . . , m} | s c = r c , φ(c ) = {k} -i.e. a non-recipient node r c ∈ N \R obtains datum unit k ∈ D during contact σ c ∈ σ, but never forwards it. The transfer plan φ obtained by copying φ, and then by setting φ (c) = ∅ has the same dissemination length, i.e. λ(φ ) = λ(φ).

Figure 3 . 1 -

 31 Figure 3.1 -The knowledge collected using dominance-based deduction tools.

  -1} and r t = s c } corresponds to the units obtained by sc during the contacts which precede contact σc In such a graph, an arc between two vertices v φ(c) ∈ V T and v {k} ∈ V D symbolises the fact that node s c ∈ N can transmit datum unit k ∈ D during contact σ c ∈ σ because it has possessed that datum unit from the outset, i.e.

  (a) an instance of the problem ⎧

Figure 3 . 2 -

 32 Figure 3.2 -An instance of the problem, its evolving graph, and finally the corresponding transfer graph.

  defines a possible way to route datum unit k from the source s c 1 to r cp . A solution where φ(c 1 ) = • • • = φ(c p ) = {k} is valid and enables nodes r c 1 , . . . , r cp to obtain datum unit k. More generally, an anti-branching rooted on a unit vertex v {k} ∈ V D describes a routing to disseminate datum unit k ∈ D. It corresponds to a set of branchings in the evolving graph.

Figure 3 . 3 -

 33 Figure 3.3 -The transfer graph and its properties (the instance is given in Figure 3.2).

  a short summary of Sections 3.2.1 to 3.2.3: 1. the transfer graph represents the whole set of valid transfer plans; 2. a spanning subgraph of the transfer graph (described by function χ A ) thus represents a subset of valid transfer plans; 3. a spanning subgraph of the transfer graph which includes at most one arc going out of each vertex represents one valid transfer plan; 4. we limit the search to the sets of anti-branchings (which are rooted on unit vertices) in order to avoid considering equivalent solutions; 5. other properties χ φ + χ D + χ D enable us to refine the subset of transfer plans represented by the transfer graph and χ A .

{4}} =Figure 3 . 4 -Definition 3 . 8 Γ

 {4}}3438 Figure 3.4 -Deduction tools for strengthening the domain χ φ of each transfer.

Algorithm 3 . 1 -

 31 Minimality+Validity consistencyRequire: transfer graph G φ = (V, A, χ A , χ φ , χ D , χ D ) ; Require: the vertex v φ(c) to which we apply these deduction rules ; 1: 2: # consistency rules in accordance with Proposition 3.5. 3: for all k ∈ D do 4:

  computed 8: # line 21 and used line 26. 9: R ← ∅ ; 10: 11: for all v z ∈ Γ( v φ(c)) do 12: 13:

# 18 : 21 :

 1821 consistency rules in accordance with Proposition 3.7.else if ∀{k} ∈ χ φ ( v φ(c)), {k} / ∈ χ φ ( v z) then 19: set χ A ( v φ(c), v z) = {false} ; 20:else add χ φ ( v z) to R ; consistency rules in accordance with Proposition 3.6. 26: for all {k} ∈ χ φ ( v φ(c))\R do remove {k} from χ φ ( v φ(c)) ; 27:

Figure 3 . 5 -

 35 Figure 3.5 -The bottom-up procedure, cf. Proposition 3.8.

Algorithm 3 . 2 - 1 : 2 :

 3212 Bottom-Up consistencyRequire: transfer graph G φ = (V, A, χ A , χ φ , χ D , χ D ) ; Require: the vertex v φ(c) to which we apply these deduction rules ; unmark all vertices ; boolean b ← true ;3: for all v z ∈ Γ( v φ(c)) do 4:

5 :b 6 : 7 :

 567 ← b and bottom-up ( v z, r c , c -1) ; if b = true then 8:

15 :

 15 put a mark on v z ; and return false ;16: 17:

( a )

 a an example of top-down deductive reasoning

Figure 3 . 6 -

 36 Figure 3.6 -The top-down procedure, cf. Proposition 3.9.

1 : 2 :

 12 # the procedure starts at vertex v φ(c) with i = r c and t = c -1. 3: top-down ( v φ(c), r c , c -1) ; 4:

12 : 13 :

 1213 else if bound = | v Z| -1 and r c = i and t = c -1 then 14:# node r c will possess all transfer values v z ∈ v Z after σ c .15:

1 : 2 : 7 :

 127 # the two bounds are evaluated -cf. Subsection 3.3.3 for details.3: min-s ← min-card(V D , s c , c -1) ; max-r ← max-card(V D , r c , c -Proposition 3.9 still holds. 6: if min-s = |V D | then for all v {k} ∈ V D apply χ D ( v {k}, s c ) ≤ c -1 ; 8:9: # Proposition 3.10 is then applied. 10: if min-s > max-r then remove ∅ from χ φ ( v φ(c)) ; 11:

( a )

 a Node 3 has to receive unit 1 before time 3 to forward it to node 4.

2 3Figure 3 . 7 -

 237 Figure 3.7 -The delivery-requirement-based deductive reasoning (Proposition 3.11).

3 : 4 : 5 :

 345 S ← {(i, j) | N j,k = {i}} ; # the bounds are updated in accordance with Proposition 3.11. 6: while S = ∅ do 7: 8:

13 :c#

 13 ≤ χ D ( v {k}, j), and {k} ∈ χ φ ( v φ(c)) stack S is then updated if required.

17

 17

  :

3 : 5 :#

 35 for c : 1 → m do 4: we try to show that all the transfer values possessed by node s c 6:

10 :#

 10 Strict-Activity (G φ , v φ(c)) the redundant transfers are finally removed in accordance13:

14 :

 14 Minimality+Validity (G φ , v φ(c)) the delivery constraints are then propagated as necessary. 19: while at least one change occurs do 20: for all k ∈ D do Delivery-Requirements (G φ , k) ; 21:

Figure 3 . 8 -

 38 Figure 3.8 -An example of transportation network used to evaluate max-card (the instance is given in Figure 3.2 on page 53).

(a) an instance of the dissemination problem 2 1

 2 {1, 2}

Figure 3 . 9 -

 39 Figure 3.9 -An instance of the dissemination problem and the corresponding transfer graph.

  the new transfer graph

Figure 3 . 10 -

 310 Figure 3.10 -A valid transformation for computing min-card({ v φ(1), v φ(3)}, 5, 6).

  and φ(11) = ∅ -proves that node 7 can possess fewer than 2 units at time 11 in a dominant solution. Consequently the best bound is min-card({ v φ(1), v φ(3)}, 7, 11) = 1, e.g. with φ(3) ⊆ O 11 5 and φ(1) ⊆ O 11 5 .

im p li c it e ly ig n o r e dFigure 3 . 11 -

 311 Figure 3.11 -An inconsistent transformation for computing min-card({ v φ(1), v φ(3)}, 7, 11).

  c does not possess (since φ(c) = ∅ and O c rc > O c-1 rc are equivalent in a minimal transfer plan), i.e. ∀k ∈ D, ∀c ∈ {1, . . . , m}, y sc,k,Ts c (c-1) -y rc,k,Tr c (c-1) ≤ k ∈D x k ,c (3.11) Altogether, the model contains 1 + un + m + 4um constraints -including constraints (3.2) through (3.11) (except constraints (3.2-a) through (3.2-c) and constraints (3.7)+(3.8)).

-

  The most trivial model is given in Section 3.4.1. This MILP-based model is defined by equations (3.1) through (3.9), and is labelled std in the following. To decide which constraints from among (3.2), (3.2-a), (3.2-b) and (3.2-c) are most suitable, we compare the four cases, cf.Table 3.1.

Δ

  rem = rem(prep.)

Figure 4 . 1 -

 41 Figure 4.1 -The assignment problem that must be solved to compute the lower bound.

Figure 4 . 1 .

 41 Hence the following proposition. Proposition 4.2

  datum units 1 and 2 can be swapped from contact σ 4 .

Figure 4 . 2 -

 42 Figure 4.2 -A symmetry appears between datum units 1 and 2 when we try to set transfer φ(4).

the subset Φ 1

 1 of transfer plans φ 1 with φ 1 (x1) = {k 1 } and φ 1 (x2) = {k 2 } dominates the subset Φ 2 of transfer plans φ 2 where φ 2 (x1) = {k 2 } and φ 2 (x2) = {k 1 } (the unit with the lowest index is transferred first).

3 4 Figure 4 . 3 -

 3443 Figure 4.3 -When consecutive contacts occur, datum units can be sent in the order of their index.

Table 4 . 1 -

 41 The results achieved with CP Optimizer and different models.

Table 4 . 6 -

 46 The best results achieved so far.

Contents 5 . 1

 51 The robust dissemination problem . . . . . . . . 121 5.1.1 Formal description . . . . . . . . . . . . . . . . . . 121 5.1.2 Robustness and evolving graphs . . . . .

4 )

 4 ∀c ∈ {1, 2, ..., m} | S(c) = 0, ∀i ∈ N \{r c }, O c i = O c-1 i .

Figure 1 .

 1 1 on page 11.

. 6 )••

 6 ∀i ∈ N , ∀k ∈ D | k ∈ O i , y i,k,0 = Γ + 1 (5.2) ∀i ∈ N , ∀k ∈ D | k / ∈ O i , y i,k,0 = 0 (3.5)• The transfer plan must be valid (sending nodes must possess the datum units that they transmit):∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, x k,c ≤ y sc,k,T i (c-1) (3Nodes possess a datum unit from the time they receive it: ∀k ∈ D, ∀c ∈ {1, 2, . . . , m}, y rc,k,T i (c-1) + x k,c = y rc,k,c (3.10) At most one datum unit can be transferred during each contact: ∀c ∈ {1, 2, . . . , m}, k∈D x k,c = a c (4.2)

Figure 5 .

 5 3 and Remark 5.4 for more details).

1 )Figure 5 . 3 -

 153 Figure 5.3 -Symmetry-breaking techniques, consecutive contacts.

Figure 4 . 3 ,

 43 page 109 (Γ = 0), considering [ φ(1) = {1} and φ(2) = {2} ] or [ φ(1) = {2} and φ(2) = {1} ] leads to equivalent states (all nodes possess the same units). Therefore, considering one option among the two is sufficient to solve the problem. Unfortunately, in Figure 5.3 (Γ > 0), the "symmetric" transfer plan [ φ(4) = {2} and φ(5) = {1} ]

Table of contents

 of

	1 The dissemination problem	1

Table 1 . 1 -

 11 State-of-the-Art (a short summary).

  ) represent the fact that clause c 2 is such that c 2 = {x 1 , x2 , xp }, and such that they are the 1 st occurrences of x 1 and x2 , and the (b p ) th occurrence of xp in C.

	.3, contacts (l 2 1 , C 2 ), ( l2 2 , C 2 ) and ( l2bp p , C 2

  represents the current state of node i ∈ N -i.e. o[i] is equal to {1} if node i possesses the datum, or to ∅ otherwise -while N d indicates the current number of recipient nodes which possess the datum. In the first loop, every element o[i] (∀i ∈ N ) is therefore set to O i , while N d is initialized with the number of recipients storing the datum at the outset. In the second loop, contacts are considered in the order of the sequence. During a contact σ c ∈ σ (from c = 1 to m), the datum is transmitted to node r c if needed and if possible, i.e. if o[r c ] = ∅ and o[s c ] = {1}. Of course o[r c ], φ(c), and N d are updated accordingly. This loop terminates if all recipient nodes possess the datum (if N d = |R|), or if the end of sequence σ has been reached. If it stops while N d < |R|, then it means the instance is not feasible. Finally the third loop sets all remaining transfers (if any) to ∅.

	It is worth nothing that Algorithm 2.1 runs in O(max(n, m)) time.

  ) ← {k} ;

	32:	add(States , S ) ;
	33:	if isSolution(S ) then return S .φ ;
	34:	end if
	35:	end for
	36:	add(States, States ) ;
	37:

  B 2 . The only possible course of action is to add arc a 5 to B 1 , and to add arc a 2 to B 2 . Then, we have to put a 6 in one branching, and a 12 in the other one. If a 6 ∈ B 1 and a 12 ∈ B 2 , then a 7 and a 3 have respectively to be in B 1 and B 2 (because a 3 cannot be used after a 10 ). Thus, both arcs a 9 and a 8 can be added in B 1 , but none can be added to B 2 because a 9 cannot be used after a 11 , and a 8 cannot be used after a 12 . The same contradiction arises with a 10 ∈ B 2 and a 11 ∈ B 1 , or with a 6 ∈ B 2 and a 12 ∈ B 1 .

1 , B 2 } has to be a partition of the set A of arcs. a 10 and a 11 cannot be in the same branching, otherwise vertices c, d, e and f could not be reached. Let us assume that a 10 ∈ B 1 and a 11 ∈ B 2 . It means that arc a 4 ∈ B 1 , and a 1 ∈

  3.1 Dominance rules . . . . . . . . . . . . . . . . . . . 46 3.2 Transfer graph . . . . . . . . . . . . . . . . . . . . 51 3.2.1 About the transfer graph . . . . . . . . . . . . . . 52 3.2.2 Transfer graph and subsets of transfer plans . . . . 54 3.2.3 Additional graph properties and complex subsets of transfer plans . . . . . . . . . . . . . . . . . . . 57 3.2.4 Using the transfer graph . . . . . . . . . . . . . . . 59

3.3 Deductive elements . . . . . . . . . . . . . . . . . 59 3.3.1 Finding non-minimal transfer plans . . . . . . . . . 60 3.3.2 Elementary reasonings . . . . . . . . . . . . . . . . 62 3.3.3 Evaluating min-card and max-card . . . . . . . . 74 3.4 Solving the dissemination problem . . . . . . . . 82 3.4.1 Integer linear programming . . . . . . . . . . . . . 82 3.4.2 Additional constraints . . . . . . . . . . . . . . . . 84 3.5 Computational results . . . . . . . . . . . . . . . 84 3.5.1 About the benchmarks . . . . . . . . . . . . . . . . 85 3.5.2 About the models . . . . . . . . . . . . . . . . . . 87 3.5.3 About the preprocessing procedures . . . . . . . . 88 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . 95

  m})

	3:
	4:	# computing the smallest number of transfer values v z ∈ v Z
	5:
	6:	bound ← min-card( v Z, i, t) ;
	7:
	8:

# possessed by node i at time t.

Table 3 . 3 -

 33 Computational results achieved using minimal preprocessings.

		minimal	light	normal	aggr.	maximal
	pre.tl (-s)	25	25	25	600	2400
	do.bottom.up	yes	yes	yes	yes	yes
	do.minimality	yes	yes	yes	yes	yes
	td.range	-	0.50	1.00	1.00	1.00
	sa.range	-	0.15	0.50	1.00	1.00
	dr.limit	2	2	2	4	4
	minc.tl	-	0.06s	0.06s	0.10s	0.10s
	maxc.tl	-	0.20s	0.20s	0.30s	0.30s

Table 3 . 4 -

 34 Computational results achieved using light preprocessings.

			standard	min		min+st/act		efficiency
		name	solved	cpu	solved	cpu	solved	cpu	prep	rem	fcd
	1	3u10n 4u20n	100 100	1.8 6.5	100 100	1.9 6.1	100 100	2.0 6.8	1.8 5.8	62.8 34.3	8.9 10.6
		4u50n	100	16.7	100	10.8	100	24.9	9.8	23.6	11.2
	2	4u100n	100	60.0	100	35.3	100	271	21.7	20.3	9.4
		5u50n	100	39.0	100	15.5	100	171	11.5	13.3	12.0
		10u10n	81.3	1017	100	107	100	313	3.5	14.4	12.3
	3	50u10n	0.00	3590	62.5	1721	0.00	3581	25.1	4.9	5.9
		100u10n	0.00	3590	16.7	3267	0.00	3587	25.3	0.76	1.3

Table 3 . 5 -

 35 Computational results achieved using normal preprocessings.

			standard	min		min+st/act		efficiency
		name	solved	cpu	solved	cpu	solved	cpu	prep	rem	fcd
	1	3u10n 4u20n	100 100	3.0 17.0	100 100	3.1 17.1	100 100	3.2 17.7	3.0 16.4	64.9 37.9	12.1 11.4
		4u50n	100	42.2	100	36.2	100	49.0	35.0	24.9	12.2
	2	4u100n	100	170	100	137	100	322	128	21.6	9.8
		5u50n	100	74.5	100	54.2	100	173	48.8	13.4	12.5
		10u10n	75.0	1020	93.8	464	100	277	12.9	14.6	15.5
	3	50u10n	0.00	3589	68.8	1691	0.00	3584	156	8.8	8.9
		100u10n	0.00	3592	66.7	3305	0.00	3591	601	1.6	1.8

Table 3 . 6 -

 36 Computational results achieved using aggressive preprocessings.

			standard	min		min+st/act		efficiency
		name	solved	cpu	solved	cpu	solved	cpu	prep	rem	fcd
	1	3u10n 4u20n	100 100	3.5 25.6	100 100	3.5 25.0	100 100	3.4 25.4	3.5 25.0	65.1 40.2	12.1 11.4
		4u50n	100	64.1	100	58.3	100	66.9	57.1	25.9	12.2
	2	4u100n	100	233	100	215	100	319	206	21.9	9.8
		5u50n	100	109	100	87.1	100	196	84.0	13.4	12.5
		10u10n	75.0	1029	93.8	533	100	337	19.7	14.7	15.5
	3	50u10n	0.00	3593	68.8	1724	0.00	3590	195	8.8	8.9
		100u10n	0.00	3600	0.00	3597	0.00	3600	2402	2.0	1.8

Table 3 . 7 -

 37 Computational results achieved using maximal preprocessings.

  Branching algorithm . . . . . . . . . . . . . . . . . 100 4.2 Additional features . . . . . . . . . . . . . . . . . 102 4.2.1 Lower bounds . . . . . . . . . . . . . . . . . . . . . 102 4.2.2 Symmetry-breaking techniques . . . . . . . . . . . 104 4.3 Computational results . . . . . . . . . . . . . . . 112 4.3.1 About the model . . . . . . . . . . . . . . . . . . . 112 4.3.2 The additional features . . . . . . . . . . . . . . . 114 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . 117

	4.1 Modelling the dissemination problem . . . . . .	98
	4.1.1 Constraint programming model . . . . . . . . . . . 98
	4.1.2

  Let t ∈ {0, 1, . . . , m} be a time index. A partial transfer plan φ t of length t is a partial function from {1, . . . , m} to T φ = {∅, {1}, . . . , {u}}, whose domain X is at least {1, 2, . . . , t} (i.e. {1, . . . , t} ⊆ X). Note that X can be empty if t = 0. The states O x i (cf. equation (1.1) on page 9) are still defined for any node i ∈ N and any x ∈ {0, . . . , t}. The delivery lengthλ i (φ t ) of a node i ∈ N becomes λ i (φ t ) = min {x ∈ {0, . . . , t} | O x i = D}, or λ i (φ t ) = ∞ ifsuch an index does not exist. The dissemination length remains λ(φ t ) = max i∈R {λ i (φ t )}.

	Definition 4.1 -partial transfer plan

  practice -Proposition 4.4 can be applied every time we have to decide the value of a transfer φ(x1) for which there exists a contact σ x2 ∈ σ, x1 < x2, such that r x1 = r x2 and ∃y ∈ {x1, x1 + 1, . . . , x2} | s y = r x1 (in a sequential branching algorithm like that proposed in section 4.1.2). Note that the first x1-1 transfers are then fixed, and the set T= { k ∈ D | x k,x1is not set to 0 } of units that can be transmitted during contact σ x1 is given. Thus, in every branch k 2 ∈ T (associated with decision φ

  Different sequences of transfers can give rise to a similar disseminationi.e. it can exist two partial transfer plans φ t 1 and φ t 2 of length t ∈ {1, . . . , m}such that ∀i ∈ N , O t i (φ t 2 ) ⊆ O t i (φ t 1 ). Where this is the case, the set of transfer plans φ 1 ∈ Λ(φ t 1 ) dominates the set of transfer plans φ 2 ∈ Λ(φ t 2 ) since, from any transfer plan φ 2 ∈ Λ(φ t2 ), we can consider a better or equivalent transfer plan by taking the first t contacts of φ t 1 , and keeping the last mt contacts of φ 2 . This can be formalized as follows.Proof. Let φ 2 be a transfer plan in Λ(φ t 2 ). We build a transfer plan φ 1 ∈ Λ(φ t 1 ) by copying the first t transfers of φ t 1 , and by completing with the last mt transfers of φ 2 -i.e. ∀c ∈ {1, . . . , t}, φ 1 (c) = φ t 1 (c), and ∀c ∈ {t + 1, . . . , m}, φ 1

	Proposition 4.5
	Let φ t 1 and φ t 2 be two valid partial transfer plans of length t ∈ {1, 2, . . . ,
	min {m, λ(φ t 1 )}}. If O t i (φ t 2 ) ⊆ O t i (φ t 1 ) holds for all the nodes i ∈ N , then Λ(φ t 1 ) dominates Λ(φ t 2 ).

  2, . . . , n}} in a list L t . In short, S curr t saves the units possessed by each node at the end the first t transfers of the current partial transfer plan φ t 2 . Every list L t then contains the global states associated with all visited partial transfer plans of length t ∈ {1, 2, . . . , m}. From Proposition 4.5, we know that a node can be pruned if there exists a dominant state S dom

	t 1 ) such that ∀i ∈ N , O t ∈ L t (corresponding to a visited partial transfer plan φ t i (S curr t ) ⊆ O t i (S dom t

Table 4 .

 4 5.

		none		sym		sym+ngr	sym+ngr+wlb
	name	solved	cpu	solved	cpu	solved	cpu	solved	cpu
	3u10n	100	0.46	100	0.47	100	0.46	100	0.39
	4u20n	100	1.8	100	1.7	100	1.7	100	1.3
	4u50n	100	6.3	100	3.2	100	3.2	100	2.7
	4u100n	100	198	100	160	100	58.5	100	88.5
	5u50n	100	51.2	100	33.7	100	39.4	100	20.7
	10u10n	43.8	2236	50.0	1807	81.3	812	87.5	462
	50u10n	43.8	2106	43.8	2105	43.8	2102	75.0	1029
	100u10n	83.3	1184	83.3	1184	83.3	1189	100	702

Table 4 . 2 -

 42 Computational results obtained with CP Optimizer -part-1.

		sym+ngr+slb	sym+wlb	sym+slb	ngr
	name	solved	cpu	solved	cpu	solved	cpu	solved	cpu
	3u10n	100	0.59	100	0.38	100	0.59	100	0.46
	4u20n	100	1.8	100	1.3	100	1.8	100	1.7
	4u50n	100	3.6	100	2.6	100	3.7	100	5.2
	4u100n	100	216	100	181	100	174	100	107
	5u50n	100	73.1	100	12.6	100	66.0	100	54.2
	10u10n	100	36.1	68.8	1135	93.8	379	43.8	2143
	50u10n	87.5	640	75.0	1032	75.0	1061	43.8	2107
	100u10n	100	1220	100	731	100	1291	83.3	1183

Table 4 . 3 -

 43 Computational results obtained with CP Optimizer -part-2.

		ngr+wlb	ngr+slb	wlb		slb
	name	solved	cpu	solved	cpu	solved	cpu	solved	cpu
	3u10n	100	0.38	100	0.59	100	0.38	100	0.60
	4u20n	100	1.3	100	2.0	100	1.5	100	2.2
	4u50n	100	4.3	100	7.7	100	5.6	100	11.9
	4u100n	100	84.6	100	279	100	154	100	395
	5u50n	100	46.7	100	241	100	29.9	95.7	245
	10u10n	50.0	1807	68.8	1425	43.8	2091	62.5	1725
	50u10n	62.5	1689	62.5	1497	62.5	1662	62.5	1495
	100u10n	83.3	1187	83.3	1431	83.3	1187	83.3	1473

Table 4 . 4

 44

-Computational results obtained with CP Optimizer -part-3.

  . . . . . 122 5.2 Robust optimization . . . . . . . . . . . . . . . . . 123 5.2.1 Necessary and sufficient condition for a transfer plan to be Γ-robust . . . . . . . . . . . . . . . . . . 124 5.2.2 Enumeration procedure . . . . . . . . . . . . . . . 127 5.3 A constraint programming approach . . . . . . . 130 5.3.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.3.2 Additional features . . . . . . . . . . . . . . . . . . 133

5.4 Preliminary results . . . . . . . . . . . . . . . . . 138 5.4.1 About the benchmark . . . . . . . . . . . . . . . . 138 5.4.2 Numerical results . . . . . . . . . . . . . . . . . . . 140 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . 142

  ∀k ∈ D, ∀t ∈ T i , y i,k,t < Γ + 1 ⇐⇒ λ i,k > t y i,k,t = Γ + 1 ⇐⇒ λ i,k ≤ t (5.3) No constraints explicitly ensures that the transfer plan is Γ-robust. Actually, this is implicitly done through the branching stage. As mentioned in Section 5.2.2, to solve the problem, we sequentially set the transfers. It corresponds to set x-variables from x k,1 (∀k ∈ D) to x k,m . 1. At each node of the search tree, the earliest transfer φ(c) which is not yet set -i.e. the smallest index c ∈ {1, . . . , m} such that ∃k ∈ D where x k,c

	Implicit constraints

Table 5 . 4 -

 54 The best results achieved with CP-optimizer.

			wlb+ngr+sym+wla
		solved	feas	cpu
	1r2u20n	100	-	0.20
	1r2u50n	81.6	16.3	835
	1r2u100n	60.0	40.0
	1r5u10n	56.3	25.0
	1r25u10n	50.0	37.5
	1r50u10n	83.3	16.7	620
	2r2u50n	39.1	30.4
	2r3u10n	93.8	6.3	251
	2r17u10n	68.8	25.0
	2r34u10n	83.3	16.7
	3r2u10n	100	-	0.20
	3r13u10n	62.5	25.0
	3r25u10n	66.7	33.3
	average	72.7	20.9

-100 -224

The behaviour of this algorithm will not be described in the present chapter (see the online documentation of the IBM-Ilog CP Optimizer for more details).

Remerciements Remerciements

J e souhaite remercier Chengbin Chu et Marie-Christine Costa pour

In Figure 5.1, only one unit of flow can traverse G(φ, 1, 5), i.e. the transfer plan is not robust to failures. The minimum cut (depicted in gray) computed by Ford-Fulkerson [START_REF] Ford | Maximal flow through a network[END_REF] algorithm informs us that node 5 cannot receive datum unit 1 if contact σ 5 = (3, 4) fails. This contact is represented by the only arc -namely (3 2 , 4 1 ) -which is in the minimum cut (all the journeys from nodes 1 to 5 actually use contact σ 5 ). On the other hand, adding one contact (4, 5) at time 9 (with φ(9) = {1}) would improve the robustness of the solutioncf. the augmenting path (src, 1 0 , 2 1 , 2 2 , 4 2 , 5 2 , snk). The arc-disjoint journeys would then be (σ 1 , σ 5 , σ 6 ) and (σ 2 , σ 8 , σ 9 ).

(a) an instance of the robust dissemination problem (Γ = 1, 6 ∈ R and t = 0)

Numerical results

Let us have a look at column none in Table 5.2. This contains the numerical results obtained by considering the model of Section 5.3.1, and the branching algorithm described in Section 5.2.2, that is the minimum needed for solving the robust dissemination problem (with no additional features).

We note that only 13% of the benchmark has been solved to optimality, but feasible (robust) transfer plans have been found for approximatively 77% of the remaining instances. It shows that the benchmark is quite challenging, and that the solver (namely CP-Optimizer) can run into difficulties, even for small instances.

To achieve better results, we need to consider the additional propagation algorithms proposed in Section 5.3.2:

• the weak (wlb) or the strong (slb) lower bounds;

• the symmetry-breaking technique (sym);

• the nogood-recording (ngr);

• and/or the look-ahead procedure (la).

In practice, by activating each feature one by one, we noticed that the weak lower bound is the element that has the most impact on the performances of the solver -cf. column wlb in Table 5.2. However, we may wonder whether the strong lower bound is really relevant for this problem, because we observe that the percentage of instances solved proven to optimality tends to be worse in column slb than in column wlb.

Nogood-recording and symmetry-breaking techniques have also appeared to be very effective. Using these two features (together with the weak lower bound) enable more than 70% of the benchmark to be solved -see columns wlb+ngr and wlb+ngr+sym in Table 5.3. The impact of the look-ahead procedure is certainly more limited, see column wlb+ngr+sym+la, but is worth mentioning.

Note finally that the best numerical results were achieved with a variant of the look-ahead procedure, termed "weak-look-ahead". This consists in not executing the look-ahead algorithm more than once, for a same transfer in a same branch -i.e. we check that a transfer fixed in advance has a chance to be robust-improving only the first time we detect it. The results are reported in Table 5

Conclusion and perspectives

I n this thesis, we addressed the problem of making use of knowledge about node mobility when information must be routed throughout an intermittently-connected network, i.e. a delay-tolerant network (DTN) or a system of systems. We sought store-forward routings -termed transfer plans -which enable a set of recipient nodes to receive some data from a set of source nodes, when a sequence of contacts (an opportunity for two nodes to communicate) can be reliably estimated. In practice, this took the shape of a combinatorial problem, termed the dissemination problem.

Our contributions are organised into three parts.

1. First, we formally defined the "dissemination problem". This step was essential since the literature was lacking a clear and unified framework for such problems. In addition, the literature did not properly consider the case where identified and indivisible pieces of data (termed datum units) need to be routed from one or several sources, to one or several recipients. Next we proved that the problem is NP-Hard in the strong sense. We also highlighted some polynomial cases. Another interesting point is that the dissemination problem was shown to be equivalent to finding mutually arc-disjoint branchings in an evolving graph. In fact, all of this corresponds to Chapters 1 and 2.

2. The second part comprises more technical elements. More specifically, we proposed two solving schemes. The first one relies on integer-linear programming, and was defined in Chapter 3. The second one relies on constraint programming, and was defined in Chapter 4. Both of them Chapter 6. Conclusion and perspectives are based on the dominance rules that we proposed beforehand. These were leveraged to build efficient preprocessing procedures, and to define extra constraints. In addition, we proposed specific ad hoc propagation algorithms for the constraint-programming model to be more efficiently solved. For example, one of these algorithms is based on a lower bound of the dissemination length. Note that constraint programming has led to the best experimental results on a self-generated benchmark.

3. Finally, we study a variant of the dissemination problem -termed the robust dissemination problem -where we need to find Γ-robust transfer plans, i.e. valid transfer plans which guarantee that the recipient nodes correctly receive all datum units, even if any Γ transfers fail. We hope that this approach will manage to cover a wide range of constraints of real applications. To tackle this problem, we proposed a necessary and sufficient condition for a valid transfer plan to be Γ-robust. Thereafter we adapted the solving scheme based on constraint programming (and proposed for the original problem) in order to take account of this new constraint. All of this is discussed in Chapter 5.

This work is still underway.

Concerning the robust dissemination problem, we still have to propose a more specific benchmark, with few but well-characterized classes and groups (like we did for the dissemination problem). For this purpose, we propose to follow the promising approach discussed in Section 5.4.1.

At the same time, we must develop/implement a preprocessing procedure for the robust dissemination problem. We are currently adapting the one we proposed for the initial dissemination problem to that end.

Finally, we think that further research on robust optimization would help prediction errors to be more effectively managed in practice (which seems to us to be a crucial point in a real context). For example, instead of considering that some contacts may fail, we could also envision that contacts occur in an uncertain order, or even that some nodes may be destroyed. Nodes deployed in hostile (e.g. military) environments are indeed prone to such risks. This being said, many other constraints are also worth considering -e.g. buffers and/or batteries limitations, transmission and/or propagation delays, interferences, etc.