A unified framework for primal-dual methods in minimum cost network flow problems

We introduce a broad class of algorithms for finding a minimum cost flow in a capacitated network. The algorithms are of the primal-dual type. They maintain primal feasibility with respect to capacity constraints, while trying to satisfy the conservation of flow equation at each node by means of a wide variety of procedures based on flow augmentation, price adjustment, and ascent of a dual functional. The manner in which these procedures are combined is flexible thereby allowing the construction of algorithms that can be tailored to the problem at hand for maximum effectiveness. Particular attention is given to methods that incorporate features from classical relaxation procedures. Experimental codes based on these methods outperform by a substantial margin the fastest available primal-dual and primal simplex codes on standard benchmark problems.This work was supported by the National Science Foundation under Contract NSF/ECS 8217668.     

Lagrangian Relaxations on Networks by <Emphasis Type="Italic">ε</Emphasis>-Subgradient Methods

The efficiency of the network flow techniques can be exploited in the solution of nonlinearly constrained network flow problems by means of approximate subgradient methods. The idea is to solve the dual problem by using ε-subgradient methods, where the dual function is estimated by minimizing approximately a Lagrangian function, which relaxes the side constraints and is subject only to network constraints. In this paper, convergence results for some kind of ε-subgradient methods are put forward. Moreover, in order to evaluate the quality of the solution and the efficiency of these methods some of them have been implemented and their performances computationally compared with codes that are able to solve the proposed test problems.     

A tabu search approach for solving a difficult forest harvesting machine location problem

This paper deals with two main problems in forest harvesting. The first is that of selecting the locations for the machinery to haul logs from the points where they are felled to the roadside. The second consists in designing the access road network connecting the existing road network with the points where machinery is installed. Their combination induces a very important and difficult problem to solve in forest harvesting. It can be formulated as a combination of two difficult optimization problems: a plant location problem and a fixed charge network flow problem. In this paper, we propose a solution approach based on tabu search. The proposed heuristic includes several enhancements of the basic tabu search framework. The main difficulty lies in evaluating neighboring solutions, which involves decisions related to location of machinery and to road network arcs. Hence, the neighborhood is more complex than in typical applications of metaheuristics. Minimum spanning tree algorithms and Steiner tree heuristics are used to deal with this problem. Numerical results indicate that the heuristic approach is very attractive and leads to better solutions than those provided by state-of-the-art integer programming codes in limited computation times, with solution times significantly smaller. The numerical results do not vary too much when typical parameters such as the tabu tenure are modified, except for the dimension of neighborhood.     

An algorithm to solve the proportional network flow problem

The proportional network flow problem is a generalization of the equal flow problem on a generalized network in which the flow on arcs in given sets must all be proportional. This problem appears in several natural contexts, including processing networks and manufacturing networks. This paper describes a transformation on the underlying network that reduces the problem to the equal flow problem; this transformation is used to show that algorithms that solve the equal flow problem can be directly applied to the proportional network flow problem as well, with no increase in asymptotic running time. Additionally, computational results are presented for the proportional network flow problem demonstrating equivalent performance to the same algorithm for the equal flow problem.     

On the computational behavior of a polynomial-time network flow algorithm

A variation on the Edmonds-Karp scaling approach to the minimum cost network flow problem is examined. This algorithm, which scales costs rather than right-hand sides, also runs in polynomial time. Large-scale computational experiments indicate that the computational behavior of such scaling algorithms may be much better than had been presumed. Within several distributions of square, dense, capacitated transportation problems, a cost scaling code, SCALE, exhibits linear growth in average execution time with the number of edges, while two network simplex codes, RNET and GNET, exhibit greater than linear growth.Our experiments reveal that median and mean execution times are predictable with surprising accuracy for all of the three codes and all three distributions from which test problems were generated. Moreover, for fixed problem size, individual execution times appear to behave as though they are approximately lognormally distributed with constant variance. The experiments also reveal sensitivity of the parameters in the models, and in the models themselves, to variations in the distribution of problems. This argues for caution in the interpretation of such computational studies beyond the realm in which the computations were performed.This work has been supported in part by NSF grants ENG-7910807, ECS-8313853, DMS-8706133, and DDM-8813054, and by AFOSR, NSF, and ONR under NSF grant DMS-8920550 to Cornell University, and by a Sloan Foundation research fellowship held by the first author.     

Network reoptimization procedures for multiobjective network probelems

Network models are attractive because of their computational efficiency. Network applications can involve multiple objective analysis. Multiple objective analysis requires generating nondominated solutions in various forms. Two general methods exist to generate new solutions in continuous optimization: changing objective function weights and inserting objective bounds through constraints. In network flow problems, modifying weights is straightforward, allowing use of efficient network codes. Use of bounds on objective attainment levels can provide a more controlled generation of solutions reflecting tradeoffs among objectives. To constrain objective attainment, however, would require a side constrained network code, sacrificing some computational efficiency for greater model flexibility. We develop reoptimization procedures for the side constrained problem and use them in conjunction with simplex-based techniques. Our approach provides a useful tool for generating solutions allowing greater decision maker control over objective attainments, allowing multiobjective analysis of large-scale problems. Results are compared with solutions obtained from the computationally more attractive weighting technique. Reoptimization procedures are discussed as a means of more efficiently conducting multiple objective network analyses.     

Maximum-throughput dynamic network flows

This paper presents and solves the maximum throughput dynamic network flow problem, an infinite horizon integer programming problem which involves network flows evolving over time. The model is a finite network in which the flow on each arc not only has an associated upper and lower bound but also an associated transit time. Flow is to be sent through the network in each period so as to satisfy the upper and lower bounds and conservation of flow at each node from some fixed period on. The objective is to maximize the throughput, the net flow circulating in the network in a given period, and this throughput is shown to be the same in each period. We demonstrate that among those flows with maximum throughput there is a flow which repeats every period. Moreover, a duality result shows the maximum throughput equals the minimum capacity of an appropriately defined cut. A special case of the maximum dynamic network flow problem is the problem of minimizing the number of vehicles to meet a fixed periodic schedule. Moreover, the elegantsolution derived by Ford and Fulkerson for the finite horizon maximum dynamic flow problem may be viewed as a special case of the infinite horizon maximum dynamic flow problem and the optimality of solutions which repeat every period.     

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.     

Lexicographic optimisation in generalised network flow problems

In this paper the lexicographic optimisation of the multiobjective generalised network flow problem is considered. Optimality conditions are proved on the basis of the equivalence of this problem and a weighted generalised network flow problem. These conditions are used to develop a network-based algorithm which properly modifies primal-dual algorithms for minimum cost generalised network flow problems. Computational results indicate that this algorithm is faster than general-purpose algorithms for linear lexicographic optimisation. Besides, this model is used for approaching a water resource system design problem.     

The flow circulation sharing problem

The flow circulation sharing problem is defined as a network flow circulation problem with a maximin objective function. The arcs in the network are partitioned into regular arcs and tradeoff arcs where each tradeoff arc has a non-decreasing tradeoff function associated with it. All arcs have lower and upper bounds on their flow while the value of the smallest tradeoff function is maximized. The model is useful in equitable resource allocation problems over time which is illustrated in a coal strike example and a submarine assignment example. Some properties including optimality conditions are developed. Each cut in the network defines a knapsack sharing problem which leads to an optimality condition similar to the max flow/min cut theorem. An efficient algorithm for both the continuous and integer versions of the flow circulation sharing problem is developed and computational experience given. In addition, efficient algorithms are developed for problems where some of the arcs have infinite flow upper bounds.     

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.     

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.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

An optimal capacity assignment for the robust design problem in capacitated flow networks

This paper proposes an exact algorithm to solve the robust design problem in a capacitated flow network in which each edge has several possible capacities. A capacitated flow network is popular in our daily life. For example, the computer network, the power transmission network, or even the supply chain network are capacitated flow networks. In practice, such network may suffer failure, partial failure or maintenance. Therefore, each edge in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. However, how to optimally assign the capacity to each edge is not an easy task. Although this kind of problem was known of NP-hard, this paper proposes an efficient exact algorithm to search for the optimal solutions for such a network and illustrates the efficiency of the proposed algorithm by numerical examples.     

Solving the resource constrained deadline scheduling problem via reduction to the network flow problem

In this paper the problem of the equivalence of scheduling tasks on processors with the presence of deadlines and additional resources and the network flow problem is studied. This equivalence permits it to be proven that the problem of finding a maximal flow in a binary network with multipliers equal to 1 or 2 is NP-complete.     

A comparison of adaptive time stepping methods for coupled flow and deformation modeling

Many subsurface reservoirs compact or subside due to production-induced pressure changes. Numerical simulation of this compaction process is important for predicting and preventing well-failure in deforming hydrocarbon reservoirs. However, development of sophisticated numerical simulators for coupled fluid flow and mechanical deformation modeling requires a considerable manpower investment. This development time can be shortened by loosely coupling pre-existing flow and deformation codes via an interface. These codes have an additional advantage over fully-coupled simulators in that fewer flow and mechanics time steps need to be taken to achieve a desired solution accuracy. Specifically, the length of time before a mechanics step is taken can be adapted to the rate of change in output parameters (pressure or displacement) for the particular application problem being studied. Comparing two adaptive methods (the local error method—a variant of Runge–Kutta–Fehlberg for solving ode’s—and the pore pressure method) to a constant step size scheme illustrates the considerable cost savings of adaptive time stepping for loose coupling. The methods are tested on a simple loosely-coupled simulator modeling single-phase flow and linear elastic deformation. For the Terzaghi consolidation problem, the local error method achieves similar accuracy to the constant step size solution with only one third as many mechanics solves. The pore pressure method is an inexpensive adaptive method whose behavior closely follows the physics of the problem. The local error method, while a more general technique and therefore more expensive per time step, is able to achieve excellent solution accuracy overall.     

Bilinear modeling solution approach for fixed charge network flow problems

We present a continuous, bilinear formulation for the fixed charge network flow problem. This formulation is used to derive an exact algorithm for the fixed charge network flow problem converging in a finite number of steps. Some preliminary computational experiments are reported to show the performance of the algorithm.     

Routing of Railway Carriages

In the context of organizing timetables for railway companies the following railway carriage routing problem occurs. Given a timetable containing rail links with departure and destination times/stations and the composition of the trains, find a routing of railway carriages such that the required carriages are always available when a train departs. The problem is formulated as an integer multi-commodity network flow problem with nonlinear objective function. We will present a local search approach for this NP-hard problem. The approach uses structural properties of the integer multi-commodity network flow formulation of the problem. Computational results for a real world instance are given.     

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.