Search

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 FROM AUTHOR]

The design of distribution networks that simultaneously consider location and inventory decisions seeks to balance costs and product availability. The most commonly observed measure of product availability in practical settings is the fill‐rate service level. However, the optimal design of a distribution network that considers the fill rate to control shortages of fast‐moving consumer goods (FMCG) is considered intractable and has only been addressed by heuristic methods. This paper addresses the optimal design of a distribution network for FMCG able to provide high fill‐rate service level under a continuous review (r,Q)$(r,Q)$ policy. Considering the exact formulation for the provided fill rate, we formulated a joint location–inventory model with fill‐rate service level constraints as a convex mixed integer nonlinear problem for which a novel decomposition‐based outer approximation algorithm is proposed. Numerical experiments have shown that our solution approach provides good‐quality solutions that are on average 0.15% and, at worst, 2.2% from the optimal solution. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 [...]

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. [ABSTRACT FROM AUTHOR]

A tabu search heuristic for the design of self-healing rings (SHRs), to protect the transmission of telecommunication demands, in a zonal network is proposed. This search has demonstrated its efficiency by improving significantly upon the best solutions that could be found with a greedy constructive heuristic over a large set of real and randomly generated instances.

Given an undirected graph, we study the problem of finding K edge-disjoint paths, each one containing at most L edges, between a given pair of nodes. We focus on the case of K = 2and L = 3. For this particular case, previous known compact formulations are valid only for the case with non-negative edge costs. We provide the first compact linear description that is also valid for general edge costs. We describe new valid inequalities that are added to a well known extended formulation in a layered graph, to get a full description of the polyhedron for K = 2and L = 3. We use a reduction of the problem to a size-2 stable set problem to prove this second property. [ABSTRACT FROM AUTHOR]

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 [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

For trees, they provide a linear-time dynamic programming algorithm and a tight and compact extended formulation. This special issue of I Networks i is devoted to recent research in the area of network analytics and optimization. Raghavan and Zhang [6] study the weighted target set selection (WTSS) problem on cycles and trees. [Extracted from the article]

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 N P -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 FROM AUTHOR]

Intra-domain routing protocols are based on Shortest Path First (SPF) routing, where shortest paths are calculated between each pair of nodes (routers) using pre-assigned link weights, also referred to as link metric. These link weights can be modified by network administrators in accordance with the routing policies of the network operator. The operator's objective is usually to minimize traffic congestion or minimize total routing costs subject to the traffic demands and the protocol constraints. However, determining a link weight combination that meets a network operator's objectives is a difficult task. In this paper, we study the link weight optimization problem in intra-domain networks. This problem is proved to be NP-hard with hard protocol constraints, e.g., a flow is evenly distributed along the shortest paths between its origin and destination nodes. We present two fast heuristic approaches to generate efficient link metrics for intra-domain routing. Some promising experimental results are reported. [ABSTRACT FROM AUTHOR]

Intra-domain routing protocols are based on shortest path first (SPF) routing, where shortest paths are calculated between each pair of nodes (routers) using pre-assigned link weights, also referred to as link metric. These link weights can be modified by network administrators in accordance with the routing policies of the network operator. The operator's objective is usually to minimize traffic congestion or minimize total routing cost subject to the traffic demands and the protocol constraints. However, determining a link weights combination that best suits the network operator's requirements is a difficult task. This paper provides a survey of meta-heuristic approaches to traffic engineering, focusing on local search approaches and extensions to the basic problem taking into account changing demands and robustness issues with respect to network failures. [ABSTRACT FROM AUTHOR]