Analysis of budget for interdiction on multicommodity network flows

In this paper, we concentrate on computing several critical budgets for interdiction of the multicommodity network flows, and studying the interdiction effects of the changes on budget. More specifically, we first propose general interdiction models of the multicommodity flow problem, with consideration of both node and arc removals and decrease of their capacities. Then, to perform the vulnerability analysis of networks, we define the function F(R) as the minimum amount of unsatisfied demands in the resulted network after worst-case interdiction with budget R. Specifically, we study the properties of function F(R), and find the critical budget values, such as \(R_a\), the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and \(R_b\), the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget \(R_b\) for completely destroying the network is not related to arc or node capacities, and supply or demand amounts, but it is related to the network topology, the sets of source and destination nodes, and interdiction costs on each node and arc. We also observe that the critical budget \(R_a\) is related to all of these parameters of the network. Additionally, we present formulations to estimate both \(R_a\) and \(R_b\). For the effects of budget increasing, we present the conditions under which there would be extra capabilities to interdict more arcs or nodes with increased budget, and also under which the increased budget has no effects for the interdictor. To verify these results and conclusions, numerical experiments on 12 networks with different numbers of commodities are performed.     

The Klein bottle and multicommodity flows

LetG be an eulerian graph embedded on the Klein bottle. Then the maximum number of pairwise edge-disjoint orientation-reversing circuits inG is equal to the minimum number of edges intersecting all orientation-reversing circuits. This generalizes a theorem of Lins for the projective plane. As consequences we derive results on disjoint paths in planar graphs, including theorems of Okamura and of Okamura and Seymour.     

Two commodity network flows and linear programming

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.     

Pricing and revenue maximization over a multicommodity transportation network: the nonlinear demand case

This paper is concerned with the design of efficient exact and heuristic algorithms for addressing a bilevel network pricing problem where demand is a nonlinear function of travel cost. The exact method is based on the piecewise linear approximation of the demand function, yielding mixed integer programming formulations, while heuristic procedures are developed within a bilevel trust region framework.     

Speeding up Karmarkar's algorithm for multicommodity flows

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.5s²) 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. Research supported by a fellowship from the Shell Foundation. Research supported by NSF under grant NSF DCR-8404239.     

An alternating linearization bundle method for convex optimization and nonlinear multicommodity flow problems

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.     

An ant colony optimization metaheuristic for single-path multicommodity network flow problems

This paper studies the single-path multicommodity network flow problem (SMNF), inwhich the flow of each commodity can only use one path linking its origin anddestination in the network. We study two versions of this problem based on twodifferent objectives. The first version is to minimize network congestion, anissue of concern in traffic grooming over wavelength division multiplexing(WDM), and in which there generally exists a commodity flow between every pairof nodes. The second problem is a constrained version of the general linearmulticommodity flow problem, in which, for each commodity, a single path isallowed to send the required flow, and the objective is to determine a flowpattern that obeys the arc capacities and minimizes the total shipping cost.Based on the node-arc and the arc-chain representations, we first present twoformulations. Owing to computational impracticality of exact algorithms forpractical networks, we propose an ant colony optimization-(ACO) basedmetaheuristic to deal with SMNF. Considering different problem properties, wedevise two versions of ACO metaheuristics to solve these two problems,respectively. The proposed algorithms’ efficiencies are experimentallyinvestigated on some generated instances of SMNF. The test results demonstratethat the proposed ACO metaheuristics are computationally efficient and robustapproaches for solving SMNF.     

On duality and fractionality of multicommodity flows in directed networks

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

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0,1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C₂,C₃,C₄,…. It is known that C₂ can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing require solving a linear program. In this paper we prove that C₃ can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0,1}ⁿ, this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network.     

Convergent Lagrangian heuristics for nonlinear minimum cost network flows

We consider the separable nonlinear and strictly convex single-commodity network flow problem (SSCNFP). We develop a computational scheme for generating a primal feasible solution from any Lagrangian dual vector; this is referred to as “early primal recovery”. It is motivated by the desire to obtain a primal feasible vector before convergence of a Lagrangian scheme; such a vector is not available from a Lagrangian dual vector unless it is optimal. The scheme is constructed such that if we apply it from a sequence of Lagrangian dual vectors that converge to an optimal one, then the resulting primal (feasible) vectors converge to the unique optimal primal flow vector. It is therefore also a convergent Lagrangian heuristic, akin to those primarily devised within the field of combinatorial optimization but with the contrasting and striking advantage that it is guaranteed to yield a primal optimal solution in the limit. Thereby we also gain access to a new stopping criterion for any Lagrangian dual algorithm for the problem, which is of interest in particular if the SSCNFP arises as a subproblem in a more complex model. We construct instances of convergent Lagrangian heuristics that are based on graph searches within the residual graph, and therefore are efficiently implementable; in particular we consider two shortest path based heuristics that are based on the optimality conditions of the original problem. Numerical experiments report on the relative efficiency and accuracy of the various schemes.     

Improved bounds on the max-flow min-cut ratio for multicommodity flows

In this paper we consider the worst case ratio between the capacity of min-cuts and the value of max-flow for multicommodity flow problems. We improve the best known bounds for the min-cut max-flow ratio for multicommodity flows in undirected graphs, by replacing theO(logD) in the bound byO(logk), whereD denotes the sum of all demands, andk demotes the number of commodities. In essence we prove that up to constant factors the worst min-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rao, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the min-cut max-flow ratio in general undirected graphs is bounded byO(logClogD), whereC denotes the sum of all the capacities. Tragoudas has improved this bound toO(lognlogD), wheren is the number of nodes in the network. Garg, Vazirani and Yannakakis further improved this toO(logklogD). Klein, Plotkin and Rao have proved that for planar networks, the ratio isO(logD).Our result improves the bound for general networks toO(log² k) and the bound for planar networks toO(logk). In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved. The method presented in this paper can be used to give polynomial time approximation algorithms to the minimum cuts in the network up to the above factors.Preliminary version appeared in Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, 1993, 691-697.Research supported by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by a grant from Mitsubishi Electric Laboratories.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

A polyhedral approach to multicommodity survivable network design

Summary. The design of cost-efficient networks satisfying certain survivability constraints is of major concern to the telecommunications industry. In this paper we study a problem of extending the capacity of a network by discrete steps as cheaply as possible, such that the given traffic demand can be accommodated even when a single edge or node in the network fails. We derive valid and nonredundant inequalities for the polyhedron of capacity design variables, by exploiting its relationship to connectivity network design and knapsack-like subproblems. A cutting plane algorithm and heuristics for the problem are described, and preliminary computational results are reported. Received August 26, 1993 / Revised version received February 1994     

A decomposition method for solving multicommodity network equilibria

We consider the numerical aspect of the multicommodity network equilibrium problem proposed by Rockafellar in 1995. Our method relies on the flexible monotone operator splitting framework recently proposed by Combettes and Eckstein.     

An implementation of steepest-descent augmentation for linear programs

Generalizing the simplex method, circuit augmentation schemes for linear programs follow circuit directions through the interior of the underlying polyhedron. Steepest-descent augmentation is especially promising, but an implementation of the iterative scheme is a significant challenge. We work towards a viable implementation through a model in which a single linear program is updated dynamically to remain in memory throughout. Computational experiments exhibit dramatic improvements over a naïve approach and reveal insight into the next steps required for large-scale computations.     

An implementation of Karmarkar's algorithm for linear programming

This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.     

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.     

Uniform multicommodity flows in the hypercube with random edge‐capacities

We give two results for multicommodity flows in the d‐dimensional hypercube with independent random edge‐capacities distributed like a random variable C where . Firstly, with high probability as , the network can support simultaneous multicommodity flows of volume close to between all antipodal vertex pairs. Secondly, with high probability, the network can support simultaneous multicommodity flows of volume close to between all vertex pairs. Both results are best possible. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 437–463, 2017