Search

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

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

We give a bundle method for minimizing the sum of two convex functions, one of them being known only via an oracle of arbitrary accuracy. Each iteration involves solving two subproblems in which the functions are alternately represented by their linearizations. Our approach is motivated by applications to nonlinear multicommodity flow problems. Encouraging numerical experience on large scale problems is reported.

This paper proposes an implementation of a constrained analytic center cutting plane method to solve nonlinear multicommodity flow problems. The new approach exploits the property that the objective of the Lagrangian dual problem has a smooth component with second order derivatives readily available in closed form. The cutting planes issued from the nonsmooth component and the epigraph set of the smooth component form a localization set that is endowed with a self-concordant augmented barrier. Our implementation uses an approximate analytic center associated with that barrier to query the oracle of the nonsmooth component. The paper also proposes an approximation scheme for the original objective. An active set strategy can be applied to the transformed problem: it reduces the dimension of the dual space and accelerates computations. The new approach solves huge instances with high accuracy. The method is compared to alternative approaches proposed in the literature.

We propose a modification of the proximal decomposition method investigated by Spingarn [30] and Mahey et al. [19] for minimizing a convex function on a subspace. For the method to be favorable from a computational point of view, particular importance is the introduction of approximations in the proximal step. First, we couple decomposition on the graph of the epsilon-subdifferential mapping and cutting plane approximations to get an algorithmic pattern that falls in the general framework of Rockafellar inexact proximal-point algorithms [26]. Recently, Solodov and Svaiter [27] proposed a new proximal point-like algorithm that uses improved error criteria and an enlargement of the maximal monotone operator defining the problem. We combine their idea with bundle mecanism to devise an inexact proximal decomposition method with error condition which is not hard to satisfy in practice. Then, we present some applications favorable to our development. First, we give a new regularized version of Benders decomposition method in convex programming called the proximal convex Benders decomposition algorithm. Second, we derive a new algorithm for nonlinear multicommodity flow problems among which the message routing problem in telecommunications data networks.

We study the polyhedra of splittable and unsplittable single arc-set relaxations of multicommodity flow capacitated network design problems. We investigate the optimization problems over these sets and the separation and lifting problems of valid inequalities for them. In particular, we give a linear-time separation algorithm for the residual capacity inequalities (19) and show that the separation problem of c-strong in- equalities (7) is NP -hard, but can be solved over the subspace of fractional variables only. We introduce two classes of inequalities for the unsplittable flow problems. We present a summary of computational experiments with a branch-and-cut algorithm for multicommodity flow capacitated network design problems to test the effectiveness of the results presented here empirically.

We present fast and simple fully polynomial-time approximation schemes (FPTAS) for generalized versions of maximum flow, multicommodity flow, minimum cost maximum flow, and minimum cost multicommodity flow. We extend and refine fractional packing frameworks introduced in FPTAS’s for traditional multicommodity flow and packing linear programs. Our FPTAS’s dominate the previous best known complexity bounds for all of these problems, some by more than a factor of n2, where n is the number of nodes. This is accomplished in part by introducing an efficient method of solving a sequence of generalized shortest path problems. Our generalized multicommodity FPTAS’s are now as fast as the best non-generalized ones. We believe our improvements make it practical to solve generalized multicommodity flow problems via combinatorial methods.

The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to the 1960s, when the solitaire cone was first described by Boardman and Conway. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper we study the extremal structure of solitaire cones for a variety of boards, and relate their structure to the well studied metric cone. In particular we give:¶1. an equivalence between the multicommodity flow problem with associated dual metric cone and a generalized peg game with associated solitaire cone;¶2. a related NP-completeness result;¶3. a method of generating large classes of facets;¶4. a complete characterization of 0-1 facets;¶5. exponential upper and lower bounds (in the dimension) on the number of facets;¶6. results on the number of facets, incidence and adjacency relationships and diameter for small rectangular, toric and triangular boards;¶7. a complete characterization of the adjacency of extreme rays, diameter, number of 2-faces and edge connectivity for rectangular toric boards.

Cover title. "The extended abstract of this article appeared in the proceedings of the 5th International IPCO Conference, Vancouver, June 1996."--P. 1.

We consider the problem of finding a feasible flow in a directed networkG = (N,A) in which each nodei ź N has a supplyb(i), and each arc(i,j) ź A has a zero lower bound on flow and an upper bounduij. It is well known that this feasibility problem can be transformed into a maximum flow problem. It is also well known that there is no feasible flow in the networkG if and only if there is a subsetS of nodes such that the net supplies of the nodes inS exceeds the capacity of the arcs emanating fromS. Such a setS is called a"witness of infeasibility" (or, simply, awitness) of the network flow problem. In the case that there are many different witnesses for an infeasible problem, a small cardinality witness may be preferable in practice because it is generally easier for the user to assimilate, and may provide more guidance to the user on how to identify the cause of the infeasibility. Here we show that the problem of finding a minimum cardinality witness is NP-hard. We also consider the problem of determining aminimal witness, that is, a witnessS such that no proper subset ofS is also a witness. In this paper, we show that we can determine a minimal witness by solving a sequence of at mostn maximum flow problems. Moreover, if we use the preflow-push algorithm to solve the resulting maximum flow problems and organize computations properly, then the total time taken by the algorithm is comparable to that of solving a single maximum flow problem. This approach determines a minimal cardinality witness in O(n2m1/2) time using simple data structures and in O(nm logn) time using the standard implementation of the dynamic tree data structures. We also show that the recognition version of the minimal witness problem is equivalent to a recognition version of a related problem known as theminimum rooted cut problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

Consider a directed graphG = (V,A), and a set of traffic demands to be shipped between pairs of nodes inV. Capacity has to be installed on the edges of this graph (in integer multiples of a base unit) so that traffic can be routed. In this paper we consider the problem of minimum cost installation of capacity on the arcs to ensure that the required demands can be shipped simultaneously between node pairs. We study two different approaches for solving problems of this type. The first one is based on the idea of metric inequalities (see Onaga and Kakusho, On feasibility conditions of multicommodity flows in networks, IEEE Transactions on Circuit Theory, CT-18 (4) (1971) 425---429.), and uses a formulation with only |A| variables. The second uses an aggregated multicommodity flow formulation and has |V||A| variables. We first describe two classes of strong valid inequalities and use them to obtain a complete polyhedral description of the associated polyhedron for the complete graph on three nodes. Next we explain our solution methods for both of the approaches in detail and present computational results. Our computational experience shows that the two formulations are comparable and yield effective algorithms for solving real-life problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

We show that an e-approximate solution of the cost-constrainedK-commodity flow problem on anN-nodeM-arc network,G can be computed by sequentially solving O(K(ɛ −2+logGK) logGM log (Gɛ −1 GK)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in $$\tilde O$$ (Gɛ −2 GKNM) running time, where the notation O(·) means “up to logarithmic factors”. This result improves the time bound mentioned by Grigoriadis and Khachiyan [4] by a factor ofM/N and that developed more recently by Karger and Plotkin [8] by a factor ofɛ −1. We also provide a simple $$\tilde O$$ (NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is $$\tilde O$$ (ɛ −3) times faster than the algorithm developed in the latter paper.

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O (k((Epsilon)^-2 + log k) log n) 1-commodity minimum-cost flow computations, where k is the number of commodities, n is the number of nodes, and (Epsilon) is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem..

We show how to speed up Karmarkar's linear programming algorithm for the case of multicommodity flows. The special structure of the constraint matrix is exploited to obtain an algorithm for the multicommodity flow problem which requires O(s 3.5 v 2.5 eL) arithmetic operations, each operation being performed to a precision of O (L) bits. Herev is the number of vertices ande is the number of edges in the given network,s is the number of commodities, andL is bounded by the number of bits in the input. We obtain a speed up of the order of (e 0.5/v 0.5)+(e 2.5/v 2.5s2) over Karmarkar's modified algorithm which is substantial for dense networks. The techniques in the paper can also be used to speed up any interior point algorithm for any linear programming problem whose constraint matrix is structurally similar to the one in the multicommodity flow problem.

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable. We describe computational experience with a cutting plane algorithm for this problem.

LetN = (G, T, c, a) be a network, whereG is an undirected graph,T is a distinguished subset of its vertices (calledterminals), and each edgee ofG has nonnegative integer-valuedcapacity c(e) andcost a(e). Theminimum cost maximum multi(commodity)flow problem (*) studied in this paper is to find ac-admissible multiflowf inG such that: (i)f is allowed to contain partial flows connecting any pairs of terminals, (ii) the total value off is as large as possible, and (iii) the total cost off is as small as possible, subject to (ii). This generalizes, on one hand, the undirected version of the classical minimum cost maximum flow problem (when |T| = 2), and, on the other hand, the problem of finding a maximum fractional packing ofT-paths (whena ≡ 0). Lovasz and Cherkassky independently proved that the latter has a half-integral optimal solution.

A generalization of the maximum-flow problem is considered in which every unit of flow sent from the source to the sink yields a payoff of $k. In addition, the capacity of any arce can be increased at a per-unit cost of $c e . The problem is to determine how much arc capacity to purchase for each arc and how much flow to send so as to maximize the net profit. This problem can be modeled as a circulation problem. The main result of this paper is that this circulation problem can be solved by the network simplex method in at mostkmn pivots. Whenc e = 1 for each arce, this yields a strongly polynomial-time simplex method. This result uses and extends a result of Goldfarb and Hao which states that the standard maximum-flow problem can be solved by the network simplex method in at mostmn pivots.

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.

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

Many design decisions in transporation, communication, and manufacturing planning can be modeled as problems of routing multiple commodities between various origin and destination nodes of a directed network. Each arc of the network is uncapacitated and carries a fixed charge as well as a cost per unit of flow. We refer to the general problem of selecting a subset of arcs and routing the required multi-commodity flows along the chosen arcs at a minimum total cost as the fixed charge network design problem. This paper focuses on strenghthening the linear programming relaxation of a path-flow formulation for this problem. The considerable success achieved by researchers in solving many related design problems with algorithms that use strong linear programming-based lower bounds motivates this study. We first develop a convenient characterization of fractional extreme points for the network design linear programming relaxation. An auxiliary graph introduced for this characterization also serves to generate two families of cuts that exclude some fractional solutions without eliminating any feasible integer solutions. We discuss a separation procedure for one class of inequalities and demonstrate that many of our results generalize known properties of the plant location problem.

The concept of an optimal flow in a multiple source, multiple sink network is defined. It generalizes maximal flow in a single source, single sink network. An existence proof and an algorithm are given.

Suppose thatG is an undirected graph whose edges have nonnegative integer-valued lengthsl(e), and that {s1,t1},⋯, {sm,tm} are pairs of its vertices. Can one assign nonnegative weights to the cuts ofG such that, for each edgee, the total weight of cuts containinge does not exceedl(e) and, for eachi, the total weight of cuts ‘separating’si andti is equal to the distance (with respect tol) betweensi andti? Using linear programming duality, it follows from Papernov's multicommodity flow theorem that the answer is affirmative if the graph induced by the pairs {s1,t1},⋯, {sm,tm} is one of the following: (i) the complete graph with four vertices, (ii) the circuit with five vertices, (iii) a union of two stars. We prove that if, in addition, each circuit inG has an even length (with respect tol) then there exists a suitable weighting of the cuts with the weights integer-valued; moreover, an algorithm of complexity O(n3) (n is the number of vertices ofG) is developed for solving such a problem. Also a class of metrics decomposable into a nonnegative linear combination of cut-metrics is described, and it is shown that the separation problem for cut cones isNP-hard.

This paper shows that the linear programming formulation of the two-commodity network flow problem leads to a direct derivation of the known results concerning this problem. An algorithm for solving the problem is given which essentially consists of two applications of the Ford—Fulkerson max flow computation. Moreover, the algorithm provides constructive proofs for the results. Some new facts concerning feasible integer flows are also given.

For any integern, a modified transportation problem with 2n + 2 nodes is constructed which requires 2 n + 2 n−2−2 iterations using all but one of the most commonly used minimum cost flow algorithms. As a result, the Edmonds—Karp Scaling Method [3] becomes the only known “good” (in the sense of Edmonds) algorithm for computing minimum cost flows.

A partitioning algorithm for solving the general minimum cost multicommodity flow problem for directed graphs is presented in the framework of a network flow method and the dual simplex method. A working basis which is considerably smaller than the number of capacitated arcs in the given network is employed and a set of simple secondary constraints is periodically examined. Some computational aspects and preliminary experimental results are discussed.

The classic traveling salesman problem is characterized in terms of continuous flows on a specially constructed non-conservative network, in 2n ź 1 linear constraints and a cardinality constraint. It is shown that every solution to the network problem is a hamiltonian circuit.