Search

Cognitive radio (CR) allows unlicensed users to access the licensed spectrum opportunistically (i.e., when the spectrum is left unused by the licensed users) to enhance the spectrum utilization efficiency. In this paper, the problem of allocating resources (channels and transmission power) in multihop CR networks is modeled as a multicommodity flow problem with the dynamic link capacity resulting from dynamic resource allocation, which is in sharp contrast with existing flow-control approaches that assume fixed link capacity. Based on queue-balancing network flow control that is ideally suited for handling dynamically changing spectrum availability in CR networks, we propose a distributed scheme (installed and operational in each node) for optimal resource allocation without exchanging spectrum dynamics information between remote nodes. Considering the power masks, each node makes resource-allocation decisions based on current or past local information from neighboring nodes to satisfy the throughput requirement of each flow. Parameters of these proposed schemes are configured to maintain the network stability. The performance of the proposed scheme for both asynchronous and synchronous scenarios is analyzed comparatively. Both cases of sufficient and insufficient network capacity are considered.

This paper describes the way a multi-item, multi-plant Lot-Sizing problem with transfer costs/capacities may be expressed according to the multi-commodity flow formalism, and decomposed into a master Facility Location problem, and a slave minimal cost flow problem. It describes the way this decomposition framework gives rise in a natural way to the design of a heuristic relax/project algorithm, and it ends with numerical experiments.

Minimum Cost Maximum Flow Problem (MCMFP) is to find the maximum flow with minimal total cost, i.e., the minimum cost maximum flow, in transportation network. In this paper, MCMFP is formulated using a bi-level programming model. As a solution method of the model, an algorithm named MCMF-A is proposed. The basic idea of the MCMF-A algorithm can be described as follows: first find a maximum flow without opposite flow in transportation network, next construct its residual network with regard to the maximum flow, then find a negative-cost cycle in the residual network by calling well-known Floyd Algorithm; if Floyd Algorithm finds that there is no negative-cost cycle in the residual network, then the maximum flow is minimum cost maximum flow, else adjust the maximum flow via the negative-cost cycle to get a new maximum flow with no opposite flow and less total transportation cost. The theory, on which the MCMF-A algorithm is based, is presented. The MCMF-A algorithm can find the optimal solution to MCMFP, and has good performance in the sense of being implemented on computer, computational time and required memory for computation. Numerical experiments demonstrate that the MCMF-A algorithm is an efficient and robust method to solve MCMFP, which can serve as an effective tool to solve other related optimization problems.

The pooling problem is an extension of the minimum cost network flow problem where the composition of the flow depends on the sources from which it originates. At each source, the composition is known. In all other nodes, the proportion of any component is given as a weighted average of its proportions in entering flow streams. The weights in this average are simply the arc flow. At the terminals of the network, there are bounds on the relative content of the various components. Such problems have strong relevance in e.g. planning models for oil refining, and in gas transportation models with quality constraints at the reception side. Although the pooling problem has bilinear constraints, much progress in solving a class of instances to global optimality has recently been made. Most of the approaches are however restricted to networks where all directed paths have length at most three, which means that there is no connection between pools. In this work, we generalize one of the most successful formulations of the pooling problem, and propose a multi-commodity flow formulation that makes no assumptions on the network topology. We prove that our formulation has stronger linear relaxation than previously suggested formulations, and demonstrate experimentally that it enables faster computation of the global optimum.

an algorithm which reduces the arbitrary instance of the network flow problem to a simple path disjoint network in polynomial time. Then the flow in each path is taken as the minimum of the arc capacities of that path from where the flow in each arc can be easily determined. The polynomial time algorithm can determine any instance of the network flow problem faster than the previously existing algorithms . An example has been given to elucidate the process. At the end a MATLAB program based on this algorithm has been given.

The paper deals with the uncapacitated minimum cost flow problems subject to additional flow constraints whether or not the sum of node capacities is zero. This is a generalization and extension of transportation problems with restrictions on total flow value. The relationship between the desired flow value and the sum of node capacities of source(s) and sink(s) gives rise to the different set of problems. Mathematical models for the various cases are formulated. For each case an equivalent standard minimum cost flow problem (MCFP) is formulated whose optimal solution provides the optimal solution to the original flow constrained problem. The paper not only extends the similar concept of transportation problem to the case of MCFP but also suggests an alternative equivalent formulation. Solving the alternative problem is computationally better in comparison to the formulation analogous to the transportation case. A broad computational comparison is carried out at the end.

We consider the NP -hard problem of scheduling n jobs in m two-stage parallel flow shops so as to minimize the makespan. This problem decomposes into two subproblems: assigning the jobs to parallel flow shops; and scheduling the jobs assigned to the same flow shop by use of Johnson’s rule. For m = 2, we present a 3 2 -approximation algorithm, and for m = 3, we present a 12 7 -approximation algorithm. Both these algorithms run in O ( n log n ) time. These are the first approximation algorithms with fixed worst-case performance guarantees for the parallel flow shop problem.

Consideration was given to the multi-index problems of linear and integer linear programming of the transport type. An approach based on the study of reducibility of the multi-index transport problems to that of seeking a flow on the network was proposed. For the multi-index problems with decomposition structure, a reduction scheme enabling one to solve the original multi-index problem using the cyclic decomposition of the minimum-cost flow of the auxiliary flow problem was constructed. The developed method underlies the heuristic algorithm to solve the NP-hard integer multi-index problem with a system of constraints featuring decompositional properties and general cost matrix.

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman's tour is the determinant of their `load'. The new models are novel multicommodity flow formulations with O(n^2) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n^3) binary variables. The paper also describes Benders Decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.

in Undetermined his survey deals with computational complexity of column generation problems arising in the design of survivable communication networks. Such problems are often modeled as linear programs based on noncompact multicommodity flow network formulations. These formulations involve an exponential number of path-flow variables, and therefore require column generation to be solved to optimality. We consider several path-based protection and restoration mechanisms and present results, both known and new, on the complexity of the corresponding column generation (also called pricing) problems. We discuss results for the case of single link or single node failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Eventually, we show that almost all the encountered pricing problems are hard to solve for scenarios admitting multiple failures, while a great deal of them are NP-hard already for single failure scenarios. (Less)

One of the best approaches for some classes of multicommodity flow problems is a specialized interior-point method that solves the normal equations by a combination of Cholesky factorizations and preconditioned conjugate gradient. Its efficiency depends on the spectral radius—in [0,1)—of a certain matrix in the definition of the preconditioner. In a recent work the authors improved this algorithm (i.e., reduced the spectral radius) for general block-angular problems by adding a quadratic regularization to the logarithmic barrier. This barrier was shown to be self-concordant, which guarantees the convergence and polynomial complexity of the algorithm. In this work we focus on linear multicommodity problems, a particular case of primal block-angular ones. General results are tailored for multicommodity flows, allowing a local sensitivity analysis on the effect of the regularization. Extensive computational results on some standard and some difficult instances, testing several regularization strategies, are also provided. These results show that the regularized interior-point algorithm is more efficient than the nonregularized on e. From this work it can be concluded that, if interior-point methods based on conjugate gradients are used, linear multicommodity flow problems are most efficiently solved as a sequence of quadratic ones.

We consider a formulation for the fixed charge network flow (FCNF) problem subject to multiple uncertain arc failures, which aims to provide a robust optimal flow assignment in the sense of restricting potential losses using Conditional Value-at-Risk (CVaR). We show that a heuristic algorithm referred to as Adaptive Dynamic Cost Updating Procedure (ADCUP) previously developed for the deterministic FCNF problem can be extended to the considered problem under uncertainty and produce high-quality heuristic solutions for large problem instances. The reported computational experiments demonstrate that the described procedure can successfully tackle both the uncertainty considerations and the large size of the networks. High-quality heuristic solutions for problem instances with up to approximately 200,000 arcs have been identified in a reasonable time.

What we are dealing with is a class of networks called dynamic generative network flows in which the flow commodity is dynamically generated at source nodes and dynamically consumed at sink nodes. As a basic assumption, the source nodes produce the flow according to time generative functions and the sink nodes absorb the flow according to time consumption functions. This paper tries to introduce these networks and formulate minimum cost dynamic flow problem for a pre-specified time horizon T. Finally, some simple, efficient approaches are developed to solve the dynamic problem, in the general form when the capacities and costs are time varying and some other special cases, as a minimum cost static flow problem.

Most past car pooling studies have focused on the to-work problem (from different origins to a common destination) or the return-from-work problem (from the same origin to different destinations). Pre-matching information, including the carpool partners and the route/schedule for each previously participating vehicle, have rarely been considered. As a result, there has not yet been a suitable method/model developed for solving practical many-to-many car pooling problem with multiple vehicle and person types, as well as pre-matching information, that occur in real-world. In this study we strive to make up this lack by employing a time-space network flow technique to develop a model for this type of car pooling problem with pre-matching information (CPPPMI). The model is formulated as an integer multiple commodity network flow problem. A solution algorithm, based on Lagrangian relaxation and a heuristic for the upper bound solution, is developed to solve the model. To test how well the model and the solution algorithm may be applied to real-world, numerical tests are performed with several problem instances randomly generated based upon data reported from a past study carried out in northern Taiwan. The test results show the effectiveness of the proposed model and solution algorithm.

In layered networks, a single failure at a lower layer may cause multiple failures in the upper layers. As a result, traditional schemes that protect against single failures may not be effective in multilayer networks. In this paper, we introduce the problem of maximizing the connectivity of layered networks. We show that connectivity metrics in layered networks have significantly different meaning than their single-layer counterparts. Results that are fundamental to survivable single-layer network design, such as the Max-Flow Min-Cut Theorem, are no longer applicable to the layered setting. We propose new metrics to measure connectivity in layered networks and analyze their properties. We use one of the metrics, Min Cross Layer Cut, as the objective for the survivable lightpath routing problem and develop several algorithms to produce lightpath routings with high survivability. This allows the resulting cross-layer architecture to be resilient to failures between layers.

In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight $\mu$, we define a metrized polyhedral complex, called the directed tight span $T_{\mu}$, and prove that the dual of $\mu$-weighted maximum multiflow problem reduces to a facility location problem on $T_{\mu}$. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by $\mu$. By utilizing this duality, we establish the classifications of terminal weights admitting combinatorial min-max relation (i) for every network and (ii) for every Eulerian network. Our result includes Lomonosov-Frank theorem for directed free multiflows and Ibaraki-Karzanov-Nagamochi's directed multiflow locking theorem as special cases., Comment: 27 pages. Fixed minor mistakes and typos. To appear in Discrete Optimization

The minimal-cost network flow problem with fixed lower and upper bounds on arc flows has been well studied. This paper investigates an important extension, in which some or all arcs have variable lower bounds. In particular, an arc with a variable lower bound is allowed to be either closed (i.e., then having zero flow) or open (i.e., then having flow between the given positive lower bound and an upper bound). This distinctive feature makes the new problem NP-hard, although its formulation becomes more broadly applicable, since there are many cases where a flow distribution channel may be closed if the flow on the arc is not enough to justify its operation. This paper formulates the new model, referred to as MCNF-VLB, as a mixed integer linear programming, and shows its NP-hard complexity. Furthermore, a numerical example is used to illustrate the formulation and its applicability. This paper also shows a comprehensive computational testing on using CPLEX to solve the MCNF-VLB instances of up to medium-to-large size.

This paper introduces a novel optimal flow control problem that seeks to convey a specified amount of fluid to each of the nodes of an acyclic digraph with a single source node, while minimizing the total amount of fluid inducted into the network. Two factors complicating the aforementioned task are (i) the presence of nodes with uncontrollable routing of the traversing flow and (ii) a set of precedence constraints regarding the satisfaction of the nodal fluid requirements. It is shown that the considered problem can be naturally formulated as a continuous-time optimal control problem that can be reduced to a hybrid optimal control problem with controlled switching. This property subsequently enables the solution of the considered problem through a Mixed Integer Programming formulation. Additional results in the paper establish the NP-hardness of the considered problem, highlight its affinity to some well known scheduling problems, and offer guidelines that can alleviate the increased problem complexity.

Conventional optical burst switching (OBS) is incapable of providing connection-oriented service, and burst loss is more likely to occur with increasing of traffic load due to its inherent architecture where the burst size is variable. In this paper, we propose and evaluate the optical time-slot switching technology, in which the fixed-size time-slot is adopted as the basic switching granularity, and switching is done in the time domain, rather than the wavelength domain. Also, we prove that time-slot switching has an equivalent function to eliminate data conflict relative to wavelength converter. Subsequently, the routing, wavelength, and time-slot assignment problem is studied in this paper. An adaptive weight function is introduced to the routing and wavelength selection algorithm, then several useful approaches, such as the train approach, wagon approach and p-distribution approach, are presented for time-slot assignment and scheduling. The results show that our scheme can perform better than conventional OBS in the aspect of blocking performance, quality of service, and class of service.

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.

In this paper, we investigate the problem of flow routing and fair bandwidth allocation under interference constraints for multihop wireless networks. We first develop a novel isotonic routing metric, RI3M, considering the influence of interflow and intraflow interference. The isotonicity of the routing metric is proved using virtual network decomposition. Second, in order to ensure QoS, an interference-aware max-min fair bandwidth allocation algorithm, LMX:M3F, is proposed where multiple paths (determined by using the routing metric) coexist for each user to the base station. In order to solve the algorithm, we develop an optimization formulation that is modeled as a multicommodity flow problem where the lexicographically largest bandwidth allocation vector is found among all optimal allocation vectors while considering constraints of interference on the flows. We compare our RI3M routing metric and LMX:M3F bandwidth allocation algorithm with various interference-based routing metrics and interference-aware bandwidth allocation algorithms established in the literature. We show that RI3M and LMX:M3F succeed in improving network performance in terms of delay, packet loss ratio, and bandwidth usage.

This paper treats with integral multi-commodity flow through a network. To enhance the Quality of Service (QoS) for channels, it is necessary to minimize delay and congestion. Decreasing the end-to-end delay and consumption of bandwidth across channels are dependent and may be considered in very complex mathematical equations. To capture with this problem, a multi-commodity flow model is introduced whose targets are minimizing delay and congestion in one model. The flow through the network such as packets, also needs to get integral values. A model covering these concepts, is NP-hard while it is very important to find transmission strategies in real-time. For this aim, we extend a cooperative algorithm including traditional mathematical programming such as path enumeration and a meta-heuristic algorithm such as genetic algorithm. To find integral solution satisfying demands of nodes, we generalize a hybrid genetic algorithm to assign the integral commodities where they are needed. In this hybrid algorithm, we use feasible encoding and try to keep feasibility of chromosomes over iterations. By considering some random networks, we show that the proposed algorithm yields reasonable results in a few number of iterations. Also, because this algorithm can be applied in a wide range of objective functions in terms of delay and congestion, it is possible to find some routs for each commodity with high QoS. Due to these outcomes, the presented model and algorithm can be utilized in a variety of application in computer networks and transportation systems to decrease the congestion and increase the usage of channels.

Distributed network utility maximization (NUM) has received an increasing intensity of interest over the past few years. Distributed solutions (e.g., the primal-dual gradient method) have been intensively investigated under fading channels. As such distributed solutions involve iterative updating and explicit message passing, it is unrealistic to assume that the wireless channel remains unchanged during the iterations. Unfortunately, the behavior of those distributed solutions under time-varying channels is in general unknown. In this paper, we shall investigate the convergence behavior and tracking errors of the iterative primal-dual scaled gradient algorithm (PDSGA) with dynamic scaling matrices (DSC) for solving distributive NUM problems under time-varying fading channels. We shall also study a specific application example, namely the multi-commodity flow control and multi-carrier power allocation problem in multi-hop ad hoc networks. Our analysis shows that the PDSGA converges to a limit region rather than a single point under the finite state Markov chain (FSMC) fading channels. We also show that the order of growth of the tracking errors is given by O(T/N), where T and N are the update interval and the average sojourn time of the FSMC, respectively. Based on this analysis, we derive a low complexity distributive adaptation algorithm for determining the adaptive scaling matrices, which can be implemented distributively at each transmitter. The numerical results show the superior performance of the proposed dynamic scaling matrix algorithm over several baseline schemes, such as the regular primal-dual gradient algorithm.

This paper is concerned with the cargo allocation problem considering empty repositioning of containers for a liner shipping company. The aim is to maximize the profit of transported cargo in a network, subject to the cost and availability of empty containers. The formulation is a multi-commodity flow problem with additional inter-balancing constraints to control repositioning of empty containers. In a study of the cost efficiency of the global container-shipping network, Song et al. (2005) estimate that empty repositioning cost constitutes 27% of the total world fleet running cost. An arc-flow formulation is decomposed using the Dantzig–Wolfe principle to a path-flow formulation. A linear relaxation is solved with a delayed column generation algorithm. A feasible integer solution is found by rounding the fractional solution and adjusting flow balance constraints with leased containers. Computational results are reported for seven instances based on real-life shipping networks. Solving the relaxe...

This paper addresses the problem of generating conflict-free train schedules on a microscopic model of the railway infrastructure. Conflicts arise if two or more trains are scheduled to block the same track section at the same time. A standard model for this problem is the so-called conflict graph, where each considered train path corresponds to a vertex, and edges represent pairwise conflicts so that a conflict-free schedule corresponds to a maximum independent set. Because the linear programming relaxation of the conflict graph formulation is typically very weak, we develop an alternative model using the sequence of resources that each train path passes, encoded in a resource tree. For each resource, we can efficiently determine the maximal conflict cliques by scanning through the blocking times of all train paths and use these cliques as strong cutting planes in an integer linear programming formulation. We show that the number of maximal conflict cliques is linear in the number of train paths, so the ILP formulation uses much fewer but stronger constraints compared to the conflict graph model. In tests with real-world data from the Swiss Federal Railways, the new Resource Tree Conflict Graph model generates for major stations within seconds, even though the underlying model contains about half a million binary variables. This corresponds to a reduction of the computation time of roughly two orders of magnitude when compared to previous approaches and thus allows us to tackle considerable larger problem instances.

We consider a variant of the well-known minimum cost flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound. The problem was recently shown to be weakly NP-complete even on series-parallel graphs. We start by showing that the problem is strongly NP-complete and cannot be approximated in polynomial time (unless P=NP) up to any polynomially computable function even when the graph is bipartite and the given instance is guaranteed to admit a feasible solution. Moreover, we present a pseudo-polynomial-time exact algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem on series-parallel graphs.

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.

Node-arc incidence matrices in network flow problems exhibit several special least-squares properties. We show how these properties can be leveraged in a least-squares primal-dual algorithm for solving minimum-cost network flow problems quickly. Computational results show that the performance of an upper-bounded version of the least-squares minimum-cost network flow algorithm with a special dual update operation is comparable to CPLEX Network and Dual Optimizers for solving a wide range of minimum-cost network flow problems.

We propose a framework for analysis and optimization of repairable flow networks by (i) stating and proving the maximum flow minimum flow path resistance theorem for networks with merging flows (ii) a discrete-event solver for determining the variation of the output flow from repairable flow networks with complex topology (iii) a procedure for determining the threshold flow rate reliability for repairable networks with complex topology (iv) a method for topology optimization of repairable flow networks and (v) an efficient algorithm for maximizing the flow in non-reconfigurable flow networks with merging flows. Maximizing the flow in a static flow network does not necessarily guarantee that the flow in the corresponding non-reconfigurable repairable network will be maximized. In this respect, we introduce a new concept related to repairable flow networks: `a specific resistance of a flow path' which is essentially the average percentage of losses from component failures for a flow path from the source to the sink. A very efficient algorithm based on adjacency arrays has also been proposed for determining all minimal flow paths in a network with complex topology and cycles. We formulate and prove a fundamental theorem about non-reconfigurable repairable flow networks with merging flows. The flow in a repairable flow network with merging flows can be maximized by preferentially saturating directed flow paths from the sources to the sink, characterized by the largest average availability. The procedure starts with the flow path with the largest average availability (the smallest specific resistance), and continues by saturating the unsaturated directed flow path with the largest average availability until no more flow paths can be saturated. A discrete-event solver for reconfigurable repairable flow networks with complex topology has also been constructed. The proposed discrete-event solver maximizes the flow rate in the network upon each component failure and return from repair. By maximizing the flow rate upon each component failure and return from repair, the discrete-event solver ensures a larger total output flow during a specified time interval. The designed simulation procedure for determining the threshold flow rate reliability is particularly useful for comparing flow network topologies, and selecting the topology characterized by the largest threshold flow rate reliability. It is also very useful in deciding whether the resources allocated for purchasing extra redundancy are justified. Finally, we propose a new optimization method for determining the network topology combining a maximum output flow rate attained within a specified budget for building the network. The optimization method is based on a branch and bound algorithm combined with pruning the full-complexity network as a way of exploring the possible repairable networks embedded in the full-complexity network.

In this paper, we study a minimum cost multicast problem on a network with shared risk link groups (SRLGs). Each SRLG contains a set of arcs with a common risk, and there is a cost associated with it. The objective of the problem is to find a multicast tree from the source to a set of destinations with minimum transmission cost and risk cost. We present a basic model for the multicast problem with shared risk cost (MCSR) based on the well-known multicommodity flow formulation for the Steiner tree problem (Goemans and Myung in Networks 1:19–28, 1993; Polzin and Daneshmand in Discrete Applied Mathematics 112(1–3): 241–261, 2001). We propose a set of strong valid inequalities to tighten the linear relaxation of the basic model. We also present a mathematical model for undirected MCSR. The computational results of real life test instances demonstrate that the new valid inequalities significantly improve the linear relaxation bounds of the basic model, and reduce the total computation time by half in average.

In particular, imprecise observations or possible perturbations mean that data in a network flows may well be better represented by intervals or fuzzy numbers than crisp quantities. In this paper we first consider the minimum cost flow problem with compact interval-valued lower and upper bounds, flows, and costs. We present a new method that shows this problem is solved using two minimum cost flow problems with crisp data. Then this result is extended to networks with fuzzy lower and upper bounds, flows, and costs. One of the best algorithms to solve the minimum cost flow problem with crisp data is the cost scaling algorithm of Goldberg and Tarjan.17 In this paper, the cost scaling algorithm is modified for fuzzy lower and upper bounds, flows and costs. The running time of the modified algorithm is equal to the running time of the cost scaling algorithm with crisp data.

The cell-transmission model-based single-destination system optimal dynamic traffic assignment problem proposed by Ziliaskopoulos was mostly solved by standard linear programming (LP) methods, e.g., simplex and interior point methods, which produce link-based flows involving vehicle-holding phenomenon. In this paper we present a network flow algorithm for this problem. We show that the problem is equivalent to the earliest arrival flow and then solve the earliest arrival flow on a time-expanded network. In particular, a scaled flow scheme is proposed to deal with the situation in which the ratio of backward wave speed to forward wave speed is less than one. The proposed algorithm produces path-based flows exhibiting realistic nonvehicle-holding properties. Complexity and numerical analyses show that the algorithm runs more efficiently than LP.

This paper considers an optimal base station clustering problem for designing a mobile (wireless) communication network. For a given network with a set of nodes (base stations), the problem is to optimally partition the set of nodes into subsets (each called a cluster) such that the associated inter-cluster traffic is minimized under certain topological constraints and cluster capacity constraints. In the problem analysis, the problem is formulated as an integer programming problem. The integer programming problem is then transformed into a binary integer programming problem, for which the associated linear programming relaxation is solved in a column generation approach assisted by a branch-and-bound procedure. For the column generation, both a heuristic algorithm and a valid inequality approach are exploited. Various numerical examples are solved to evaluate the effectiveness of the LP (Linear Programming) based branch-and-bound algorithm.

The hydraulic circuit theory created to model hydraulic systems such as pipeline transportation systems usually considers the flow distribution problem with specified flow rates of the medium to be transported to and from the transportation system at individual nodes. This paper investigates the case of practical interest where the medium flow rates at individual nodes are not fixed but depend on the pressure at these nodes.

This paper presents an algorithm for solving Bi-criteria Minimum Cost Dynamic Flow (BiCMCDF) problem with continuous flow variables. The approach is to transform a bi-criteria problem into a parametric one by building a single parametric linear cost out of the two initial cost functions. The algorithm consecutively finds efficient extreme points in the decision space by solving a series of minimum parametric cost flow problems with different objective functions. On each of the iterations, the flow is augmented along a cheapest path from the source node to the sink node in the time-space network avoiding the explicit time expansion of the network.

We provide a complexity classification of four variants of robust integer programming when the underlying Graver basis is given. We discuss applications to robust multicommodity flows and multiway statistical table problems, and describe an effective parametrization of robust integer programming.

Scheduling is generally believed to be a hard computational problem. People propose a lot of algorithms for solving this problem, most of which require exponential time. In this paper, we study a restricted form of scheduling problem, called the course scheduling problem. We show that this problem can be solved by reducing it to the network flow problem, which requires polynomial time to solve. Our proposed method is simple and efficient. It can scale up to real-world scheduling problems.

The objective of the classical minimum cost flow problem is to send units of a good that reside at one or more points in a network (sources or supply nodes) with arc capacities to one or more other points in the network (sinks or demand nodes), incurring minimum cost. We develop fast algorithms for previously unstudied specially structured minimum cost flow problems that have applications in many areas, such as locomotive and airline scheduling, repositioning of empty rail freight cars, highway and river transportation, congestion pricing, shop loading, and production planning. First, we consider the case where the n1 supply and n2 demand nodes lie on a circle (or line) (n = n1 + n2) and flow is allowed only in one direction; our algorithm solves this problem in O(n) time. Next, we consider a constrained version of this problem and show that it can be solved in O(n log n2) time. Finally, we consider the version where the nodes lie on a circle (or line), flow is allowed in both directions, and the costs of flow between two nodes in the clockwise and the counterclockwise direction are different; our algorithm solves this problem in O(n log n) time. Our algorithms are based on the successive shortest-path algorithm for the minimum cost flow problem. We exploit the special structure of the problem and use advanced data structures, when required, to achieve short run times.

The multi-transshipment problem is NP-hard already for two commodities over bipartite networks. Nonetheless, using our recent theory of n-fold integer programming and extensions developed herein, we are able to establish the polynomial time solvability of the problem in two broad situations. First, for any fixed number of commodities and number of suppliers, we solve the problem over bipartite networks with variable number of consumers in polynomial time. This is very natural in operations research applications where few facilities serve many customers. Second, for every fixed network, we solve the problem with variable number of commodities in polynomial time.

This paper studies the single-path multicommodity network flow problem (SMNF), in which the flow of each commodity can only use one path linking its origin and destination in the network. We study two versions of this problem based on two different objectives. The first version is to minimize network congestion, an issue of concern in traffic grooming over wavelength division multiplexing (WDM), and in which there generally exists a commodity flow between every pair of nodes. The second problem is a constrained version of the general linear multicommodity flow problem, in which, for each commodity, a single path is allowed to send the required flow, and the objective is to determine a flow pattern that obeys the arc capacities and minimizes the total shipping cost. Based on the node-arc and the arc-chain representations, we first present two formulations. Owing to computational impracticality of exact algorithms for practical networks, we propose an ant colony optimization-(ACO) based metaheuristic to deal with SMNF. Considering different problem properties, we devise two versions of ACO metaheuristics to solve these two problems, respectively. The proposed algorithms’ efficiencies are experimentally investigated on some generated instances of SMNF. The test results demonstrate that the proposed ACO metaheuristics are computationally efficient and robust approaches for solving SMNF.

Network flows are of growing interest in both applications and theory. Given a network flow with costs and arc capacities, the classical max flow-min cost problem is to send a given amount of flow from the source vertex to the sink vertex at least cost. Among the predominant issues in this field are problems that result when the flow is going through one arc to another arc in the same direction, such as the role of compressors in gas pipeline networks or the role of transformers in electricity wide networks. Hence, in order to minimize the cost of these elements in the network, we perform applications of line-digraphs in the form of an optimization algorithm. This paper proposes a new variant of the max flow-min cost problem. Our objective is to find the smoothest max flow over a given network.

In this study, we consider the routing and wavelength assignment problem on SONET over WDM ring networks. Our problem is the minimum ADM (add-drop multiplexer) cost problem of minimizing the number of ADM equipment instead of the minimum wavelength problem. To deal with the complexity of the problem, we create a new mathematical formulation and suggest an efficient solution method based on the branch-and-price method. We exploit the structure of the ring network to develop an efficient algorithm and show the efficiency using computer simulations.

This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem.

In this paper, we consider the 1-median problem in R d with the Chebyshev-norm. We give an optimality criterion for this problem which enables us to solve the following inverse location problem in polynomial time: Given n points P 1 , … , P n with non-negative weights w i and a point P 0 the task is to find new non-negative weights w ˜ i such that P 0 is a 1-median with respect to the new weights and ‖ w − w ˜ ‖ 1 is minimized. In fact, this problem reduces to a balancing flow problem for which an optimal solution can be obtained in polynomial time.

This study is part of a series of research projects on a distribution system we developed to deal with cases in a state-owned company. It concerns the design of the Public Service Obligation State-owned Company (PSO-SOC) distribution system. The intrinsic features of PSO-SOC are distributing strategic commodities and having subsidies within the cost function. Hence their distribution flow has to be secured under consideration of moving the commodities within road networks that have traffic flow dependency. This paper focuses on the solution of the proposed model which represents traffic flow dependency within a freight distribution network. The mathematical formulation takes the form of a Minimum Cost Multicommodity Flow (MCMF) problem. Traffic flow dependency is incorporated into the model by introducing a coefficient of speed, which is derived from the traffic assignment of ordinary traffic associated with the transportation of the type of freight under consideration The solution of the proposed model is formulated by Network Representation (NR), in which all of the components of the mathematical model are represented in the form of dummy links and nodes added to the original (physical) network. It is to be noted then, that the traffic flow on each road or link is represented by a link performance function (LPF), depicting traffic flow dependent travel time and consequent cost. The MCMF problem of NR is further solved by a Primal–Dual Algorithm. Finally, an illustrative example is exercised to show how the proposed step-wise solution works.

An extension of the capacitated, fixed charge, multicommodity network flow problem with an uncertain demand of services and survivability constraints was designed and modeled as a stochastic programming problem. A polynomial algorithm based on the GRASP metaheuristic with a construction phase of a survivable topology and a local search phase based on a key-path decomposition of the graph and a feasible key-path replacement was proposed to solve it. The heuristic algorithm was tested for several problem instances, and its solutions were compared with a branch-and-cut solver. The heuristic reached good quality solutions for the tested cases.

A problem and a new algorithm are given for the linear fractional minimal cost flow problem on network. Using a new check number and combining the characteristic of network to extend the traditional theories of minimum cost flow problem, discussed the relation between it and its dual problem. Optimality conditions are derived and a Network Simplex Algorithm is proposed that leads to optimal solution assuming certain properties. Finally, an numerical example test is also developed.

This paper deals with a general minimum cost dynamic flow problem in a discrete time model with time-varying transit times, transit costs, transit capacities, storage costs, and storage capacities. For this problem, an algorithm of time complexity O(V nT(n+T)) is presented, where V is an upper bound on the total supply, n is the number of nodes, and T denotes the given time horizon of the dynamic flow problem. The algorithm is a discrete-time version of the successive shortest path algorithm.

Recently, many works have employed deterministic strategies in dealt with flow scheduling problem in Air traffic flow management (ATFM). In practice, however, they are proved unreasonable for omitting airline’s preference in ATFM. In this paper, we develop a novel air traffic flow control model based on game theory to solve this problem in air traffic network. In the flow model, a resource (link/time pair in air traffic network) allocation strategy that uses sequential game method to predict traffic allocation is proposed in resource sharing environment. The problem of multiple airlines competes for an optimal route is formulated as a multi-player dynamic game. Through finding the Nash equilibrium solution of the multi-player dynamic game, the optimal flow scheduling is also formed at the same time. The flow model also incorporates many key characteristics of ATFM, such as competitive airlines, allowing multiply flow control strategies and so on. Numerical simulation results show the feasibility of solving the air traffic flow control problem using game theory on the air traffic network.

Optimal and reduced-complexity near-optimal algorithms are developed for the design of wireless networks in the presence of fading. The physical layer is interference-limited, whereby network terminals treat interference as noise. Optimal wireless network design amounts to joint optimization of application-level rates, routes, link capacities, power consumption, and power allocation across frequency tones, neighboring terminals, and fading states. The present contribution shows how recent results establishing the optimality of layered architectures can be realized in practice by developing physical layer resource allocation algorithms that are seamlessly integrated into layered architectures without loss of optimality. Specifically, the provably convergent algorithms yield (near-)optimal end-to-end rates, multicommodity flows, link capacities, and average powers. These design variables are obtained offline, and are subsequently used for control during network operation.