An exact approach for the maximum concurrent k-splittable flow problem

We consider the maximization of a multicommodity flow throughput in presence of constraints on the maximum number of paths to be used. Such an optimization problem is strongly NP-hard, and is known in the literature as the maximum routable demand fraction variant of the k-splittable flow problem. Here we propose an exact approach based on branch and bound rules and on an arc-flow mixed integer programming formulation of the problem. Computational results are provided, and a comparison with a standard commercial solver is proposed.     

An exact solution approach for the interdiction median problem with fortification

Systematic approaches to security investment decisions are crucial for improved homeland security. We present an optimization modeling approach for allocating protection resources among a system of facilities so that the disruptive effects of possible intentional attacks to the system are minimized. This paper is based upon the p-median service protocol for an operating set of p facilities. The primary objective is to identify the subset of q facilities which, when fortified, provides the best protection against the worst-case loss of r non-fortified facilities. This problem, known as the r-interdiction median problem with fortification (IMF), was first formulated as a mixed-integer program by Church and Scaparra [R.L. Church, M.P. Scaparra, Protecting critical assets: The r-interdiction median problem with fortification, Geographical Analysis 39 (2007) 129–146]. In this paper, we reformulate the IMF as a maximal covering problem with precedence constraints, which is amenable to a new solution approach. This new approach produces good approximations to the best fortification strategies. Furthermore, it provides upper and lower bounds that can be used to reduce the size of the original model. The reduced model can readily be solved to optimality by general-purpose MIP solvers. Computational results on two geographical data sets with different structural characteristics show the effectiveness of the proposed methodology for solving IMF instances of considerable size.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

Cutting plane algorithms for the inverse mixed integer linear programming problem

We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal.     

Asymptotic analysis of the flow deviation method for the maximum concurrent flow problem

We analyze the asymptotic behavior of the Flow Deviation Method, first presented in 1971 by Fratta, Gerla and Kleinrock, and show that when applied to packing linear programs such as the maximum concurrent flow problem, it yields a fully polynomial-time approximation scheme. Received: December 28, 2000 / Accepted: May 25, 2001?Published online October 2, 2001     

A new strategy for the undirected two-commodity maximum flow problem

We address the two-commodity maximum flow problem on undirected networks. As a result of a change of variables, we introduce a new formulation that solves the problem through classical maximum flow techniques with only one-commodity. Therefore, a general strategy, based on this change of variables, is defined to deal with other undirected multi-commodity problems. Finally, we extend the single objective problem to a bicriteria environment. We show that the set of efficient solutions of the biobjective undirected two-commodity maximum flow problem is the set of alternative optimum solutions of the undirected two-commodity maximum flow problem. In addition, we prove that the set of efficient extreme points in the objective space has, at most, cardinality two.     

A simple GAP-canceling algorithm for the generalized maximum flow problem

We give a simple primal algorithm for the generalized maximum flow problem that repeatedly finds and cancels generalized augmenting paths (GAPs). We use ideas of Wallacher (A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms, 1991) to find GAPs that have a good trade-off between the gain of the GAP and the residual capacity of its arcs; our algorithm may be viewed as a special case of Wayne’s algorithm for the generalized minimum-cost circulation problem (Wayne in Math Oper Res 27:445–459, 2002). Most previous algorithms for the generalized maximum flow problem are dual-based; the few previous primal algorithms (including Wayne in Math Oper Res 27:445–459, 2002) require subroutines to test the feasibility of linear programs with two variables per inequality (TVPIs). We give an O(mn) time algorithm for finding negative-cost GAPs which can be used in place of the TVPI tester. This yields an algorithm with O(m log(mB/ε)) iterations of O(mn) time to compute an ε-optimal flow, or O(m ² log (mB)) iterations to compute an optimal flow, for an overall running time of O(m ³ nlog(mB)). The fastest known running time for this problem is , and is due to Radzik (Theor Comput Sci 312:75–97, 2004), building on earlier work of Goldfarb et al. (Math Oper Res 22:793–802, 1997). David P. Williamson is supported in part by an IBM Faculty Partnership Award and NSF grant CCF-0514628.     

Strongly polynomial dual simplex methods for the maximum flow problem

This paper presents dual network simplex algorithms that require at most 2nm pivots and O(n ² m) time for solving a maximum flow problem on a network ofn nodes andm arcs. Refined implementations of these algorithms and a related simplex variant that is not strictly speaking a dual simplex algorithm are shown to have a complexity of O(n ³). The algorithms are based on the concept of apreflow and depend upon the use of node labels that are underestimates of the distances from the nodes to the sink node in the extended residual graph associated with the current flow. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research was supported by NSF Grants DMS 91-06195, DMS 94-14438 and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.Research was supported by NSF Grant CDR 84-21402 at Columbia University.     

The inverse maximum dynamic flow problem

We consider the inverse maximum dynamic flow (IMDF) problem. IMDF problem can be described as: how to change the capacity vector of a dynamic network as little as possible so that a given feasible dynamic flow becomes a maximum dynamic flow. After discussing some characteristics of this problem, it is converted to a constrained minimum dynamic cut problem. Then an efficient algorithm which uses two maximum dynamic flow algorithms is proposed to solve the problem.     

On a continuous approach for the maximum weighted clique problem

This paper is focused on computational study of continuous approach for the maximum weighted clique problem. The problem is formulated as a continuous optimization problem with a nonconvex quadratic constraint given by the difference of two convex functions (d.c. function). The proposed approach consists of two main ingredients: a local search algorithm, which provides us with crucial points; and a procedure which is based on global optimality condition and which allows us to escape from such points. The efficiency of the proposed algorithm is illustrated by computational results.     

New solution approaches for the maximum-reliability stochastic network interdiction problem

We investigate methods to solve the maximum-reliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker’s probability of undetected traversal through the network. The attacker’s origin and destination are unknown to the defender and assumed to be random. SNIP can be formulated as a stochastic mixed-integer program via a deterministic equivalent formulation (DEF). As the size of this DEF makes it impractical for solving large instances, current approaches to solving SNIP rely on modifications of Benders decomposition. We present two new approaches to solve SNIP. First, we introduce a new DEF that is significantly more compact than the standard DEF. Second, we propose a new path-based formulation of SNIP. The number of constraints required to define this formulation grows exponentially with the size of the network, but the model can be solved via delayed constraint generation. We present valid inequalities for this path-based formulation which are dependent on the structure of the interdicted arc probabilities. We propose a branch-and-cut (BC) algorithm to solve this new SNIP formulation. Computational results demonstrate that directly solving the more compact SNIP formulation and this BC algorithm both provide an improvement over a state-of-the-art implementation of Benders decomposition for this problem.     

On the equivalence of the maximum balanced flow problem and the weighted minimax flow problem

We point out the equivalence of the maximum balanced flow problem of Minoux and the weighted minimax flow problem of Ichimori, Ishü and Nishida. Some generalizations of the two problems are also suggested.     

A Branch and Price algorithm for the k-splittable maximum flow problem

The Maximum Flow Problem with flow width constraints is an NP-hard problem. Two models are proposed: the first model is a compact node-arc model using two flow conservation blocks per path. For each path, one block defines the path while the other one sends the right amount of flow on it. The second model is an extended arc-path model, obtained from the first model after a Dantzig–Wolfe reformulation. It is an extended model as it relies on the set of all the paths between the source and the sink nodes. Some symmetry breaking constraints are used to improve the model. A Branch and Price algorithm is proposed to solve the problem. The column generation procedure reduces to the computation of a shortest path whose cost depends on weights on the arcs and on the path capacity. A polynomial-time algorithm is proposed to solve this subproblem. Computational results are shown on a set of medium-sized instances to show the effectiveness of our approach.     

On strongly polynomial dual simplex algorithms for the maximum flow problem

Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on ann-node,m-arc network in at most 2nm pivots and O(n ² m) time are presented. These rules are based on the concept of apreflow and depend upon the use of node labels which are either the lengths of a shortestpseudoaugmenting path from those nodes to the sink node orvalid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms. This research was supported in part by NSF Grants DMS 91-06195, DMS 94-14438, and CDR 84-21402 and DOE Grant DE-FG02-92ER25126.     

A capable neural network model for solving the maximum flow problem

This paper presents an optimization technique for solving a maximum flow problem arising in widespread applications in a variety of settings. On the basis of the Karush–Kuhn–Tucker (KKT) optimality conditions, a neural network model is constructed. The equilibrium point of the proposed neural network is then proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the maximum flow problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.     

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 strongly polynomial algorithm for the minimum maximum flow degree problem

Let us consider a network flow respecting arc capacities and flow conservation constraints. The flow degree of a node is sum of the flow entering and leaving it. We study the problem of determining a flow that minimizes the maximum flow degree of a node. We show how to solve it in strongly polynomial time with linear programming.     

Direct problem and inverse problem for the supersonic plane flow past a curved wedge

In this paper, we consider the isentropic irrotational steady plane flow past a curved wedge. First, for a uniform supersonic oncoming flow, we study the direct problem: For a given curved wedge y = f(x), how to globally determine the corresponding shock y = g(x) and the solution behind the shock? Then, we solve the corresponding inverse problem: How to globally determine the curved wedge y = f(x) under the hypothesis that the position of the shock y = g(x) and the uniform supersonic oncoming flow are given? This kind of problems plays an important role in the aviation industry. Under suitable assumptions, we obtain the global existence and uniqueness for both problems. Copyright © 2011 John Wiley & Sons, Ltd.     

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.