Search

In this paper, we propose a new global routing algorithm supporting advance reservation. A predefined number of messages are to be routed in a capacitated network including a set of nodes that can be producers and/or consumers of information. We assume that the same information can be held by different sources. We first propose the non-linear mathematical formulation for this problem by extending the single path multicommodity flow formulation. To solve such an NP -hard optimization problem, we develop a multi-start variable neighborhood search method (MVNS). The results of extensive computational experiments across a variety of networks from the literature are reported. For small and medium scale instances, the results are compared with the optimal solution generated by LINGO in terms of time and optimality. For large size instances, a comparison to a state-of-the-art ant colony system approach is performed. The obtained results show that the MVNS algorithm is computationally effective and provides high-quality solutions.

This study uses a minimum cost flow method to solve a dispatch problem in order to minimize the consumption of coal in the dispatching of a thermal power system. Low-carbon generation dispatching is also considered here since the scheduling results are consistent with energy-saving generation dispatch. Additionally, this study employs minimum coal consumption as an objective function in considering the output constraints, load balance constraints, line loss, ramp rate limits, spinning reverse needs, prohibited operating zone requirements, security constraints, and other common constraints. The minimum cost flow problem, considering the loss of network flow, is known as a generalized network flow problem, which can be expressed as a quadratic programming problem in mathematics. Accordingly, the objective function was solved by LINGO11, which was used to calculate a network in a single time; a continuous period dispatch plan was obtained by accumulating each period network flow together. This analysis proves it feasible to solve a minimal cost flow problem with LINGO11. Theoretical analysis and numerical results prove the correctness and effectiveness of the proposed method.

a model for network load balancing is considered. Network consists of computational nodes, some pairs of them are connected via communication channel. Initially some tasks are distributed between the nodes. Each task can be either resolved by the node the task is currently assigned to either sent the task to some of the node's neighbour. Assuming that communication channels have restricted capacity and there can be large amount of data to be transferred the problem of finding minimum possible time required for resolving all the tasks is considered. Here we present an approach for this model based on solving parametric flow problem. Such approach allows easy solution of the problem in presence of restricted communication capacities (those are usually discarded from the problem formulation or treated roughly).

This chapter is devoted to modeling and optimization techniques applicable to communication network design and planning. The main emphasis is put on the models dealing with optimization of the capacity of network resources and traffic routing that lead to tractable optimization problems. It is a common belief that the right means for such modeling are multicommodity flow networks (MFN). MFN form a field of operations research on its own, and are closely connected to integer programming. In consequence, the presented chapter aims at giving a systematic survey of basic MFN models and integer programming methods applicable to communication network design.

We propose a dynamic energy balanced max flow routing algorithm to maximize load flow within the network lifetime and balance energy consumption to prolong the network lifetime in an energy-harvesting wireless sensor network. The proposed routing algorithm updates the transmission capacity between two nodes based on the residual energy of the nodes, which changes over time. Hence, the harvested energy is included in calculation of the maximum flow. Because the flow distribution of the Ford–Fulkerson algorithm is not balanced, the energy consumption among the nodes is not balanced, which limits the lifetime of the network. The proposed routing algorithm selects the node with the maximum residual energy as the next hop and updates the edge capacity when the flow of any edge is not sufficient for the next delivery, to balance energy consumption among nodes and prolong the lifetime of the network. Simulation results revealed that the proposed routing algorithm has advantages over the Ford–Fulkerson algorithm and the dynamic max flow algorithm with respect to extending the load flow and the lifetime of the network in a regular network, a small-world network, and a scale-free network.

The Multiplicative Weights Update method (MWU) is a simple yet powerful algorithm for learning linear classifiers, for ensemble learning a la boosting, for approximately solving linear and semidefinite systems, for computing approximate solutions to multicommodity flow problems, and for online convex optimization, among other applications. In this brief announcement, we apply techniques from interactive theorem proving to define and prove correct the first formally verified implementation of MWU (specifically, we show that our MWU is no regret). Our primary application -- and one justification of the relevance of our work to the PODC community -- is to verified multi-agent systems, such as distributed multi-agent network flow and load balancing games, for which verified MWU provides a convenient method for distributed computation of approximate Coarse Correlated Equilibria.

We show the strong-convexity assumption of regularization-based methods for solving bilinear saddle point problems may be relaxed to a weaker notion of area-convexity with respect to an alternating bilinear form. This allows bypassing the infamous '' barrier for strongly convex regularizers that has stalled progress on a number of algorithmic problems. Applying area-convex regularization, we present a nearly-linear time approximation algorithm for solving matrix inequality systems A X ≤ B over right-stochastic matrices X. By combining that algorithm with existing work on preconditioning maximum-flow, we obtain a nearly-linear time approximation algorithm for maximum concurrent flow in undirected graphs: given an undirected, capacitated graph with m edges and k demand vectors, the algorithm takes O(mke'1) time and outputs k flows routing the specified demands with total congestion at most (1+e) times optimal.

This work is dealing with train timetabling problem. In the first chapter, one can find an introduction to network flows which is needed for understanding deeper concepts later on. Namely, basic graph theory definitions are stated as well as core problems like the minimum cost flow and shortest path problem. Furthermore, two equivalent representations of network flows are described, including some useful properties connected to each of them. At the end of the chapter, linear programming and simplex method are introduced into some detail. In the second chapter more complex theory is introduced. At the beginning, multi-commodity flow problem is stated and few solutions approaches are briefly described. Once we settled for one of them, the rest of the chapter is dealing with Lagrangian relaxation and column generation techniques. Since column generation is the main result needed for solving our problem, some finer results, like determining lower and upper bounds, are stated. In the last, third chapter, one can find a model for representing train timetabling problem for a single line network. That model was introduced by Valentina Cacchiani in her Ph.D. thesis. In this work, periodicity of timetable is assumed because it makes computations way quicker, as well as it has some other benefits. At the end, one can find an algorithm based on column generation technique for solving introduced model. That algorithm is based on 6 steps, and after reading this work, one should be able to fully understand each of them. Ovaj rad bavi se problemom rasporeda vožnje u željezničkom prometu. U prvom poglavlju nalazi se uvod u mrežne tokove koji je potreban za razumijevanje naprednijih koncepata. Konkretno, iskazane su osnovne definicije teorije grafova kao i neki temeljni problemi poput problema najjeftinijeg toka i problema najkraćeg puta. Nadalje, opisana su dva ekvivalenta prikaza mrežnih tokova, uključujući neka korisna svojstva za svaki od njih. Na kraju poglavlja, linearno programiranje i simpleks metoda, objašnjeni su na razini razumijevanja. U drugom poglavlju nalazi se naprednija teorija koja se nadovezuje na prvo poglavlje. Na početku poglavlja prikazan je problem više dobara, kao i nekoliko pristupa rješavanju navedenog problema. Nakon što smo se odlučili za jedan od pristupa, ostatak poglavlja bavi se Lagrangeovom relaksacijom i metodom generacije stupaca. Kako je upravo metoda generacije stupaca najvažniji rezultat za rješavanje našega problema, napredniji rezultati vezani uz određivanje donjih i gornjih granica su detaljno objasnjeni. U posljednjem, trećem poglavlju, nalazi se model za prikazivanje problema rasporeda vožnje za mreže s jednom tračnicom. Navedeni model prvi puta je predstavljen u doktorskom radu Valentine Cacchiani. U ovom radu također pretpostavljamo periodičnost rasporeda vožnje kako bismo, između ostalih, ostvarili prednost poput bržeg vremena računanja. Na kraju rada nalazi se algoritam, temeljen na metodi generacije stupaca, za rješavanje predstavljenog modela. Navedeni algoritam sastoji se od 6 koraka, od kojih je svaki detaljno opisan u ovome radu.

We study the approximability of the All-or-Nothing multicommodity flow problem in directed graphs with symmetric demand pairs (SymANF). The input consists of a directed graph $$G = (V, E)$$G=(V,E) and a collection of (unordered) pairs of nodes $$\mathcal {M}= \left\{ s_1t_1, s_2t_2, \ldots , s_kt_k\right\} $$M=s1t1,s2t2,?,sktk. A subset $$\mathcal {M}'$$M? of the pairs is routable if there is a feasible multicommodity flow in $$G$$G such that, for each pair $$s_it_i \in \mathcal {M}'$$siti?M?, the amount of flow from $$s_i$$si to $$t_i$$ti is at least one and the amount of flow from $$t_i$$ti to $$s_i$$si is at least one. The goal is to find a maximum cardinality subset of the given pairs that can be routed. Our main result is a poly-logarithmic approximation with constant congestion for SymANF. We obtain this result by extending the well-linked decomposition framework of Chekuri et al. (2005) to the directed graph setting with symmetric demand pairs. We point out the importance of studying routing problems in this setting and the relevance of our result to future work.

In this paper, we introduce a network design problem with two-edge matching failures. Given a graph, any two edges non-incident to the same node form a two-edge matching. The problem consists in finding a minimum-cost subgraph such that, when deleting any two-edge matching of the graph, every pair of terminal nodes remains connected. We give mixed integer linear programming formulations for the problem and propose a heuristic algorithm based on the Branch-and-Bound method to solve it. We also present computational results.

We present an alternative linear programming formulation of the maximum concurrent flow problem MCFP termed the triples formulation. The standard formulations in the literature are the edge-path and node-edge formulations, which are known to be equivalent due to the Flow Decomposition Theorem. We present algorithms for deriving a triples solution from an edge-path solution and vice versa, and hence show that all three formulations are equivalent. Our new formulation leads to more compact linear programs than either the edge-path or node-path formulations. We show that the triples formulation often has half the number of rows and half the number of columns compared to the node-edge formulation. We report computational results comparing the solution times using the three formulations and the state-of-the-art linear programming solver CPLEX on a set of popular problem instances from the literature and a set of instances defined on random geometric graphs. The results indicate that the triples formulation can be solved more efficiently than the other two. We found that the CPLEX linear programming solvers solved 89% of the MCFP instances in our computational study faster with the triples formulation than it did with the other two formulations, typically two to four times faster than the node-edge formulation when available computer memory allowed both to be solved. The triples formulation appears to be particularly well suited for problem instances defined on dense graphs; on average, CPLEX solved these types of problems in our study 10 times faster with the triples formulation. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 651, 68-87. 2015

This study investigates a heuristic routing and wavelength assignment (RWA) scheme for an optical-carrier-reusable ring network. This network has two unique features. First, only one light source, called the multi-carrier light source, is required which eases the difficulty of controlling many light source devices. Second, optical carriers are reused in order to improve the efficiency of wavelength usage. Given the target of wavelength-resource-efficient channel establishment, performance of the heuristic RWA scheme is evaluated. To realise efficient wavelength usage, the authors formulate the RWA problem as an integer linear programming (ILP) problem of obtaining the minimum number of required wavelengths for given requests. With the ILP approach, the calculation process is not tractable in practical time. The heuristic RWA scheme introduced in this study solves the RWA problem. This scheme consists of two algorithms. Channel routes are obtained by the routing algorithm, and the wavelength assignment algorithm is then performed to assign a wavelength to each route. Moreover, two candidates, considering the shortest path and considering the avoidance of wavelength conversion, for the routing algorithm are examined. Numerical results show that the first candidate is more suitable in terms of reducing the number of required wavelengths than the second candidate.

The scheduling optimization of the flow line is a core of modern managing technology and Data Processing. The goal of the problem is to minimize the sum of the total flow time. Aiming at machine scheduling of production process, this paper presents a genetic algorithm based heuristic for the problem. An encoding method based working procedure and parthenogenetic operations are applied to solve the flow line scheduling problem. The computational results indicate that the proposed approach is effective in terms of reduced makespan for the attempted problems.

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {ue?e ? E} and edge-costs {ce?e ? E}, source-sink pair s, t ? V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ? B, E) and an integer k > 0. The goal is to find a node subset S ⊆ A ? B of minimum size |S| such G has k pairwise edge-disjoint paths between S ? A and S ? B. We give an O(klogk)$O(\sqrt {k\log k})$ approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {bv : v ? V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log3+??n approximation scheme for it using Group Steiner Tree techniques.

In this paper, a three-stage assembly flow shop scheduling problem with machine availability constraints is taken into account. Two objectives of minimising total weighted completion times (flow time) and minimising sum of weighted tardiness and earliness are simultaneously considered. To describe this problem, a mathematical model is presented. The problem is generalisation of three-machine flow shop scheduling problem and two-stage assembly flow shop scheduling problem. Since these problems are known to be NP-hard, the considered problem is also strongly NP-hard. Therefore, two multi-objective meta-heuristics are presented to efficiently solve this problem in a reasonable amount of time. Comprehensive computational experiments are performed to illustrate the performance of the presented algorithms.

This paper proposes a new algorithm to find a representation of the set of all non-dominated points of the bi-objective integer network flow problem. The algorithm solves a sequence of e-constraint problems with a branch-and-bound algorithm to find a subset of non-dominated points that represents the set of all non-dominated points well in the sense of coverage or uniformity. At each iteration of the algorithm, one non-dominated point, determined by solving one e-constraint problem, is added to the representation until it is guaranteed that the representation has the desired quality. Computational experiments on different problem types show the efficacy of the algorithm.

We examine in this article when it is possible to predict, without numerical computation, the direction of change of optimal multicommodity flows on suspension graphs resulting from changes in arc-commodity parameters. Using results of Evans (Oper Res 26 (1978), 673–679) and of Soun and Truemper (SIAM J Algebr Discrete Meth 1 (1980), 348–358), the multicommodity flow problem on a graph that is two-isomorphic to a suspension graph is reduced to a single-commodity flow problem on an enlarged graph, called a “rolodex graph.” Such a reduction allows us to apply results of Granot and Veinott (Math Oper Res 10 (1985), 471–497), developed for single-commodity network-flow problems, to derive qualitative sensitivity analysis results for multicommodity flow problems on graphs which are two-isomorphic to suspension graphs. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(2), 65–75 2014

Thanks to its high dimensionality and a usually non-convex constraint set, system optimal dynamic traffic assignment remains one of the most challenging problems in transportation research. This paper identifies two fundamental properties of the problem and uses them to design an efficient solution procedure. We first show that the non-convexity of the problem can be circumvented by first solving a relaxed problem and then applying a traffic holding elimination procedure to obtain the solution(s) of the original problem. To efficiently solve the relaxed problem, we explore the relationship between the relaxed problems based on different traffic flow models (PQ, SQ, CTM) and a minimal cost flow (MCF) problem for a special space-expansion network. It is shown that all the four problem formulations produce the same minimal system cost and share one common solution which does not involve inside queues in the network. Efficient solution algorithms such as the network simplex method can be applied to solve the MCF problem and identify such an optimal traffic pattern. Numerical examples are also presented to demonstrate the efficiency of the proposed solution procedure.

In [Bianco, L., Giuseppe C., and P. Reverberi. 2001. "A network based model for traffic sensor location with implications on O/D matrix estimates". Transportation Science 35(1):50-60.], the authors present the Sensor Location Problem: that of locating the minimum number of traffic sensors at intersections of a road network such that the traffic flow on the entire network can be determined. They offer a necessary and sufficient condition on the set of monitored nodes in order for the flow everywhere to be determined. In this paper, we present a counterexample that demonstrates that the condition is not actually sufficient (though it is still necessary). We present a stronger necessary condition for flow calculability, and show that it is a sufficient condition in a large class of graphs in which a particular subgraph is a tree. Many typical road networks are included in this category, and we show how our condition can be used to inform traffic sensor placement., Comment: Submitted for peer review on October 3, 2010

It was about 40 years ago that the ARPANET had surpassed 40 nodes and was rapidly growing at the rate of one node per month. The first government and commercial P/S networks were emerging. Designing an efficient topology and flow assignment strategy that could meet the requirements at lowest costs was essential in order to outperform the competition represented by circuit-switched or private-line networks. The challenge was to solve a combined flow and capacity assignment problem. Researchers at UCLA, under Len Kleinrock’s leadership and DARPA support, developed a method based on multicommodity flow and non-linear programming principles called the Flow Deviation (FD) algorithm. The key underlying technique was to “deviate flows” on incrementally improving paths until the optimum was reached. In the early days, the FD algorithm was used to design and “upgrade” the growing ARPANET topology. After the ARPANET topology became stable, the FD algorithm took on a life of its own as an intuitive, efficient method to solve a variety of network flow problems in different domains, from ARPANET packets to WDM wavelengths, urban traffic cars and SDN tunnels, as reflected in the over 500 citations. This paper reviews the key concepts and features of the FD algorithm as published in 1973, traces the various problems and scenarios to which it has been applied (most recently, vehicular traffic management) and discusses the possible use of FD in today’s SDN tunnel allocation.

In this paper, we study the problem of minimum-cost multicast with network coding, while the maximum end-to-end weight, such as delay, throughput, and security, along paths from the source to each destination is bounded by a constant. We propose a path-based mixed integer programming model for the problem and show that the problem is non-deterministic polynomial (NP)-hard. We apply a column-generation approach to solve this model, where the problem is decomposed into a master linear programming problem and several integer programming sub-problems. We also introduce an approach to get a lower bound of optimal solution. Simulation results demonstrate that using of column-generation approach in combination with network coding to solve this problem can enhance the efficiency of final solution, no matter of the size of underlying network.

The multiple-unicast network coding conjecture states that for multiple unicast sessions in an undirected network, network coding is equivalent to routing. Simple and intuitive as it appears, the conjecture has remained open since its proposal in 2004, and is now a well-known unsolved problem in the field of network coding. Based on a recently proposed tool of space information flow, we present a geometric framework for analyzing the multiple-unicast conjecture. The framework consists of four major steps, in which the conjecture is transformed from its throughput version to cost version, from the graph domain to the space domain, and then from high dimension to 1-D, where it is to be eventually proved. We apply the geometric framework to derive unified proofs to known results of the conjecture, as well as new results previously unknown. A possible proof to the conjecture based on this framework is outlined.

The maximum flow problem is one of the classic combinatorial optimization problems with many applications in electrical power systems, communication networks, computer networks and logistic networks. The goal of the problem is to find the maximum amount of flow from the source to the sink in a network. A network is called uncertain if the arc capacities of the network are uncertain variables. The main purpose of this paper is to solve the maximum flow in an uncertain network by under the framework of uncertainty theory.

This paper deals with multi-commodity flow problem with fractional objective function. The optimality conditions and the duality concepts of this problem are given. For this aim, the fractional linear programming formulation of this problem is considered and the weak duality, the strong direct duality and the weak complementary slackness theorems are proved applying the traditional duality theory of linear programming problems which is different from same results in Chadha and Chadha (2007) [1]. In addition, a strong (strict) complementary slackness theorem is derived which is firstly presented based on the best of our knowledge. These theorems are transformed in order to find the new reduced costs for fractional multi-commodity flow problem. These parameters can be used to construct some algorithms for considered multi-commodity flow problem in a direct manner. Throughout the paper, the boundedness of the primal feasible set is reduced to a weaker assumption about solvability of primal problem which is another contribution of this paper. Finally, a real world application of the fractional multi-commodity flow problem is presented.

As urbanization increases and new business models for transportation and mobility arise, the design of transportation networks should no longer be done in a vacuum. Design interactions between multiple networks have largely been analyzed either as non-cooperative games with non-unique Nash equilibria, even if assumptions needed for such games are not satisfied, or using knowledge-based or agent-based methods that cannot explicitly quantify network sensitivities. A new framework is proposed to model network design in the presence of coexisting networks using multiobjective optimization in a novel manner to identify symbiotic relationships. The framework does not require strict assumptions about availability of information or timing of decisions, and it can be used to examine network sensitivities that knowledge-based methods cannot. A bundled discount pricing problem and subsidy problem are derived from the symbiotic relationships. The framework is applied to formulate a symbiotic bike-sharing network design problem in the presence of a coexisting transit system as a departure-time-elastic multicommodity flow problem. A small network example demonstrates the potential dependency between transit systems and bike-sharing systems for the first time, and the existence of an optimal discount value for considering bundled fares. A larger bike-sharing network, BIXI, is examined in the presence of the Toronto Transit Commission (TTC) in downtown Toronto to address the question of subsidy. It is found that BIXI is operating in a relatively transit-friendly state, and subsidy by TTC to maintain a status quo in Toronto may be worth considering if the cost of subsidy is less than a conservative average reduction achieved of 2.43 units of transit-only user cost for every 1 unit increase of bike-sharing cost.

The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when all sources are in the first echelon and all sinks are in two echelons, and when there is a single source but many sinks in multiple echelons. The polynomiality argument relies on a combination of a particular dynamic programming formulation and an investigation of the extreme points of the underlying flow polyhedron. We derive an analytical formula for the inflow into any node in an extreme point solution, which generalizes a result of Zangwill (Manag Sci 14(7):429---450, 1968) for the multi-echelon lot-sizing problem.

In this study we deal with network routing decisions and approximate performance evaluation approaches for generalized open queuing networks (OQN), in which commodities enter the network, receive service at one or more arcs and then leave the network. Exact performance evaluation has been applied for the analysis of Jackson OQN, where the arrival and service processes of the commodities are assumed to be Poisson. However, the Poisson processes’ hypotheses are not a plausible or acceptable assumption for the analysis of generalized OQN, as their arrival and service processes can be much less variable than Poisson processes, resulting in overestimated system performance measures and inappropriate flow routing solutions. In this paper we merge network routing algorithms and network decomposition methods to solve multicommodity flow problems in generalized OQN. Our focus is on steady-state performance measures as average delays and waiting times in queue. The main contributions are twofold: (i) to highlight that solving the corresponding multicommodity flow problem by representing the generalized OQN as a Jackson OQN may be a poor approximation and may lead to inaccurate estimates of the system performance measures, and (ii) to present a multicommodity flow algorithm based on a routing step and on an approximate decomposition step, which leads to much more accurate solutions. Computational results are presented in order to show the effectiveness of the proposed approach.

The network of delivering commodities has been an important design problem in our daily lives and many transportation applications. The reliability of delivering commodities from a source node to a sink node in the network is maximised to find the optimal routing. However, the design problem is not simple due to randomly distributed attributes in each path, multiple commodities with variable path capacities and the allowable time constraints for delivery. This paper presents the design optimisation of the multi-state flow network MSFN for multiple commodities. We propose an efficient and robust approach to evaluate the system reliability in the MSFN with respect to randomly distributed path attributes and to find the optimal routing subject to the allowable time constraints. The delivery rates of the path segments are evaluated and the minimal-speed arcs are eliminated to reduce the complexity of the MSFN. Accordingly, the correct optimal routing is found and the worst-case reliability is evaluated. The reliability of the optimal routing is at least higher than worst-case measure. Three benchmark examples are utilised to demonstrate the proposed method. The comparisons between the original and the reduced networks show that the proposed method is very efficient.

We consider the problem of finding an optimal mining sequence for an open pit during a number of time periods subject to only spatial and temporal precedence constraints. This problem is of interest because such constraints are generic to any open-pit scheduling problem and, in particular, because it arises as a Lagrangean relaxation of an open-pit scheduling problem. We show that this multi-period open-pit mining problem can be solved as a maximum flow problem in a time-expanded mine graph. Further, the minimum cut in this graph will define an optimal sequence of pits. This result extends a well-known result of J.-C. Picard from 1976 for the open-pit mine design problem, that is, the single-period case, to the case of multiple time periods.

In the planning and operation of distribution network, flow calculation and optimal flow is the hot issue for many experts and scholars to study. In network reconfiguration, service restoration and capacitor configuration, it needs hundreds even thousands times of power flow calculation. So it is very important to propose a suitable optimization algorithm. Based on the three-phase model we proposed hybrid particle swarm algorithm to calculate the three-phase power flow. The method uses the superposition principle. The distribution network is divided into two network models, one is the pure radial network without cyclic structure, and another is the pure cyclic network without radiation structure. We do iterative calculation respectively using hybrid particle algorithm, getting the calculation results. The hybrid algorithm is a new reference for the future optimization of power flow calculation in this paper.

The present paper discusses enhanced flow in a capacitated indefinite quadratic transportation problem. Sometimes, situations arise where either reserve stocks have to be kept at the supply points say, for emergencies, or there may be extra demand in the markets. In such situations, the total flow needs to be controlled or enhanced. In this paper, a special class of transportation problems is studied, where the total transportation flow is enhanced to a known specified level. A related indefinite quadratic transportation problem is formulated, and it is shown that to each basic feasible solution called corner feasible solution to related transportation problem, there is a corresponding feasible solution to this enhanced flow problem. The optimal solution to enhanced flow problem may be obtained from the optimal solution to the related transportation problem. An algorithm is presented to solve a capacitated indefinite quadratic transportation problem with enhanced flow. Numerical illustrations are also included in support of the theory. Computational software GAMS is also used.

The aim of this paper is to give an uncertainty distribution of the least cost of shipment of a commodity through a network with uncertain capacities. Uncertainty theory is used to deal with uncertain capacities, and an $$\alpha $$ ? -minimum cost flow problem model is proposed. After defining the $$\alpha $$ ? -minimum cost flow, the properties of the model are analyzed, and then an algorithm for uncertain minimum cost flow problem is developed. The algorithm can be considered as a general solution to the uncertain minimum cost flow problem. To demonstrate the efficiency of the proposed algorithm, a numerical example is illustrated.

We consider the multicommodity network flow formulation of the multiple depot vehicle scheduling problem (MDVSP) and investigate several strategies within a branch-and-cut framework for solving the MDVSP. In particular, we compare subalgorithms for separating the cutting planes introduced by Hadjar et al. (Oper Res 54:130–149, 2006). We also evaluate the effectiveness of a new criterion for fixing some variables in the multicommodity flow formulation. Finally, we present computational experiments to illustrate the strengths and weaknesses of the strategies.

Routing and wavelength assignment (RWA) is the most concern in wavelength routed optical networks. This paper proposes a novel binary quadratic programming (BQP) formulation for the static RWA problem in order to balance traffic load among a network links more fairly. Subsequently, a greedy heuristic algorithm namely variable-weight routing and wavelength assignment (VW-RWA) is proposed to solve the developed BQP problem. In this method, the weight of a link is proportional to the link congestion. Performance evaluation results for different practical network topologies show that our proposed algorithm can decrease the number of required wavelengths in the network, blocking rate and variance of used wavelengths in each link. Besides, it is shown that the number of required wavelengths to establish call requests for a given network topology can be reduced at lower cost compared to other heuristics.

The article discuses a number of fundamental results related to determining the maximum output flow in a network after edge failures. On the basis of four theorems, we propose very efficient augmentation algorithms for restoring the maximum possible output flow in a repairable flow network, after an edge failure. In many cases, the running time of the proposed algorithm is independent of the size of the network or varies linearly with the size of the network. The high computational speed of the proposed algorithms makes them suitable for optimising the performance of repairable flow networks in real time and for decongesting overloaded branches in networks. We show that the correct algorithm for maximising the flow in a static flow network, with edges fully saturated with flow, is a special case of the proposed reoptimisation algorithm, after transforming the network into a network with balanced nodes. An efficient two-stage augmentation algorithm has also been proposed for maximising the output flow in a network with empty edges. The algorithm is faster than the classical flow augmentation algorithms. The article also presents a study on the link between performance, topology and size of repairable flow networks by using a specially developed software tool. The topology of repairable flow networks has a significant impact on their performance. Two networks built with identical type and number of components can have very different performance levels because of slight differences in their topology.

A two-phase approach for the train unit scheduling problem is proposed. The first phase assigns and sequences train trips to train units temporarily ignoring some station infrastructure details. Real-world scenarios such as compatibility among traction types and banned/restricted locations and time allowances for coupling/decoupling are considered. Its solutions would be near-operable. The second phase focuses on satisfying the remaining station detail requirements, such that the solutions would be fully operable. The first phase is modeled as an integer fixed-charge multicommodity flow (FCMF) problem. A branch-and-price approach is proposed to solve it. Experiments have shown that it is only capable of handling problem instances within about 500 train trips. The train company collaborating in this research operates over 2400 train trips on a typical weekday. Hence, a heuristic has been designed for compacting the problem instance to a much smaller size before the branch-and-price solver is applied. The process is iterative with evolving compaction based on the results from the previous iteration, thereby converging to near-optimal results. The second phase is modeled as a multidimensional matching problem with a mixed integer linear programming (MILP) formulation. A column-and-dependent-row generation method for it is under development.

In this paper, a new design optimization method-cross entropy methods for passenger flow routing in passenger hubs is employed, in order to develop rational and efficient passenger flow routing program, which will help improving the passenger flow organization. According to the description and characteristics of the problem, we transform the problem into a combinatorial optimization problem, so that it is convenient to explore the best solution. The numerical example declares that the method given above can obtain the optimal solution under the condition of fixed demand. Results show that the cross entropy method is effective, and can be well applied in passenger flow routing design problem. Systematic studying the passenger terminal passenger flow routing design optimization techniques and methods and developing rational and efficient passenger flow routing program will help improving the organization of passenger flow. According to the description of the problem and the characteristics of itself, the paper transforms the problem into a combinatorial optimization problem, so that it is convenient to explore the best solution. The paper also employs the cross entropy method to solve the problems. Numerical example declares that the method given above can obtain the optimal solution under the condition of fixed demand. Results show that the cross entropy method is effective, and this method can be well applied in passenger flow routing design problem.

The problem consists in selection of multicommodity flow routes and channel capacities and the paper presents the linear capacity and heuristic algorithms for multicommodity flow in computer networks engineering to minimize shipping cost subject to the budget constraint

In this paper, we consider an energy harvesting sensor network where sensors are powered by reusable energy such as solar energy, wind energy, and so on, from their surroundings. We first formulate a novel monitoring quality maximization problem that aims to maximize the quality, rather than the quantity, of collected data, by incorporating spatial data correlation among sensors. An optimization framework consisting of dynamic rate weight assignment, fair data rate allocation, and flow routing for the problem is proposed. To fairly allocate sensors with optimal data rates and efficiently route sensing data to the sink, we then introduce a weighted, fair data rate allocation and flow routing problem, subject to energy budgets of sensors. Unlike the most existing work that formulated the similar problem as a linear programming (LP) and solved the LP, we develop fast approximation algorithms with provable approximation ratios through exploiting the combinatorial property of the problem. A distributed implementation of the proposed algorithm is also developed. The key ingredients in the design of algorithms include a dynamic rate weight assignment and a reduction technique to reduce the problem to a special maximum weighted concurrent flow problem, where all source nodes share the common destination. We finally conduct extensive experiments by simulation to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm is very promising, and the solution to the weighted, fair data rate allocation and flow routing problem is fractional of the optimum.

In this paper, we consider the problem of sending a set of multiple commodities from their origin to destination nodes via intermediate hubs. Each hub node is associated with a reliability function, which depends on the total flow that crosses that hub. The probability that each commodity is successfully relayed from its origin to its destination is given by the product of hub reliabilities on the commodity's path. The problem we consider seeks to find minimum-cost commodity paths such that each commodity reaches its destination with a sufficiently large probability. We first formulate the problem as a nonlinear multicommodity network-flow problem and prove that it is strongly NP-hard. We then present two linearization techniques for this formulation, and propose a pair of lower- and upper-bounding formulations, which can then be used within an exact cutting-plane algorithm to solve the problem. Finally, we analyze the computational effectiveness of our proposed strategies on a set of randomly generated instances.

This paper describes an exact algorithm to solve a nonlinear mixed-integer programming model due to capacity expansion and flow assignment in multicommodity networks. The model combines continuous multicommodity flow variables associated with nonlinear congestion costs and discrete decision variables associated with the arc expansion costs. After establishing precise correspondences between a mixed-integer model and a continuous but nonconvex model, an implicit enumeration approach is derived based on the convexification of the continuous objective function. Numerical experiments on medium size instances considering one level of expansion are presented. The results reported on the performance of the proposed algorithm show that the approach is efficient, as commercial solvers were not able to tackle the instances considered.

We consider the dynamic version of the maximum flow network interdiction problem; that is, we assume a positive number is assigned to each arc which indicates the traversal time of the flow through that arc. We also assume that an intruder uses a single resource with limited budget to interrupt the flow of a single commodity through the network within a given time limit of T. A new formulation based on the concept of Temporally Repeated Flow (TRF) is presented. The problem is then solved using Benders' decomposition. Another solution method, based on the most vital arcs in a network is also discussed. Finally, some computational results are reported.

The time limited vehicle routing problem (TLVRP) stems from the vehicle routing problem. The main difference is that the routes are paths (not cycles), i.e. vehicles do not return to the central city (or at least we do not observe their way back). Costs are given for the straight routes between each pair of the cities and represent the time necessary for going through. Each path must not exceed a given time limit. The sum of times for all routes is to be minimized.This problem is NP-hard. There are many various possibilities how to design the heuristics (approximation methods) to solve it. One of the ways of how to obtain an approximation method for the TLVRP is to modify the famous savings method by Clark and Wright (1964) for this purpose. In this paper we suggest several different versions of this method, test them in some instances, and evaluate and mutually compare the results of individual versions.

Where to locate one or several facilities on a network so as to minimize the expected users-closest facility transportation cost is a problem well studied in the OR literature under the name of median problem. In the median problem users are usually identified with nodes of the network. In many situations, however, such assumption is unrealistic, since users should be better considered to be distributed also along the edges of the transportation network. In this paper we address the median problem with demand distributed along edges and nodes. This leads to a global-optimization problem, which can be solved to optimality by means of a branch-and-bound with DC bounds. Our computational experience shows that the problem is solved in short time even for large instances.

We design a network that supports a feasible multicommodity flow even after the failures of any k edges. We present a mixed-integer linear program (MILP), a cutting plane algorithm, and a column-and-cut algorithm. The algorithms add constraints to repair vulnerabilities in partial network designs. Empirical studies on previously unsolved instances of SNDlib demonstrate their effectiveness.

International audience; In this paper, a new decomposition approach is proposed to solve large size instances of Multicommodity Flow problems. Instead of generating paths, we generate trees in a convenient way. Numerical results show that the new approach is much more efficient than the classical paths generation approach. Moreover, we propose a combinatorial polynomial-time algorithm to solve the maximum concurrent flow problem (MCF) in the single-source case.

An integer fixed-charge multicommodity flow (FCMF) model is used as the first part of a two-phase approach for train unit scheduling, and solved by an exact branch- and-price method. To strengthen knapsack constraints and deal with complicated scenarios arisen in the integer linear program (ILP) from the integer FCMF model, preprocessing is used by computing convex hulls of sets of points representing all possible train formations utilizing multiple unit types.

linear programming; equivalence of separation and optimization; multicommodity flow networks; path generation; survivable network design; NP-hardness; International audience; In this article, we revisit a classical optimization problem occurring in designing survivable multicommodity flow networks. The problem, referred to as FR, assumes flow restoration that takes advantage of the so-called stub release. As no compact linear programming (LP) formulation of FR is known and at the same time all known noncompact LP formulations of FR exhibit eNP-hard dual separation, the problem itself is believed to be NP-hard, although without a proof. In this article, we study a restriction of FR (RFR) that assumes only elementary (cycle-free) admissible paths--an important case virtually not considered in the literature. The two problems have the same noncompact LP formulations as they differ only in the definition of admissible paths: all paths (also those including cycles) are allowed in FR, while only elementary paths are allowed in RFR. Because of that, RFR is in general computationally more complex than FR. The purpose of this article, is three-fold. First, the article reveals an interesting special case of RFR--the case with only one failing link--for which a natural noncompact LP formulation obtained by reducing the general RFR formulation still exhibits NP-hard dual separation, but nevertheless this special case of RFR is polynomial. The constructed example of a polynomial multicommodity flow problem with difficult dual separation is of interest since, to our knowledge, no example of this kind has been known. In this article, we also examine a second special case of RFR, this time assuming two failing links instead of one, which turns out to be NP-hard. This implies that problem RFR is NP-hard in general (more precisely, for two or more failure states). This new result is the second contribution of the article. Finally, we discuss the complexity of FR in the light of our new findings, emphasizing the differences between RFR and FR.