On the flow cost lowering problem

This paper presents the flow cost lowering problem (FCLP), which is an extension to the integral version of the well-known minimum cost flow problem (MCFP). While in the MCFP the flow costs are fixed, the FCLP admits lowering the flow cost on each arc by upgrading the arc. Given a flow value and a bound on the total budget which can be used for upgrading the arcs, the goal is to find an upgrade strategy and a flow of minimum cost. The FCLP is shown to be NP-hard even on series–parallel graphs. On the other hand the paper provides a polynomial time approximation algorithm on series–parallel graphs.     

A specialized network simplex algorithm for the constrained maximum flow problem

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.     

Budget constrained minimum cost connected medians

Several practical instances of network design and location theory problems require the network to satisfy multiple constraints. In this paper, we study a graph-theoretic problem that aims to simultaneously address a network design task and a location-theoretic constraint. The Budget Constrained Connected Median Problem is the following: We are given an undirected graph G=(V,E) with two different edge-weight functions c (modeling the construction or communication cost) and d (modeling the service distance), and a bound B on the total service distance. The goal is to find a subtree T of G with minimum c-cost c(T) subject to the constraint that the sum ∑_vVTdist_d(v,T) of the service distances of all the remaining nodes vVT does not exceed the specified budget B. Here, the service distance dist_d(v,T) denotes the shortest path distance of v to a vertex in T with respect to d. This problem has applications in optical network design and the efficient maintenance of distributed databases.

We formulate this problem as a bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem which demonstrate that our performance ratios are close to best possible.     

Maximum flow problem on dynamic generative network flows with time-varying bounds

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.     

A parametric algorithm for convex cost network flow and related problems

The convex cost network flow problem is to determine the minimum cost flow in a network when cost of flow over each arc is given by a piecewise linear convex function. In this paper, we develop a parametric algorithm for the convex cost network flow problem. We define the concept of optimum basis structure for the convex cost network flow problem. The optimum basis structure is then used to parametrize v, the flow to be transsshipped from source to sink. The resulting algorithm successively augments the flow on the shortest paths from source to sink which are implicitly enumerated by the algorithm. The algorithm is shown to be polynomially bounded. Computational results are presented to demonstrate the efficiency of the algorithm in solving large size problems. We also show how this algorithm can be used to (i) obtain the project cost curve of a CPM network with convex time-cost tradeoff functions; (ii) determine maximum flow in a network with concave gain functions; (iii) determine optimum capacity expansion of a network having convex arc capacity expansion costs.     

Network flow interdiction on planar graphs

The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.     

Minimum convex piecewise linear cost tension problem on quasi-<Emphasis Type="Italic">k</Emphasis> series-parallel graphs

Some hypermedia synchronization issues request the resolution of the minimum convex piecewise linear cost tension problem (CPLCT problem) on directed graphs that are close to two-terminal series-parallel graphs (TTSP-graphs), the so-called quasi-k series-parallel graphs (k-QSP graphs). An aggregation algorithm has already been introduced for the CPLCT problem on TTSP-graphs. We propose here a reconstruction method, based on the aggregation and the well-known out-of-kilter techniques, to solve the problem on k-QSP graphs. One of the main steps being to decompose a graph into TTSP-subgraphs, methods based on the recognition of TTSP-graphs are thoroughly discussed.Received: October 2003, Revised: July 2004, MSC classification: 90C35, 05C85     

A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems

Traditionally, minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Some advanced local search algorithms have been developed to solve concave cost bipartite network problems. These have been found to be more effective than the traditional linear approximation methods and local search methods. Recently, a genetic algorithm and an ant colony system algorithm were employed to develop two global search algorithms for solving concave cost transshipment problems. These two global search algorithms were found to be more effective than the advanced local search algorithms for solving concave cost transshipment problems. Although the particle swarm optimization algorithm has been used to obtain good results in many applications, to the best of our knowledge, it has not yet been applied in minimum concave cost network flow problems. Thus, in this study, we employ an arc-based particle swarm optimization algorithm, coupled with some genetic algorithm and threshold accepting method techniques, as well as concave cost network heuristics, to develop a hybrid global search algorithm for efficiently solving minimum cost network flow problems with concave arc costs. The proposed algorithm is evaluated by solving several randomly generated network flow problems. The results indicate that the proposed algorithm is more effective than several other recently designed methods, such as local search algorithms, genetic algorithms and ant colony system algorithms, for solving minimum cost network flow problems with concave arc costs.     

An algorithm for the min concave cost flow problem

A method is presented to solve that class of network flow problems, which may be formulated as one source - multiple destination minimum cost flow problems with concave costs. The global optimum is searched using a branch and bound procedure, in which the enumeration scheme is based on a characterization of the optimal solution set, while linear relaxations of the original problem provide lower bounds.     

A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

Optimal expansion of an existing network

Given an existing network, a list of arcs which could be added to the network, the arc costs and capacities, and an available budget, the problem considered in this paper is one of choosing which arcs to add to the network in order to maximize the maximum flow from a sources to a sinkt, subject to the budgetary constraint. This problem appears in a large number of practical situations which arise in connection with the expansion of electricity or gas supply, telephone, road or rail networks. The paper describes an efficient tree-search algorithm using bounds calculated by a dynamic programming procedure which are very effective in limiting the solution space explicitly searched. Computational results for a number of medium sized problems are described and computing times are seen to be very reasonable.     

Optimal expansion of capacitated transshipment networks

In this paper, we address the problem of allocating a given budget to increase the capacities of arcs in a transshipment network to minimize the cost of flow in the network. The capacity expansion costs of arcs are assumed to be piecewise linear convex functions. We use properties of the optimum solution to convert this problem into a parametric network flow problem. The concept of optimum basis structure is used which allows us to consider piecewise linear convex functions without introducing additional arcs. The resulting algorithm yields an optimum solution of the capacity expansion problem for all budget levels less than or equal to the given budget. For integer data, the algorithm performs almost all computations in integers. Detailed computational results are also presented.     

Inverse minimum cost flow problems under the weighted Hamming distance

Given a network N(V, A, u, c) and a feasible flow x⁰, an inverse minimum cost flow problem is to modify the cost vector as little as possible to make x⁰ form a minimum cost flow of the network. The modification can be measured by different norms. In this paper, we consider the inverse minimum cost flow problems, where the modification of the arcs is measured by the weighted Hamming distance. Both the sum-type and the bottleneck-type cases are considered. For the former, it is shown to be APX-hard due to the weighted feedback arc set problem. For the latter, we present a strongly polynomial algorithm which can be done in O(n · m²).     

The fractional minimal cost flow problem on network

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.     

A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Minimum cost multicommodity flows are a useful model for bandwidth allocation problems. These problems are arising more frequently as regional service providers wish to carry their traffic over some national core network. We describe a simple and practical combinatorial algorithm to find a minimum cost multicommodity flow in a ring network. Apart from 1 and 2-commodity flow problems, this seems to be the only such “combinatorial augmentation algorithm” for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each link by one, we may also find an integral routing of no greater cost. The “pivots” in the algorithm are determined by choosing an >0, increasing and decreasing sets of variables, and adjusting these variables up or down accordingly by . In this sense, it generalizes the cycle cancelling algorithms for (single source) mincost flow. Although the algorithm is easily stated, proof of its correctness and polynomially bounded running time are more complex.     

Inverse <Emphasis Type="Italic">p</Emphasis>-median problems with variable edge lengths

The inverse p-median problem with variable edge lengths on graphs is to modify the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified set of p vertices becomes a p-median with respect to the new edge lengths. The problem is shown to be strongly NP{\mathcal{NP}}-hard on general graphs and weakly NP{\mathcal{NP}}-hard on series-parallel graphs. Therefore, the special case on a tree is considered: It is shown that the inverse 2-median problem with variable edge lengths on trees is solvable in polynomial time. For the special case of a star graph we suggest a linear time algorithm.     

An algorithm for optimizing network flow capacity under economies of scale

The problem of optimally allocating a fixed budget to the various arcs of a single-source, single-sink network for the purpose of maximizing network flow capacity is considered. The initial vector of arc capacities is given, and the cost function, associated with each arc, for incrementing capacity is concave; therefore, the feasible region is nonconvex. The problem is approached by Benders' decomposition procedure, and a finite algorithm is developed for solving the nonconvex relaxed master problems. A numerical example of optimizing network flow capacity, under economies of scale, is included.This research was supported by the National Science Foundation, Grant No. GK-32791.     

The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm

This paper is concerned with the minimum cost flow problem. It is shown that the class of dual algorithms which solve this problem consists of different variants of a common general algorithm. We develop a new variant which is, in fact, a new form of the ‘primal-dual algorithm’ and which has several interesting properties. It uses, explicitly only dual variables. The slope of the change in the (dual) objective is monotone. The bound on the maximum number of iterations to solve a problem with integral bounds on the flow is better than bounds for other algorithms. This paper is part of the author's doctoral dissertation submitted at Yale University.     

The multi-terminal maximum-flow network-interdiction problem

This paper defines and studies the multi-terminal maximum-flow network-interdiction problem (MTNIP) in which a network user attempts to maximize flow in a network among K ? 3 pre-specified node groups while an interdictor uses limited resources to interdict network arcs to minimize this maximum flow. The paper proposes an exact (MTNIP-E) and an approximating model (MPNIM) to solve this NP-hard problem and presents computational results to compare the models. MTNIP-E is obtained by first formulating MTNIP as bi-level min-max program and then converting it into a mixed integer program where the flow is explicitly minimized. MPNIM is binary-integer program that does not minimize the flow directly. It partitions the node set into disjoint subsets such that each node group is in a different subset and minimizes the sum of the arc capacities crossing between different subsets. Computational results show that MPNIM can solve all instances in a few seconds while MTNIP-E cannot solve about one third of the problems in 24 hour. The optimal objective function values of both models are equal to each other for some problems while they differ from each other as much as 46.2% in the worst case. However, when the post-interdiction flow capacity incurred by the solution of MPNIM is computed and compared to the objective value of MTNIP-E, the largest difference is only 7.90% implying that MPNIM may be a very good approximation to MTNIP-E.     

有预算限制的最大多种物资流问题

研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.