Abstract This article considers resilience of service networks that are composed of service and control nodes to node‐targeted attacks. Two complementary problems of selecting attacked nodes and placing control nodes reflect the interaction between the network operator and the network attacker. This interaction can be analyzed within the framework of game theory. Considering the limited performance of the previously introduced iterative solution algorithms based on non‐compact problem models, new compact integer programming formulations of the node attack optimization problem are proposed, which are based on the notion of pseudo‐components and on a bilevel model. The efficiency of the new formulations is illustrated by the numerical study that uses two reference networks (medium‐size and large‐size), and a wide range of the sizes of attacks and controllers placements.

Abstract In this article we introduce a preprocessing technique to solve the Segment Routing Traffic Engineering Problem optimally using significantly fewer computational resources than previously introduced methods. Segment routing is a recently developed interior gateway routing protocol to be used on top of existing protocols that introduces more flexibility in traffic engineering. In practice, segment routing allows to deviate traffic from its original path by specifying a list of intermediate nodes or links, called segments, to visit before going to its destination. The issue we tackle in this article is that the number of segment paths scales exponentially with the maximum number of segments allowed leading to scalability issues in mathematical formulations. This article introduces the notion of dominated segment paths, these are paths that can be eliminated from the solution space when searching for an optimal solution. We propose a dynamic programming algorithm eliminating dominated paths for any number of segments. Numerical results show that respectively 50%, 90%, and 97% of paths are dominated when considering up to 2, 3, and 4 segments on benchmark network topologies.

In blockchains , transaction fees are fixed by the users. The probability for a transaction to be processed quickly increases with the fee level. In this paper, we study the transaction fee optimization problem in the Ethereum blockchain. This problem consists of determining the minimum price a user should pay so that its transaction is processed with a given probability in a given amount of time. To reach this goal, we define a new solution method based on a Monte Carlo approach to predict the probability that a transaction will be mined within a given time limit. Numerical results on real data highlight the quality of the results.

Abstract We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop‐indexed arc variables. Although such models have proved to have a very strong linear programming bound, they are not easy to use because of the huge number of variables. This has motivated some studies with models involving fewer variables that use, instead of the hop‐indexed arc variables, hop‐indexed node variables. In this article, we contextualize the linear programming relaxation of these node‐based models in terms of the linear programming relaxation of known arc‐based models. We show that the linear programming relaxation of a general node‐based model is implied by the linear programming relaxation of a straightforward arc‐based model.

Special issue on network analytics

International audience

We introduce a strategic decision problem in a one-way electric car sharing system. We propose a mixed integer linear programming formulation for solving this problem. We conduct an extensive computational study to test the performance of our formulation and its relaxations by using real data instances. The results turn out to be encouraging for diving into more challenging extensions of the problem under consideration.

During the planning of communication networks, the routing decision process (distributed and online) often remains decoupled from the network design process, that is, resource installation and allocation‐planning process (centralized and offline). To reconcile both processes and take into account demand variability, we generalize the capacitated multicommodity fixed charge network design class of problems by including different types of fixed costs (installation and maintenance costs) and variable costs (routing costs) but also variable traffic demands over multiple periods. However, conventional integer programming methods can typically solve only small to medium size instances of this problem. Two major difficulties are encountered when using commercial solvers to solve the associated mixed integer programs: (i) problems are large scale and even solving the linear relaxation of the problem can be challenging; and (ii) the solver hardly find good feasible solutions for medium to large scale instances. As an alternative, we propose a Lagrangian approach for computing a lower bound by relaxing the flow conservation constraints such that the Lagrangian subproblem itself decomposes by node. Though this approach yields one subproblem per network node, solving the Lagrangian dual by means of the bundle method remains a complex computational tasks. However, it always provides a lower bound on the optimal solution. Moreover, based on this relaxation, we propose a Lagrangian heuristic that makes the approach more robust than a black‐box usage of a Mixed Integer Programming (MIP) solver. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 110–123 2017

In communication networks, the routing decision process (distributed and online) remains decoupled from the network design process, i.e., resource installation and allocation planning process (centralized and offline). To reconcile both processes, we ambition to design a distributed optimization technique aware of distributed nature of the routing process by decomposing the optimization problem along same dimensions as (distributed) routing decision process. For this purpose, we generalize the capacitated multi-commodity capacitated fixed charge network design (MCND) class of problems by including different types of fixed costs (installation and maintenance costs) and variable costs (routing costs) but also variable traffic demands over multiple periods. However, conventional integer programming methods can typically solve only small to medium size instances. As an alternative, we propose a Lagrangian approach for computing a lower bound by relaxing the flow conservation constraints such that the Lagrangian subproblem itself decomposes by node. Though this approach yields one subproblem per network node, solving the Lagrangian dual by means of the bundle method remains a complex computational tasks. However, the approach is more robust than any LP solvers and it always returns some solutions. Instead, we proved that CPLEX, which uses the Dual Simplex algorithm, is not able to provide a solution for large instances.

The capacitated fixed‐charge network design (FCND) problem considers the simultaneous optimization of capacity installation and routing of traffic where a fixed cost is paid for opening a link and a linear routing cost is paid for sending traffic flow(s) on that link. The routing decisions must be performed such that the traffic flows remain bounded by the installed link capacities. The FCND problem appears as a particular case of the combined multiperiod network design and traffic flow routing problem with time‐dependent demands formulated in this article as a mixed integer linear program (MILP). A compact formulation based on the aggregation of traffic flows per destination and an extended formulation, where flows are decomposed by origin‐destination pairs while keeping the requirement of destination‐based routing, have been proposed in D. Papadimitriou and B. Fortz, IEEE International Conference on Communications (2014), pp.1124–1130 and IEEE Global Communications Conference (2014), pp.1303–1309, respectively. In this article, we propose to resolve this computationally challenging problem by means of the rolling horizon heuristic with the objective to decrease the computational time while degrading as less as possible the quality of the solution. The resulting improvements enable to progressively overcome the computational limits encountered when solving such problem, in particular, when the network size and number of periods increase. The improvements provided by the rolling horizon heuristic can be further exploited by extending the proposed model to account for different patterns of failures that may affect installed arcs over time. For this purpose, our generalized MILP formulation comprises a time‐variable link maintenance cost function. We further analyze the quality of the results for the proposed formulation with different link maintenance cost functions with the objective to derive the best arc replacement strategy. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(4), 364–379 2015

The combined network design and (distributed) traffic routing problem can be formulated as a large-scale multi-period mixed integer optimization problem. This problem combines network design decisions and routing decisions, with time-dependent traffic demands. In this paper, we consider different branch-and-cut strategies for solving the problem with the base and extended formulations proposed in our prior work.

The combined network design and (distributed) traffic routing problem can be formulated as a large-scale multi-period mixed integer optimization problem. This problem combines network design decisions and routing decisions, with time-dependent demands. In [1], we proposed a compact formulation based on the aggregation of flows by destination. We observed that its resolution on realistic instances becomes intractable and unscalable with state-of-the-art solvers due to the weak linear programming bound that this formulation provides. In this paper, we consider an extended formulation where flows are decomposed by origin-destination pairs, while keeping the requirement of destination-based routing. The quality of the extended formulation and the computational time needed to solve it are evaluated on a representative set of network topologies and traffic demands, and compared to results obtained with the base formulation of [1]. The extended formulation can then be considered for more efficient resolution methods involving decomposition and cutting planes approaches.

In today's communication networks, distributed control functions such as routing inherit their design driven by processing capacity and memory consumption. Henceforth, the routing protocol decision process (distributed and online) remains still decoupled from the routing optimization process (centralized and offline). Distributed optimization does not take into account the distributed nature of the online routing decision making process because distributed optimization is not decomposed along the same dimensions as the routing decision making process. The challenge becomes thus how to modify the routing decision process to include optimization objectives and how to make the optimization problem aware of the distributed nature of the online routing decision process under dynamic conditions. As a first evolution in that direction, we propose a new combined optimization model that integrates network design decisions and routing decisions, with time-dependent demands. As part of our main contribution, the proposed model keeps in sight the need for a distributed routing function, through the use of scalable routing tables. We also put our work in the perspective of a fully distributed, decomposed optimization setting.

Given a graph with nonnegative edge weights and node pairs Q, we study the problem of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L edges between each pair in Q. Using the layered representation introduced by Gouveia [Gouveia, L. 1998. Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints. INFORMS J. Comput. 10(2) 180–188], we present a formulation for the problem valid for any K, L ≥ 1. We use a Benders decomposition method to efficiently handle the large number of variables and constraints. We show that our Benders cuts contain constraints used in previous studies to formulate the problem for L = 2, 3, 4, as well as new inequalities when L ≥ 5. Whereas some recent works on Benders decomposition study the impact of the normalization constraint in the dual subproblem, we focus here on when to generate the Benders cuts. We present a thorough computational study of various branch-and-cut algorithms on a large set of instances including the real-based instances from SNDlib. Our best branch-and-cut algorithm combined with an efficient heuristic is able to solve the instances significantly faster than CPLEX 12 on the extended formulation.

Abstract The ring spur assignment problem arises in the design of next‐generation telecommunications networks and has applications in location‐allocation problems. The aim is to identify a minimum cost set of interconnected ring spurs. We seek to connect all nodes of the network either on a set of bounded disjoint local rings or by a single spur edge connected to a node on a local ring. Local rings are interconnected by a special ring called the tertiary ring. We show that the problem is NP ‐Hard and present an Integer Programming formulation with additional valid inequalities. We implement a branch‐and‐cut algorithm and present our conclusions with computational results. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract The desire for configuring well‐managed open shortest path first (OSPF) routes to handle the communication needs in the contemporary business world with larger networks and changing service requirements has opened the way to use traffic engineering tools with the OSPF protocol. Moreover, anticipating possible shifts in expected traffic demands while using network resources efficiently has started to gain more attention. We take these two crucial issues into consideration and study the weight setting problem for OSPF routing problem with polyhedral demands. Our motivation is to optimize the link weight metric such that the minimum cost routing uses shortest paths with equal cost multipath splitting and the routing decisions are robust to possible fluctuations in demands. In addition to a compact mixed integer programming model, we provide an algorithmic approach with two variations to tackle the problem. We present several test results for these two strategies and discuss whether we could make our weight‐managed OSPF comparable to unconstrained routing under polyhedral demand uncertainty. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012

Along with many ASCILITE members, we have grown increasingly concerned that current approaches to \neducational technology research lack value and practical application in the field. Educational design \nresearch (EDR) is an emerging approach that bridges the demand for rigorous research with the \ndevelopment of relevant solutions to educational problems. EDR is an intervention and process-oriented \napproach that uses a variety of methods to examine the development and implementation of instructional \nsolutions to current educational problems. As evidence about the inner workings of interventions \naccumulates over time, design principles and learning theories are derived from work in local contexts, and \ntheir limits can be tested in other settings. This genre of research is currently underrepresented in the \nliterature. To advance scholarship through the execution and reporting of EDR, we identified an urgent \nneed for examples across fields, and especially related to educational technology in higher education.

info:eu-repo/semantics/published

A system of techniques is presented for optimizing open shortest path first (OSPF) or intermediate system-intermediate system (IS-IS) weights for intradomain routing in a changing world, the goal being to avoid overloaded links. We address predicted periodic changes in traffic as well as problems arising from link failures and emerging hot spots.

Open shortest path first (OSPF) is the most commonly used intra-domain Internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to their physical distances, but often the main goal is to avoid congestion, i.e., overloading of links, and the standard heuristic recommended by Cisco is to make the weight of a link inversely proportional to its capacity. Our starting point was a proposed AT&T WorldNet backbone with demands projected from previous measurements. The desire was to optimize the weight setting based on the projected demands. We showed that optimizing the weight settings for a given set of demands is NP-hard, so we resorted to a local search heuristic. Surprisingly it turned out that for the proposed AT&T WorldNet backbone, we found weight settings that performed within a few percent from that of the optimal general routing where the flow for each demand is optimally distributed over all paths between source and destination. This contrasts the common belief that OSPF routing leads to congestion and it shows that for the network and demand matrix studied we cannot get a substantially better load balancing by switching to the proposed more flexible multi-protocol label switching (MPLS) technologies. Our techniques were also tested on synthetic internetworks, based on a model of Zegura et al., (1996), for which we did not always get quite as close to the optimal general routing.