Search

In recent years, Internet traffic has increased due to its widespread use. This can be attributed to the growth of social games on smartphones and video distribution services with increasingly high image quality. In these situations, a routing mechanism is required to control congestion, but most existing routing protocols select a single optimal path. This causes the load to be concentrated on certain links, increasing the risk of congestion. In addition to the optimal path, the network has redundant paths leading to the destination node. In this study, we propose a multipath control with multi-commodity flow problem. Comparing the proposed method with OSPF, which is single-path control, and OSPF-ECMP, which is multipath control, we confirmed that the proposed method records higher packet arrival rates. This is expected to reduce congestion.

The job sequencing and tool switching (SSP) is a well-known combinatorial optimization problem that aims to minimize the number of tool switches. The problem mainly arises in a flexible manufacturing system, in which machines can be configured with various tools to process different jobs and tool switches will correspond to a reduction of productivity. While the general studies assume uniform setup time for tool switching, applications on the industries indicate that the setup time of a tool might depend on the previously installed tool of the same slot. Therefore, this article proposes two integer linear programming models for the sequence-dependent SSP, namely the five-index formulation and the multicommodity flow formulation. Experimental tests are executed to compare the sequence-dependent SSP with the uniform SSP and the results show the effectiveness of multicommodity flow formulation. Finally, several managerial discussions are derived from the results.

Introducing InterSatellite Links (ISLs) is a major trend in new-generation Global Navigation Satellite Systems (GNSSs). Data transmission scheduling is a crucial problem in the study of ISL management. The existing research on intersatellite data transmission has not considered the capacities of ISL bandwidth. Thus, the current study is the first to describe the intersatellite data transmission scheduling problem with capacity restrictions in GNSSs. A model conversion strategy is designed to model the aforementioned problem as a length-bounded single-path multicommodity flow problem. An integer programming model is constructed to minimize the maximal sum of flows on each intersatellite edge; this minimization is equivalent to minimizing the maximal occupied ISL bandwidth. An iterated tree search algorithm is proposed to resolve the problem, and two ranking rules are designed to guide the search. Experiments based on the BeiDou satellite constellation are designed, and results demonstrate the effectiveness of the proposed model and algorithm.

Bus driver rostering generates the work plan for a pool of drivers during a planning period of predefined length. This plan, called the roster, must consider the balance between the pressure of costs, the provision of a service of high quality, labour agreements, and the goodwill of the workers. The bus driver rerostering problem occurs during real-time operational planning, when unexpected events—such as non-planned absences of drivers—disrupt the roster. To reconstruct a roster which is originally built in a context of days off schedules for drivers, we propose a reactive methodology based on a multicommodity flow assignment mixed integer linear programming model. The objective is to minimise the number of depot drivers who are assigned to drive and the number of postponed days off, as well as the dissimilarity between the reconstructed and the original roster and the balancing of the workload. The proposed algorithm enables the disrupted roster to be reconstructed at the expense of a relatively small number of changes in drivers’ work and rest periods, while, at the same time, controlling the dimension of the multicommodity flow network. Computational experience based on real-life based instances revealed that the algorithm has the ability to produce reconstructed rosters with few changes to the drivers’ original work assignment, in a short CPU time.

Origin-destination integer multicommodity flow problems differ from classic multicommodity models in that each commodity has one source and one sink, and each commodity must be routed along a single path. A new invisible-hand heuristic that mimics economic markets' behavior is presented and tested on large-scale telecommunications networks, with solution times two orders of magnitude faster than Cplex's LP relaxation, more dramatic MIP ratios, and small solution value differences.

Pin accessibility encounters nontrivial challenges due to the smaller number of routing tracks, higher pin density, and more complex design rules. Consequently, securing design rule-correct routability has become a critical bottleneck for sub-10-nm IC designs (particularly in the detailed routing stage) costing days of runtime. To reduce turnaround time, IC designers demand new design methodologies to analyze the routing feasibility of a given layout architecture (e.g., conditional design rules, pin assignment patterns, etc). There are several conventional methods capable of assessing routability that consider pin accessibility. However, precise diagnosis of unroutable layouts remains an open problem for IC design practitioners. In this article, we propose two novel frameworks that: 1) efficiently analyzes design rule-correct routability via an integer linear programming (ILP)-derived Boolean satisfiability (SAT) formulation written in light-weight conjunctive normal form, on top of multicommodity flow theory and 2) precisely diagnose explicit reasons for design-rule violations (DRVs) in the form of human-interpretable explanations, while specifying conflicting design rules with a physical location. While covering a variety of conditional design rules, we have refined our formulation by using SAT encoding techniques, supernode simplification, Boolean constraint propagation-based preprocessing, etc. We demonstrate that our routability analysis framework produces design rule-correct routability assessment within 0.02% of ILP runtime on average. Also, our routability diagnosis framework precisely examines DRVs, revealing design-rule conflicts for a variety of pin layouts and switchboxes. We show our frameworks scalability by utilizing practical benchmarks ranging up to 40 000 grid-size layouts (i.e., 200 Htrack $\times $ 200 Vtrack), producing results within an hour.

In this work , one proposes a model to evaluate the optimal deployment of Centralised Radio Access Network (C- RAN ) architecture elements , i.e. Base Band processing Units ( BBUs ) and fronthaul links , in a brown- field scenario, in which traditional base stations are already deployed and a physical network is present. The proposed optimisation framework jointly optimises BBU placement and access network infrastructures deployment . It clusterises the Remote Radio Heads in the scenario through a Multicommodity Flow approach , and solves the minimum cost fronthaul network deployment through a Rooted Delay - Constrained Minimum Spanning Tree approach . Optical fibre and microwave links are considered as fronthaul infrastructures . The proposed optimisation framework is validated through a comparison with a theoretical output for a canonical scenario, being afterwards applied to a real scenario. A cost analysis for different scenario configurations is presented , and trade - offs and guidelines for a cost optimal deployment of C- RAN are provided . The analysis of results for the real scenario of the city of Lisbon and its surrounding areas shows that the delay budget in the fronthaul network highly impacts on capital expenditures as well as on operational ones . It is shown that a larger delay budget enables an annual cost reduction up to 72 % in urban areas and 54 % in rural ones .

The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We show that the switch chain for sampling simple undirected graphs with a given degree sequence is rapidly mixing when the degree sequence is so-called strongly stable. Strong stability is satisfied by all degree sequences for which the switch chain was known to be rapidly mixing based on Sinclair's multicommodity flow method up until a recent manuscript of Erdős and coworkers in 2019. Our approach relies on an embedding argument, involving a Markov chain defined by Jerrum and Sinclair in 1990. This results in a much shorter proof that unifies (almost) all the rapid mixing results for the switch chain in the literature, and extends them up to sharp characterizations of P-stable degree sequences. In particular, our work resolves an open problem posed by Greenhill and Sfragara in 2017.

The maritime industry is one of the greenest modes of transportation, taking care of almost 90% of the global trade. The maritime container business revolves around liner shipping, which consists of container vessels sailing on fixed itineraries. For the last 20 years, there has been an increasing number of publications regarding how to design such fixed routes (services), to ensure a high level of service while minimizing operational costs and environmental impact. The liner shipping network design problem can briefly be described as follows: Given a set of demands (defined by origin, destination, time limit) and a set of vessels with variable capacity, the task is to design a set of weekly services, assign vessels to the services, and flow the demand through the resulting network such that it arrives within the stated time constraints. The objective is to maximize revenue of transported demand subtracting the operational costs. We present an in-depth literature overview of existing models and solution methods for liner shipping network design, and discuss the four main families of solution methods: integrated mixed integer programming models; two-stage algorithms designing services in the first step and flowing containers in the second step; two-stage algorithms first flowing containers and then designing services; and finally algorithms for selecting a subset of proposed candidate services. We end the presentation by comparing the performance of leading algorithms using the public LINER-LIB instances. The paper is concluded by discussing future trends in liner shipping, indicating directions for future research.

Robust multiperson tracking requires the correct associations of online detection responses with existing trajectories. In this paper, we propose to integrate multiple cues to resolve the ambiguities in data association for multiperson tracking. Unlike most existing algorithms which integrate multiple cues in the same manner for different scenes, we learn scene-specific parameters to integrate multiple cues for different scenes, as the discriminative power of each cue may vary in different scenes. The scene-specific integration parameters are learned offline by supervised learning method. Min-cost multicommodity flow is employed to solve the data association task. The edge cost of the multicommodity network, which is crucial for the data association, is determined by integrating the multiple cues extracted from the detection response based on the learned scene-specific integration parameters. The experimental results on public multiperson tracking data set demonstrate the effectiveness of the proposed scene-specific integration method.

In this paper a new multicommodity flow mathematical model for the Job Sequencing and Tool Switching Problem (SSP) is presented. The proposed model has an LP relaxation lower bound equal to the num...

This paper deals with multi-depot bus scheduling (MDBS) problem. Depot workload balancing constraints are introduced. In this case, the problem can be stated as a two-objective multi-commodity flow...

This article discusses the guide path design of automated guided vehicle (AGV) systems for which we propose a model that incorporates a dynamic multicommodity flow with capacity constraints from a pickup to a delivery point. The problem is formulated as the selection of a guide path connecting a given set of pickup/delivery points. A cell-based local search that is based on an original neighborhood technique is developed. In the proposed method, the guide path is effectively optimized based on a local search of cell-based neighborhood search preserving connectivity constraints and the subsequent solution of a dynamic multicommodity flow problem. The performance of the proposed method is strengthened by the redundant elimination of arcs and intensification of search according to the concept of the flow-concentrated cell. The effectiveness of the proposed method is demonstrated by comparing it with a general-purpose solver and recent algorithms for fixed-charge capacitated multicommodity network design problems. A real case study is presented to demonstrate the applicability of the proposed method by using simulation software. Note to Practitioners —Due to the recent growth of online shipping, the design of automated warehousing systems is receiving much attention. Most automated warehousing systems introduce multiple automated guided vehicles (AGVs) for transportation. This article presents an efficient optimization of guide path design considering congestions and dynamic multicommodity flow routing. We develop cell-based local search heuristics for the guide path design problem for AGV systems that can be applied to a large-scale transportation model to solve the problem efficiently. Our major finding is that the guide path design with the dynamic multicommodity flow can significantly reduce the delays caused by congestions and improve the efficiency of the warehousing systems. The effectiveness of the derived guide path design is evaluated by simulation software. The feasibility of the guide path is confirmed in several case studies.

A multi-commodity flow problem consists of moving several commodities from their respective sources to their sinks through a network where each edge has different costs and capacity constraints. This paper explores different linear programming algorithms and their performance regarding finding an optimal solution for multi-commodity flow problems. By testing several of different network constraints, we examine which algorithms are most suitable for specific network and problem structures. Furthermore, we implement our own multi-commodity solver and compare its performance against state-of-the-art linear programming solvers. The results show that for the methods we tested it is difficult to discern which class of linear programming methods are optimal solvers for multi-commodity flow problems and that their performance depends on how the network and commodities are structured.

We consider the problem of optimizing the achievable EPR-pair distribution rate between multiple source-destination pairs in a quantum Internet, where the repeaters may perform a probabilistic Bell-state measurement and we may impose a minimum end-to-end fidelity as a requirement. We construct an efficient linear programming (LP) formulation that computes the maximum total achievable entanglement distribution rate, satisfying the end-to-end fidelity constraint in polynomial time (in the number of nodes in the network). Our LP formulation gives the optimal rate for a class of entanglement generation protocols where the repeaters have very short-lived quantum memories. We also propose an efficient algorithm that takes the output of the LP solver as an input and runs in polynomial time (in the number of nodes) to produce the set of paths to be used to achieve the entanglement distribution rate. Moreover, we point out a practical entanglement generation protocol that can achieve those rates.

Time-varying network flows (also called dynamic network flows) generalize standard network flows by introducing an element of time. In this paper, we consider the dynamic version of the minimum cost multicommodity flow problem with storage at intermediate nodes. This problem is known to be NP-hard. By using of the flow decomposition theorem in network flows, we propose an efficient model based on dynamic path flows for this problem. For some special structures of the path-flow formulation, we provide an algorithm based on decomposition principle, for solving the proposed model. In the end, the efficiency of the proposed approach is evaluated through a number of experimental tests.

Within the formalism of the mathematical model of transferring a multicommodity flow, the reachability set of multiuser network systems is studied. A method is proposed for constructing an internal supporting frame based on the vectors of the maximum flows that can be transferred between all pairs of nodes in exclusive and limited exclusive modes of flow control. Using the obtained limit values, we construct a polyhedron of a simpler structure (frame) belonging to the set of reachable multi-flows and a cone of possible directions for the generation of boundary points. Methods for obtaining various multicriteria evaluations of the functional capabilities of a transmission network are considered. The developed approach can be used for the a priori analysis of the set of reachable multiflows, including quickly obtaining estimates and acceptable options for the fair distribution of the limited capacity of the transmission network.

The analysis of network routing games typically assumes precise, detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desired target flow as an equilibrium. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. We give a crisp positive answer to this question. We show that one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes tolls as input and outputs the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method, and extends to various other settings. We obtain improved query-complexity bounds for series-parallel networks, and single-commodity routing games with linear latency functions. Our techniques provide new insights into network routing games.

Within the formalism of the multicommodity flow model, changes in the functional characteristics of a multiuser network after a damage are studied. To analyze the original limiting capabilities of the system, the maximum flow is calculated for each pair of vertices independently of other pairs. All edges of the corresponding minimum cut are removed, and the maximum possible flows for all origin–destination pairs are found in the damaged network and compared with their initial values. The detriment is evaluated for various cuts (structural damages). The influence of structural damages on the attainable values of the flow for each pair of vertices is investigated. This makes it possible to rank the origin–destination pairs by their susceptibility to the influence of damages from a given class. Ranking is performed on the basis of a bi-criteria detriment evaluation model. This approach is used for analyzing the vulnerability of large territory distributed systems, including telecommunication systems, communication and control systems.

This article addresses a variant of the Discrete Cost Multicommodity Flow (DCMF) problem with random demands, where a penalty is incurred for each unrouted demand. The problem requires finding a network topology that minimizes the sum of the fixed installation facility costs and the expected penalties of unmet multicommodity demands. A two-stage stochastic programming with recourse model is proposed. A simulation-optimization approach is developed to solve this challenging problem approximately. To be precise, the first-stage problem requires solving a specific multi-facility network design problem using an exact enhanced cut-generation procedure coupled with a column generation algorithm. The second-stage problem aims at computing the expected penalty using a Monte Carlo simulation procedure together with a hedging strategy. To assess the empirical performance of the proposed approach, a Sample Average Approximation (SAA) procedure is developed to derive valid lower bounds. Results of extensive computational experiments attest to the efficacy of the proposed approach. Scopus

We consider a problem arising in the design of ad-hoc wireless sensor networks. Given a connected bidirectional digraph with n sensors and a fixed sink, the p-arborescence star problem is the problem of clustering the sensors into p disjoint subsets and defining a directed backbone that spans the sink and all p cluster-heads, one for each cluster. The overall objective of the problem is to minimize the sum of intra and inter-cluster costs. We introduce and compare formulations based on directed cutset constraints and multicommodity flow variables. Valid inequalities to strengthen the models are also given. To solve these models, we develop efficient cutting-plane methods. We carry out extensive computational experiments and comparisons to illustrate the performance of our methods.

We derive an analytical expression for the mean load at each node of an arbitrary undirected graph for the non-uniform multicommodity flow problem under weighted random routing. We show the mean load at each node, net of its demand and normalized by its (weighted) degree, is a constant equal to the trace of the product of two matrices: the Laplacian of the demand matrix and the generalized inverse of the graph Laplacian. For the case of uniform demand, this constant reduces to the sum of the inverses of the non-zero eigenvalues of the graph Laplacian. We note that such a closed-form expression for the network capacity for the general multicommodity network flow problem has not been reported before, and even though (weighted) random routing is not a practical procedure, it enables us to derive a (tight) upper bound for the capacity of the network under more standard routing policies. Using this new expression, we compute network capacity for a sample of demand matrices for some prototypical networks, including uniform demand (one unit between all node pairs) and broadcast demand (one unit between a source node and each other node as destination), and finally derive estimates of the mean load in some asymptotic cases.

This chapter presents a new mathematical formulation, which is based on multicommodity flow, for a classical capacitated minimum spanning tree problem. It also demonstrates the performance of Van Roy’s cross decomposition algorithm for solving the capacitated minimum spanning tree can be significantly improved by incorporating an edge exchange heuristic algorithm at a tremendous saving in the computational effort. The results also reveal that the proposed algorithm is very competitive with Lagrangian original algorithm in terms of solution quality. The use of the new formulation and the proposed algorithm which take better advantage of the problem structure, especially that of the dual subproblem, provide a large potential for improvement.

We deal with a problem which combines storage location assignment with sequencing decisions about the assigned storage locations. Given a set of different product types, with the corresponding storage demand, a set of capacitated storage locations has to be assigned to each product type for the corresponding storing operations. In addition, a suitable sequencing of the assigned storage locations must be devised for each product type, i.e., it has to be decided the ordering with which the storage locations will be filled up during the storing operations. A motivation is that a First-In First-Out (FIFO) picking criterion among storage locations is required per product type. The sequencing established for the assigned storage locations will therefore allow to easily implement the FIFO policy in the successive order picking. Moreover, the selected sequencing also determines the availability of extra storage per product type, on top of pairs of consecutive storage locations along the sequence. The goal is to maximize the storage capacity which remains available after the assignment of the storage locations. We prove the NP-Hardness of the problem and we model it as a constrained multicommodity flow problem on an auxiliary graph. We then propose a Mixed-Integer Linear Programming (MILP) model, with some valid inequalities, based on the multicommodity flow formulation. Two relaxations are proposed as well to estimate the quality of the model solutions. Two matheuristic approaches are then designed starting from the MILP model. The proposed methodology is applied to a case study related to a large warehouse with a high stock rotation index in tissue logistics, which motivated our study. Computational results on a wide test bed related to such a real application context show the efficiency and the efficacy of the presented approaches.

The multicommodity flow problem deals with the transshipment of more than one commodity from respective sources to corresponding sinks without violating the capacity constraints. Due to the capacity constraints, flows out from the sources may not reach their sinks, and so, the storage of excess flows at intermediate nodes plays an important role in the maximization of flow values. In this paper, we introduce the maximum static as well as maximum dynamic multicommodity flow problems with intermediate storage. We present polynomial and pseudopolynomial time algorithms for the former and latter problems, respectively. We also present the solution procedures to these problems in contraflow network having symmetric as well as asymmetric arc transit times. We transform the solutions in continuous-time settings by using natural transformation.

In this paper we derive an analytical expression for the mean load at each node of an arbitrary undirected graph for the uniform multicommodity flow problem under random walk routing. We show the mean load is linearly dependent on the nodal degree with a common multiplier equal to the sum of the inverses of the non-zero eigenvalues of the graph Laplacian. Even though some aspects of the mean load value, such as linear dependence on the nodal degree, are intuitive and may be derived from the equilibrium distribution of the random walk on the undirected graph, the exact expression for the mean load in terms of the full spectrum of the graph has not been known before. Using the explicit expression for the mean load, we give asymptotic estimates for the load on a variety of graphs whose spectral density are well known. We conclude with numerical computation of the mean load for other well-known graphs without known spectral densities.

Virtual Network Embedding (VNE) that addresses the embedding problems of heterogeneous virtual networks onto a physical limited-capacity infrastructure efficiently is a major challenge in network virtualization (NV). VNE is computationally intractable when considering various constraints on nodes and links, and is also known as ${\mathcal{N}}{\mathcal{P}}$-hard even in offline embedding. Although the VNE problems have received attentions over recent decades with a vast number of VNE solutions, the majority of them only focus on VNE node mapping, whilst leaving the link mapping stage for the shortest path method or multicommodity flow (MCF) algorithm. We persuasively argue that node and link mappings equally play pivotal roles to approach an efficient VNE solution. In this paper, we reassess the role of link mapping stage in VNE problem, and then propose a novel intelligent VNE orchestration which effectively implements a distributed parallel model to reduce the operation time remarkably. Extensive evaluation results show that our proposed algorithm is not only faster than state-of-the-art VNE algorithms in speed, but also better in all performance metrics.

Reliable operation, test, debug and diagnosis of complex integrated systems are ensured by embedded instruments, such as sensors, aging monitors or Built-In Self-Test (BIST) registers. Reconfigurable Scan Networks (RSNs) offer a flexible and efficient way to access such test instruments throughout the whole life-cycle. However, improper RSN integration might introduce additional connectivity properties to the device under test (DUT), which can be exploited to perform unauthorized access or cause information leakage. The existence of such additional connectivity through the RSN can compromise the security of the DUT and is considered as a security threat.In this paper, a method is presented to resolve all such security compliance violations. The problem is formulated in terms of Integer Linear Programming (ILP) as a minimum cut problem in multicommodity flow. An efficient heuristic is presented, which, to our knowledge, for the first time allows to consider the whole set of violations simultaneously and thereby to find a minimized number of changes to the RSN structure in order to make it compliant with the initial security requirements of the DUT and prevent the information leakage through the scan chain.

In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a $1/4$-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of $8$.

The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of vertices can send and receive flow concurrently. The objective of MCFP is to find a maximum throughput and the flow corresponding to the throughput under a set of capacity constraints. We present an improved version of the Flow Deviation Method for the maximum concurrent flow problem, which was first presented by Daniel Bienstock and Olga Raskina in 2000. The algorithm is based on linear programming formulation involving Frank-Wolfe procedure and minimum-cost flow problem. The correctness of the algorithm is strictly proved and the performance is evaluated under several networks of different sizes.

Stable flows generalize the well-known concept of stable matchings to markets in which transactions may involve several agents, forwarding flow from one to another. An instance of the problem consists of a capacitated directed network in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk. Fleiner (Algorithms 7:1–14, 2014) established that a stable flow always exists by reducing it to the stable allocation problem. We present an augmenting path algorithm for computing a stable flow, the first algorithm that achieves polynomial running time for this problem without using stable allocations as a black-box subroutine. We further consider the problem of finding a stable flow such that the flow value on every edge is within a given interval. For this problem, we present an elegant graph transformation and based on this, we devise a simple and fast algorithm, which also can be used to find a solution to the stable marriage problem with forced and forbidden edges. Finally, we study the stable multicommodity flow model introduced by Kiraly and Pap (Algorithms 6:161–168, 2013). The original model is highly involved and allows for commodity-dependent preference lists at the vertices and commodity-specific edge capacities. We present several graph-based reductions that show equivalence to a significantly simpler model. We further show that it is $${\textsf {NP}}$$ -complete to decide whether an integral solution exists.

The paper presents a comparison between three approaches to solving the length-bounded maximum multicommodity flow problem with unit edge-lengths. Following the first approach, Garg and K?nemann?s, we developed an improved fully polynomial time approximation scheme for this problem. As the second alternative, we considered the well-known greedy approach. The third approach is the one that yields exact solutions by means of a standard LP solver applied to an LP model on the time-expanded network. Computational experiments are carried out on benchmark graphs and the graphs that model software defined satellite networks, to compare the proposed algorithms with an exact linear programming solver. The results of the experiments demonstrate a trade-off between the computing time and the precision of algorithms under consideration.

The Minimum Cost Hop-and-root Constrained Forest Problem (MCHCFP) is a combinatorial optimization problem that arises in the design of energy efficient wireless sensor networks with mobile sinks. It aims at providing a communication topology that minimizes energy consumption while controlling network latency and message loss due to communication failure. The problem is defined in terms of a mixed graph G = ( V , E , A ) with set of vertices V (representing the sensor nodes), edges E, arcs A, and parameters K , H ∈ N , and D ∈ R + . Each edge has an associated length, and each arc has an associated cost. The MCHCFP aims at finding a rooted spanning forest of (V, A) with minimum total cost. The solution must be hop constrained, in the sense that the path from any leaf to its root in the forest does not have more than H arcs, as well as distance constrained, so that one must be able to find K routes of length at most D, visiting exactly once the chosen roots of the forest. We study four integer programming formulations, two of them are new, the other two come from the literature. The first formulation coming from the literature is a multicommodity flow based model. The second is a Dantzig–Wolfe reformulation of the first. The two new formulations, which are equivalent with respect to their linear programming bounds, arise when the problem is formulated over a layered graph. To evaluate the bounds implied by the formulations other than the network flow model, we develop algorithms based on delayed column and/or row generation. We provide computational experiments showing that the best lower bounds are given by the formulations based on the layered graph. The reformulation coming from the literature provides lower bounds that are very close to those provided by the layered graph formulations, but in significantly less computational time. As it provides the best trade-off between lower bound quality and computational effort, that reformulation is thus chosen as the basis for a branch-and-price algorithm introduced here. Such an algorithm managed to solve instances with up to 60 vertices, a significant improvement over the previous approach in the literature, which systematically solves instances with up to 20 vertices.

Telecommunication networks can be seen as the stacking of several layers like, for instance, IP-over-Optical networks. This infrastructure should have sufficient capacities to route some demands between their origin-destination nodes. In this paper we consider the Capacitated Multi-Failure Survivable Network Design problem. We study two variants of this problem with simple and multiple capacities. We give two multicommodity flow formulations for each variant of this problem and describe some valid inequalities. In particular, we characterize valid inequalities obtained using Chvatal-Gomory procedure from the well known Cutset inequalities. We show that some of these inequalities are facet defining. We discuss separation routines for all the valid inequalities. Using these results, we develop a Branch-and-Cut algorithm and a Branch-and-Cut-and-Price algorithm for each variant and present extensive computational results.

Taxi planning problem studies aircraft routing and scheduling on the airport ground. Taxi planning has been formulated using a binary multicommodity flow model in a space-time airport network. The flow capacity constraints are used to represent the conflicts among aircraft, given an airport’s capacity. Branch and price methodology has been adapted to take advantage of the integer model structures. The computational tests have been run with real data from Adolfo Suárez Madrid-Barajas airport. The tests were oriented toward comparing the new adapted branch and price with the classic Branch and Bound algorithm, trying to obtain conclusions that are useful for airport managers.

This paper presents a fast and efficient method for load flow analysis of radial distribution networks. Here, an adaptive algorithm is proposed to analyze the load flow problem of distribution systems. An adaptive algorithm is the combination of backward/forward (BW/FW) sweep and cuckoo search (CS) algorithms. In the proposed method, the optimum load flow analysis of the radial distribution system is attained, while optimizing the voltage and current computation of the BW/FW sweep algorithm. Now, by the CS, the output voltage of the BW/FW sweep algorithm is compared with the standard voltage and optimized. From the optimized voltage and current, load flow parameters like power loss and real and reactive power flow are assessed. The proposed method is implemented using the MATLAB platform and tested into the IEEE 33 bus radial distribution system. The effectiveness of the proposed technique is determined by comparing with the BW/FW algorithm and genetic algorithm-based BW/FW algorithm.

The DC Power Flow approximation has been widely used for decades in both industry and academia due to its computational speed and simplicity, but suffers from inaccuracy, in part due to the assumption of a lossless network. Here we present a natural extension of the DC Power Flow to lossy networks. Our approach is based on reformulating the lossy active power flow equations into a novel fixed-point equation, and iterating this fixed-point mapping to generate a sequence of improving estimates for the active power flow solution. Each iteration requires the solution of a standard DC Power Flow problem with a modified vector of power injections. The first iteration returns the standard DC Power Flow, and one or two additional iterations yields a one or two order-of-magnitude improvement in accuracy. For radial networks, we give explicit conditions on the power flow data which guarantee (i) that the active power flow equations possess a unique solution, and (ii) that our iteration converges exponentially and monotonically to this solution. For meshed networks, we extensively test our results via standard power flow cases., Revision, 9 pages 3 figures. Revised version

Given a linear programming problem with the objective function coefficients vector c and a feasible solution x 0 to this problem, a corresponding inverse linear programming problem is to modify the vector c as little as possible to make x 0 form an optimal solution to the linear programming problem. The modifications can be measured by different distances. In this article, we consider the inverse linear programming problem under the bottleneck-type weighted Hamming distance. We propose an algorithm based on the binary search technique to solve the problem. At each iteration, the algorithm has to solve a linear programming problem. We also consider the inverse minimum cost flow problem as a special case of the inverse linear programming problems and specialize the proposed method for solving this problem in strongly polynomial time. The specialized algorithm solves a shortest path problem at each iteration. It is shown that its complexity is better than the previous one.

The feasibility problem of multicommodity flow is reduced to finding out if a multidimensional vector determined by the network parameters belongs to a convex polyhedral cone determined by the set of paths in the network. It is shown that this representation of the feasibility problem makes it possible to formulate the feasibility criterion described in [1] in a different form. It is proved that this criterion is sufficient. The concepts of reference vectors and networks are defined, and they are used to describe a method for solving the feasibility problem for an arbitrary network represented by a complete graph.

Flows over time problems consider finding optimal dynamic flows over a network where capacities and transit times on arcs are given. In this paper we study a multicommodity flow over time problem in which no storage of flow at nodes is allowed and solutions are restricted to loopless flow-paths. We propose an exact algorithm based on a column generation approach for a path-based linear programming model and present the results of a preliminary computational study.

Network virtualization helps overcome shortcomings of the current Internet architecture. The virtualized network architecture enables coexistence of multiple virtual networks (VNs) on an existing physical infrastructure. VN embedding (VNE) problem, which deals with the embedding of VN components onto a physical network, is known to be ${\mathcal {NP}}$ -hard. In this paper, we propose two VNE algorithms: MaVEn-M and MaVEn-S. MaVEn-M employs the multicommodity flow algorithm for virtual link mapping while MaVEn-S uses the shortest-path algorithm. They formalize the virtual node mapping problem by using the Markov decision process (MDP) framework and devise action policies (node mappings) for the proposed MDP using the Monte Carlo tree search algorithm. Service providers may adjust the execution time of the MaVEn algorithms based on the traffic load of VN requests. The objective of the algorithms is to maximize the profit of infrastructure providers. We develop a discrete event VNE simulator to implement and evaluate performance of MaVEn-M, MaVEn-S, and several recently proposed VNE algorithms. We introduce profitability as a new performance metric that captures both acceptance and revenue to cost ratios. Simulation results show that the proposed algorithms find more profitable solutions than the existing algorithms. Given additional computation time, they further improve embedding solutions.

This paper combines the multi-product variant of the capacitated facility location problem with multicommodity flow routing. This problem shares many similarities with the digital content placement and retrieval problem when minimizing the cost of installing a set of servers for storing multiple sets of data objects (files) and connecting clients to them in order to satisfy their demands while accounting for the induced arc load. However, the regular formulation of the facility location problem models the cost of allocating the demand originated by individual clients independently of the others. The combination of this problem with flow routing removes the demand allocation independence property, leading to strongly interrelated facility location and routing decisions. Moreover, involving multiple types of data objects yields facility capacity constraints with a more complex structure than the simple superposition of per-product constraints. This paper proposes a mixed integer programming formulation for this combined problem and evaluate the computational performance for solving it. Experimental results obtained with this combined formulation are provided and compared with those obtained when solving these two problems sequentially. With the latter, the routing cost increases (up to doubling) or the facility installation cost increases (up to requiring more than twice the number of facilities) compared to the cost values obtained by solving the combined problem. This paper also extends the combined model with demand rerouting to evaluate its cost gain compared to demand protection as provided by the reliable facility location model. The results obtained with the combined formulation indicate that when subject to representative failure probabilities, demand rerouting can significantly outperform demand protection up to a factor four.

Detailed routing is an important stage in very large scale integrated physical design. Due to the extreme scaling of transistor feature size and the complicated design rules, ensuring routing completion without design rule checking (DRC) violations becomes more and more difficult. Studies have shown that the low routing quality partly results from nonoptimal net-ordering nature of traditional sequential methods. The concurrent routing strategy is always based on an NP-hard model, thus is at a disadvantage in runtime. In this paper, we present a novel concurrent detailed routing algorithm that routes all nets simultaneously. Based on the multicommodity flow model, detailed routing problem with complex design rule constraints is formulated as an integer linear programming. Some model simplification heuristics and efficient model solving algorithms are proposed to improve the runtime. Experimental results show that, the proposed algorithms can reduce the DRC violations by 80%, meanwhile can reduce wirelength and via count by 5% and 8% compared with an industry tool. In addition, the proposed algorithm is general that it can be adopted as an incremental detailed router to refine a routing solution, so the number of DRC violations that industry tool cannot fix are further reduced by 27%.

We study the following all-or-nothing multicommodity flow problem in planar graphs. Input: A graph G with n vertices and k pairs of vertices (s1, t1), (s2, t2),..., (sk, tk) in G. Find: A largest subset W of {1, ...., k such that for every i in W, we can send one unit of flow between si and ti. This problem is different from the well-known maximum edge-disjoint paths problem in that we do not require integral flows for the pairs. This problem is APX-hard even for trees, and a 2-approximation algorithm is known for trees. For general graphs, Chekuri et al. (STOC'04) give a poly-logarithmic factor approximation algorithm and show that a natural LP-relaxation has a poly-logarithmic integrality gap. This result is in contrast with the integrality gap Ω(√n) for the maximum edge-disjoint paths problem. Our main result considerably strengthens this result when an input graph is planar. Namely, for the all-or-nothing multicommodity flow problem in planar graphs, we give an O(1)-approximation algorithm and show that the integrality gap is O(1). In particular, in polynomial time, we can find an index set W with |W| = Ω(OPT) and eight si-ti paths for each i in W such that each edge is used at most eight times in these paths (with multiplicity), where OPT is the optimal value of the LP-relaxation of the all-or-nothing multicommodity flow problem. Our result can be compared to the recent result by S'eguin-Charbonneau and Shepherd (FOCS'11) who give an O(1)-approximation algorithm for the maximum edge-disjoint paths problem in planar graphs with congestion 2 (but not implied by this result).

Achieving high penetration of electric vehicles (EVs) is one of the objectives proposed by the scientific community to mitigate the negative environmental impact caused by conventional mobility. The limited autonomy and the excessive time to recharge the battery discourage the final consumer from opting for new environmentally friendly mobility alternatives. Consequently, it is essential to provide the urban road network with charging infrastructure (CI) to ensure that the demand generated by EV users is met. The types of terminals to be considered in charging stations (CS) are fast and ultra-fast. The high energy requirements in these types of terminals could stress the electrical systems, reducing the quality of service. To size and forecast the resources needed in CI, it is of great interest to model and predict the maximum number of EVs, in each hour, that each CS will have to serve according to the geographic area in which they are located. Our proposal is not based on an assumed number of vehicles to be served by each CS, but rather it is based on the analysis of vehicular traffic in geo-referenced areas, so that the load managers can design the topology of the CS. The maximum vehicular concentration is determined by some considerations such as the road system, direction of the route, length of the road segment, the intersections, and the economic zone to which it belongs. The topology of the road map is freely extracted from OpenStreetMap to know the latitude and longitude coordinates. Vehicular traffic will be modeled through the topology obtained from OpenStreetMap and other microscopic variables to understand the traffic engineering constraints. In addition, the Hungarian algorithm is used as a minimum cost decision tool to allocate demand to the CS by observing vehicular traffic as a cost variable. The multi commodity flow problem (MCFP) algorithm aims to make commodities flow through the road network with the minimum cost without exceeding the capacities of the road sections. Therefore, it is proposed to solve the transportation problem by directing the vehicular flow to the CS while minimizing the travel time. This situation will contribute significantly to the design of the topology of each CS, which will be studied in future research.

This paper introduces a variant of the well-known Multi-Depot Periodic Vehicle Routing Problem, which is inspired by a real situation of a distribution company. The problem consists in determining the number of extra vehicles to rent, the assignment of vehicles to plants, and the routes between plants and distribution centers, while the transportation cost is minimized. We propose a mixed integer linear formulation and a Reactive Greedy Randomized Adaptive Search Procedure to solve the problem. Extensive computational results show that the proposed procedure provides high-quality solutions with an average gap lower than 2.5% from the computed lower bound.

This study aims to develop a network model driven platform that supports decision-makers to make well-informed decisions for the efficient water supplies, taking Saudi Arabia as a case study. The water/energy network analysis should be able to identify optimal locations for sustainable desalination infrastructure investments, accounting for the existing assets and the current investment plans. The geographical aspect of individual resource production and distribution can be quantitatively handled by a graph-theoretic approach. This study employs a new multicommodity network flow model called the INFINIT (interdependent network flows with induced internal transformation) model, which enables to address water-energy nexus issues and to optimize the flow of multiple resources as well as placement of new water/energy facilities at the individual facility level. The INFINIT model in this study formulates and solves mixed-integer linear programming (MILP) problems to minimize the designated multi-objective functions of the total cost and CO2 emission. As a result of optimization, the Pareto-optimal solutions with different network flow topology and the downselected potential locations for new facilities are obtained. To effectively visualize alternative design and policy scenarios, two ways of visualization of the results are developed: a MATLAB-based graphical user interface and tabletop 3D map projection.

The proliferation of cloud computing has forced data centers to support a large number of dynamic resources such as virtual machines and storage volumes from any physical location within the data center. This has led to highly volatile and unpredictable traffic patterns. The emergence of cloud applications that exchange large volumes of information have created large persistent flows that need to coexist with other types of traffic. As a result, a number of data center topologies have been proposed to support cloud applications. One of the topologies that has gained prominence is the Clos network. On one hand, Clos networks provide many nice properties, such as equidistant hops, bandwidth, and latency. On the other hand the routing of diverse traffic flows still remains an issue. Current routing methods such as equal-cost multi-path (ECMP) routing that rely on flow hashing over equal cost paths do not take into consideration traffic volume nor network state. In this paper, we investigate routing in Clos topologies. We formulate optimal flow routing in Clos networks as a binary multicommodity flow problem and present optimized flow re-routing, a modified version of the binary multicommodity flow problem that uses a heuristics approach to minimize hash collisions. We also propose FlowFit, a practical optimization method that uses network state to optimally re-assign flows to links. Our experimental and simulation results show a significant improvement in bisection bandwidth and flow completion time over ECMP.

A major problem in communication networks is how to efficiently define the routing paths and to allocate bandwidths in order to satisfy a given collection of transmission requests. In this paper, we study this routing problem by modeling it as a bi-objective single path multicommodity flow problem (SMCFP). Two conflicting objective functions are simultaneously optimized: the delay and reliability of the generated paths. To tackle the complexity of this problem (NP-hard), most of the existing studies proposed approximate methods and metaheuristics as solution approaches. In this paper, we propose to adapt the augmented $$\epsilon $$ -constraint method in order to solve small sized instances of the bi-SMCFP. For large scale problems, we develop three metaheuristics: a multiobjective multi-operator genetic algorithm, an adaptive multiobjective variable neighborhood search and new hybrid method combining the $$\epsilon $$ -constraint with the evolutionary metaheuristic. The idea of the hybridization schema is to first use the metaheuristic to generate a good approximation of the Pareto front, then to enhance the quality of the solutions using the $$\epsilon $$ -constraint method to push them toward the exact Pareto front. An intelligent decomposition scheme is used to reduce the size of the search space before applying the exact method. Computational results demonstrate the efficiency of the proposed hybrid algorithm using instances derived from real network topology and other randomly generated instances.