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.     

On Solving Quickest Time Problems in Time-Dependent, Dynamic Networks

In this paper, a pseudopolynomial time algorithm is presented for solving the integral time-dependent quickest flow problem (TDQFP) and its multiple source and sink counterparts: the time-dependent evacuation and quickest transshipment problems. A more widely known, though less general version, is the quickest flow problem (QFP). The QFP has historically been defined on a dynamic network, where time is divided into discrete units, flow moves through the network over time, travel times determine how long each unit of flow spends traversing an arc, and capacities restrict the rate of flow on an arc. The goal of the QFP is to determine the paths along which to send a given supply from a single source to a single sink such that the last unit of flow arrives at the sink in the minimum time. The main contribution of this paper is the time-dependent quickest flow (TDQFP) algorithm which solves the TDQFP, i.e. it solves the integral QFP, as defined above, on a time-dependent dynamic network, where the arc travel times, arc and node capacities, and supply at the source vary with time. Furthermore, this algorithm solves the time-dependent minimum time dynamic flow problem, whose objective is to determine the paths that lead to the minimum total time spent completing all shipments from source to sink. An optimal solution to the latter problem is guaranteed to be optimal for the TDQFP. By adding a small number of nodes and arcs to the existing network, we show how the algorithm can be used to solve both the time-dependent evacuation and the time-dependent quickest transshipment problems. This revised version was published online in August 2006 with corrections to the Cover Date.     

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.     

A characterization of network representable polymatroids

Meggido [1974] showed that the maximum flow through sets of sources in a multiple sink flow network is a polymatroidal function. Recently, Federgruen and Groenevelt [1985], [1986] have considered polymatroids that can be represented by a multiple source flow network and have improved the runnung time of an important scheduling application.We give a characterization of network representability and relate representable polymatroids to the theory of gammoids.

---

Zusammenfassung Meggido [1974] hat gezeigt, daß ein maximaler Fluß durch ein Netzwerk mit mehrfachen Senken eine polymatroidale Funktion beschreibt. Federgruen und Groenvelt [1985], [1986] haben kürzlich solche Polymatroide betrachtet, die durch Flüsse in derartigen Netzwerken repräsentiert werden können und haben so die Laufzeit einer wichtigen Schedulinganwendung verbessern können.Wir geben eine Charakterisierung von Funktionen, die durch derartige Netzflußnetzwerke realisierbar sind. Dabei stellen wir eine Verbindung her zwischen Repräsentierbarkeit und Gammoidtheorie.

     

An introduction to dynamic generative networks: Minimum cost flow

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.     

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 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.     

A Hybrid Immersed Interface Method for Driven Stokes Flow in an Elastic Tube

We present a hybrid numerical method for simulating fluid flow through a compliant, closed tube, driven by an internal source and sink. Fluid is assumed to be highly viscous with its motion described by Stokes flow. Model geometry is assumed to be axisymmetric, and the governing equations are implemented in axisymmetric cylindrical coordinates, which capture 3D flow dynamics with only 2D computations. We solve the model equations using a hybrid approach: we decompose the pressure and velocity fields into parts due to the surface forcings and due to the source and sink, with each part handled separately by means of an appropriate method. Because the singularly-supported surface forcings yield an unsmooth solution, that part of the solution is computed using the immersed interface method. Jump conditions are derived for the axisymmetric cylindrical coordinates. The velocity due to the source and sink is calculated along the tubular surface using boundary integrals. Numerical results are presented that indicate second-order accuracy of the method.     

Minimum cost flow algorithms for series-parallel networks

It is shown that an acyclic multigraph with a single source and a single sink is series-parallel if and only if for arbitrary linear cost functions and arbitrary capacities the corresponding minumum cost flow problem can be solved by a greedy algorithm. Furthermore, for networks of this type with m edges and n vertices, two O(mn+logm)-algorithms. One of them is based on the greedy scheme.     

Combined effects of non-uniform heat source/sink and thermal radiation on heat transfer over an unsteady stretching permeable surface

The present paper is concerned with the study of flow and heat transfer characteristics in the unsteady laminar boundary layer flow of an incompressible viscous fluid over continuously stretching permeable surface in the presence of a non-uniform heat source/sink and thermal radiation. The unsteadiness in the flow and temperature fields is because of the time-dependent stretching velocity and surface temperature. Similarity transformations are used to convert the governing time-dependent nonlinear boundary layer equations for momentum and thermal energy are reduced to a system of nonlinear ordinary differential equations containing Prandtl number, non-uniform heat source/sink parameter, thermal radiation and unsteadiness parameter with appropriate boundary conditions. These equations are solved numerically by applying shooting method using Runge–Kutta–Fehlberg method. Comparison of numerical results is made with the earlier published results under limiting cases. The effects of the unsteadiness parameter, thermal radiation, suction/injection parameter, non-uniform heat source/sink parameter on flow and heat transfer characteristics as well as on the local Nusselt number are shown graphically.     

Network-based formulations of the quadratic assignment problem

We present two formulations of the Quadratic Assignment Problem (QAP) that result in network flow problems with integer variables and side constraints. A linearization of the QAP is obtained in both cases by considering each facility to consist of two parts—a source for all outgoing flows from that facility, and a sink for all incoming flows to the facility. Preliminary computational experience with both approaches is presented.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

The quickest path problem with batch constraints

The quickest path problem has been proposed to cope with flow problems through networks whose arcs are characterized by both travel times and flowrate constraints. Basically, it consists in finding a path in a network to transmit a given amount of items from a source node to a sink in as little time as possible, when the transmission time depends on both the traversal times of the arcs and the rates of flow along arcs. This paper is focused on the solution procedure when the items transmission must be partitioned into batches with size limits. For this problem we determine how many batches must be made and what the sizes should be.     

A generalized bi-criteria fuzzy integer flow sharing problem

The flow sharing problem is a class of techniques that can be used to find the optimal flow in a capacitated network, which realizes an equitable distribution of flows. This paper extends the integer flow sharing problem by considering fuzzy capacities and fuzzy weights such that the flux received at each sink node and the flow value through each arc are restricted to be multiples of some block unit. Fuzzy capacity describes the flexibility of the upper limit of flow value through each arc. Fuzzy weight represents the degree of satisfaction of the flux to a sink node. Our model has the two following criteria: to maximize the minimal degree of satisfaction among all of the fuzzy capacity constraints and to maximize the minimal degree of satisfaction among the fluxes to all of the sink nodes. Because an optimal flow pattern that simultaneously maximizes the two objectives is usually not feasible, we define non-domination in this setting and propose a pseudo-polynomial algorithm that finds some non-dominated flow patterns. Finally, a numerical example is presented to demonstrate how our algorithm works.     

Analytical vortex and source surface distributions for flow about elliptical cylinders

Summary A cylindrical body is introduced into a potential flow and the resulting disturbance is treated using only an analytical singularity distribution on the surface of the body. Conformai transformation methods, using previously published results for singularity distributions on a circular cylinder, enable the derivation of the required form of vorticity distribution on the transformed body. This approach, however, does not facilitate the derivation of the analogous source/sink distribution. For an elliptic cylinder, examples of vorticity distributions are presented and a new solution is obtained giving the source/sink distribution on the surface of the cylinder in a uniform stream at incidence.     

Convective heat and mass transfer in three-dimensional mixed convection flow of viscoelastic fluid in presence of chemical reaction and heat source/sink

Heat and mass transfer effects in the three-dimensional mixed convection flow of a viscoelastic fluid with internal heat source/sink and chemical reaction have been investigated in the present work. The flow generation is because of an exponentially stretching surface. Magnetic field normal to the direction of flow is considered. Convective conditions at the surface are also encountered. Appropriate similarity transformations are utilized to reduce the boundary layer partial differential equations into the ordinary differential equations. The homotopy analysis method is used to develop the solution expressions. Impacts of different controlling parameters such as ratio parameter, Hartman number, internal heat source/sink, chemical reaction, mixed convection, concentration buoyancy parameter and Biot numbers on the velocity, temperature and concentration profiles are analyzed. The local Nusselt and Sherwood numbers are sketched and examined.     

Analytic solutions of unsteady boundary flow and heat transfer on a permeable stretching sheet with non-uniform heat source/sink

In this paper, we study the boundary layer flow and heat transfer on a permeable unsteady stretching sheet with non-uniform heat source/sink. The analytic solutions are obtained by using suitable similarity transformations and homotopy analysis method (HAM). Furthermore, the effects of unsteadiness parameter, Prandtl number and heat source/sink parameter on the dynamics are analyzed and discussed.     

Revisiting parametric multi-terminal problems: Maximum flows, minimum cuts and cut-tree computations

Given an undirected network, the multi-terminal network flows analysis consists in determining the all pairs maximum flow values. In this paper, we consider an undirected network in which some edge capacities are allowed to vary and we analyze the impact of such variations on the all pairs maximum flow values. We first provide an efficient algorithm for the single parametric capacity case, and then propose a generalization to the case of multiple parametric capacities. Moreover, we provide a study on Gomory–Hu cut-tree relationships.     

Generate upper boundary vectors meeting the demand and budget for a p-commodity network with unreliable nodes

The system capacity for a single-commodity flow network is the maximum flow from the source to the sink. This paper discusses the system capacity problem for a p-commodity limited-flow network with unreliable nodes. In such a network, arcs and nodes all have several possible capacities and may fail. Different types of commodity, which are transmitted through the same network simultaneously, competes the capacities of arcs and nodes. In particular, the consumed capacity by different types of commodity varies from arcs and nodes. We first define the system capacity as a vector and then a performance index, the probability that the upper bound of the system capacity is a given pattern subject to the budget constraint, is proposed. Such a performance index can be easily computed in terms of upper boundary vectors meeting the demand and budget. A simple algorithm based on minimal cuts is thus presented to generate all upper boundary vectors. The manager can apply this performance index to measure the system capacity level for a supply-demand system.     

Heat transfer in MHD viscoelastic boundary layer flow over a stretching sheet with thermal radiation and non-uniform heat source/sink

An analysis has been carried out to study the flow and heat transfer characteristics for MHD viscoelastic boundary layer flow over an impermeable stretching sheet with space and temperature dependent internal heat generation/absorption (non-uniform heat source/sink), viscous dissipation, thermal radiation and magnetic field due to frictional heating. The flow is generated due to linear stretching of the sheet and influenced by uniform magnetic field, which is applied vertically in the flow region. The governing partial differential equations for the flow and heat transfer are transformed into ordinary differential equations by a suitable similarity transformation. The governing equations with the appropriate conditions are solved exactly. The effects of viscoelastic parameter and magnetic parameter on skin friction and the effects of viscous dissipation, non-uniform heat source/sink and the thermal radiation on heat transfer characteristics for two general cases namely, the prescribed surface temperature (PST) case and the prescribed wall heat flux (PHF) case are presented graphically and discussed. The numerical results for the wall temperature gradient (the Nusselt number) are presented in tables and are discussed.