The biobjective undirected two-commodity minimum cost flow problem

We address the two-commodity minimum cost flow problem considering two objectives. We show that the biobjective undirected two-commodity minimum cost flow problem can be split into two standard biobjective minimum cost flow problems using the change of variables approach. This technique allows us to develop a method that finds all the efficient extreme points in the objective space for the two-commodity problem solving two biobjective minimum cost flow problems. In other words, we generalize the Hu's theorem for the biobjective undirected two-commodity minimum cost flow problem. In addition, we develop a parametric network simplex method to solve the biobjective problem.     

A polynomial time approximation algorithm for the two-commodity splittable flow problem

We consider a generalization of the unsplittable maximum two-commodity flow problem on undirected graphs where each commodity ${i \in \{1, 2\}}$ can be split into a bounded number k _i of equally-sized chunks that can be routed on different paths. We show that in contrast to the single-commodity case this problem is NP-hard, and hard to approximate to within a factor of α > 1/2. We present a polynomial time 1/2-approximation algorithm for the case of uniform chunk size over both commodities and show that for even k _i and a mild cut condition it can be modified to yield an exact method. The uniform case can be used to derive a 1/4-approximation for the maximum concurrent (k ₁, k ₂)-splittable flow without chunk size restrictions for fixed demand ratios.     

An exact algorithm for the maximum k-club problem in an undirected graph

In this paper, we prove that the maximum k-club problem (MkCP) defined on an undirected graph is NP-hard. We also give an integer programming formulation for this problem as well as an exact branch-and-bound algorithm and computational results on instances involving up to 200 vertices. Instances defined on very dense graphs can be solved to optimality within insignificant computing times. When k=2, the most difficult cases appear to be those where the graph density is around 0.15.     

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.     

A successful algorithm for the undirected Hamiltonian path problem

In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes. It first reintroduces the concept described in [13] and then explains the algorithm. Computational comparison with the algorithm by Posa [10] is given.It is shown that a Hamiltonian Path is a spanning arborescence with zero ramification index. Given an undirected graph, the Minram algorithm starts by finding a spanning tree which defines a unique spanning arborescence. By suitable pivots it locates a locally minimal value of the ramification index. If this local minima corresponds to zero ramification index then the algorithm is considered to have ended successfully, else a failure is reported.Computational performance of the algorithm on randomly generated Hamiltonian graphs is given. The random graphs used as test problems were generated using the procedure explained in Section 6.1. Comparison with our version of the Posa algorithm which we call Posa-ran algorithm [10] is also made.     

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.     

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.     

A new trust region technique for the maximum weight clique problem

A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of other stationary points of the program. We formulate and prove a condition when a Motzkin-Straus optimum coincides with such a point. The developed method has complexity O(n³), where n is the number of vertices of the graph. It was implemented in a publicly available software package QUALEX-MS.Computational experiments indicate that the algorithm is exact on small graphs and very efficient on the DIMACS benchmark graphs and various random maximum weight clique problem instances.     

A maximum flow problem with intermediate node requirements

The conventional Maximum flow problem is modified to take account of possible requirements at intermediate nodes across which flow takes place. This is achieved by incorporating pseudo or priority arcs to act as thresholds controlling out-flow from the nodes and modifying the Ford and Fulkerson algorithm to take account of these thresholds. Effect of introducing these threshold-requirements at intermediate nodes on the final flow into the sink in the network is examined by some numerical examples.     

Cutting plane approach for the maximum flow interdiction problem

The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.     

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     

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.     

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.     

A maximum problem for matrices

The following maximum problem is considered: To find among all contractions T on an n-dimensional Hilbert space whose spectral radius does not exceed a given number p< 1, the operator T for which |Tⁿ| is maximum. A matrix T of Toeplitz type is constructed for which this maximum is attained.     

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.     

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.