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 note on the minimum interval cost flow problem

We reduce the problem of minimum interval cost flow problem (MICFP) introduced by Hashemi et al. (2006) to the well-known minimum cost flow problem (MCFP).     

Parallel primal-dual methods for the minimum cost flow problem

In this paper we discuss the parallel asynchronous implementation of the classical primaldual method for solving the linear minimum cost network flow problem. Multiple augmentations and price rises are simultaneously attempted starting from several nodes with possibly outdated price and flow information. The results are then merged asynchronously subject to rather weak compatibility conditions. We show that this algorithm is valid, terminating finitely to an optimal solution. We also present computational results using an Encore MULTIMAX that illustrate the speedup that can be obtained by parallel implementation.This work supported in part by the BM/C3 Technology branch of the United States Army Strategic Defense Command.     

The biobjective absolute center problem

This paper deals with the problem of determining the absolute center of a network, taking into account two objective functions. These functions consist of minimizing the maximum of the distances from any point on the network to the vertices, using two independent lengths on each edge. We propose an algorithm in polynomial time to obtain the non-dominated location points on the network, using the Kariv and Hakimi method (1979). This work was partially supported by project number 93/108 from the Dirección General de Universidades e Investigación del Gobierno de Canarias.     

The biobjective travelling purchaser problem

The purpose of this article is to present and solve the Biobjective Travelling Purchaser Problem, which consists in determining a route through a subset of markets in order to collect a set of products, minimizing the travel distance and the purchasing cost simultaneously. The most convenient purchase of the product in the visited markets is easily computed once the route has been determined. Therefore, this problem contains a finite set of solutions (one for each route) and the problem belongs to the field of the Biobjective Combinatorial Optimization. It is here formulated as a Biobjective Mixed Integer Linear Programming model with an exponential number of valid inequalities, and this model is used within a cutting plane algorithm to generate the set of all supported and non-supported efficient points in the objective space. A variant of the algorithm computes only supported efficient points. For each efficient point in the objective space exactly one Pareto optimal solution in the decision space is computed by solving a single-objective problem. Each of these single-objective problems, in turn, is solved by a specific branch-and-cut approach. A heuristic improvement based on saving previously generated cuts in a common cut-pool structure has also been developed with the aim of speeding up the algorithm performance. Results based on benchmark instances from literature show that the common cut-pool heuristic is very useful, and that the proposed algorithm manages to solve instances containing up to 100 markets and 200 different products. The general procedure can be extended to address other biobjective combinatorial optimization problems whenever a branch-and-cut algorithm is available to solve a single-objective linear combination of these criteria.     

A generic auction algorithm for the minimum cost network flow problem

In this paper we broadly generalize the assignment auction algorithm to solve linear minimum cost network flow problems. We introduce a generic algorithm, which contains as special cases a number of known algorithms, including the -relaxation method, and the auction algorithm for assignment and for transportation problems. The generic algorithm can serve as a broadly useful framework for the development and the complexity analysis of specialized auction algorithms that exploit the structure of particular network problems. Using this framework, we develop and analyze two new algorithms, an algorithm for general minimum cost flow problems, called network auction, and an algorithm for thek node-disjoint shortest path 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.     

Time-varying minimum cost flow problems

In this paper, we study a minimum cost flow problem on a time-varying network. Let N(V,A,l,b,c_r,c_w) be a network with an arc set A and a vertex set V. Each a∈A is associated with three integer parameters: a positive transit time b(a,t), an arbitrary transit cost c_r(a,t), and a positive capacity limit l(a,t). Each x∈V is associated with two integer parameters: a waiting cost c_w(x,t) and a vertex capacity l(x,t). All these parameters are functions of the discrete time t=0,1,2,… The objective is to find an optimal schedule to send a flow from the origin (the source vertex) to its destination (the sink vertex) with the minimum cost, subject to the constraint that the flow must arrive at the destination before a deadline T. Three versions of the problem are examined, which are classified depending on whether waiting at the intermediate vertices of the network is strictly prohibited, arbitrarily allowed, or bounded. Three algorithms with pseudopolynomial time complexity are proposed, which can find optimal solutions to the three versions of the problem, respectively.     

Inverse minimum flow problem

In this paper we consider the inverse minimum flow (ImF) problem, where lower and upper bounds for the flow must be changed as little as possible so that a given feasible flow becomes a minimum flow. A linear time and space method to decide if the problem has solution is presented. Strongly and weakly polynomial algorithms for solving the ImF problem are proposed. Some particular cases are studied and a numerical example is given.     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

The complexity of a minimum reload cost diameter problem

We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P=NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85].     

On dual minimum cost flow algorithms

We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general problems (like submodular flow) and is likely to be more efficient in practice.  Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running time of our algorithm by a factor of n.     

The problem of the optimal biobjective spanning tree

This paper studies the problem of finding the set of optimal spanning trees of a connected graph, considering two cost functions defined on the set of edges. This problem is NP-hard and the solution is described through an algorithm that builds the family of efficient trees. This algorithm needs two procedures that solve the following uniobjective problems: the construction of all the spanning trees of a connected graph and the construction of the whole set of minimum cost spanning trees. The computational results obtained are shown in Section 5.     

A bad network problem for the simplex method and other minimum cost flow algorithms

For any integern, a modified transportation problem with 2n + 2 nodes is constructed which requires 2 ⁿ + 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.     

The minimum cost flow problem: A unifying approach to dual algorithms and a new tree-search algorithm

This paper is concerned with the minimum cost flow problem. It is shown that the class of dual algorithms which solve this problem consists of different variants of a common general algorithm. We develop a new variant which is, in fact, a new form of the ‘primal-dual algorithm’ and which has several interesting properties. It uses, explicitly only dual variables. The slope of the change in the (dual) objective is monotone. The bound on the maximum number of iterations to solve a problem with integral bounds on the flow is better than bounds for other algorithms. This paper is part of the author's doctoral dissertation submitted at Yale University.     

The relax codes for linear minimum cost network flow problems

We describe a relaxation algorithm [1,2] for solving the classical minimum cost network flow problem. Our implementation is compared with mature state-of-the-art primal simplex and primal-dual codes and is found to be several times faster on all types of randomly generated network flow problems. Furthermore, the speed-up factor increases with problem dimension. The codes, called RELAX-II and RELAXT-II, have a facility for efficient reoptimization and sensitivity analysis, and are in the public domain.This work has been supported by the National Science Foundation under Grant NSF-ECS-8217668.     

Geometric algorithms for the minimum cost assignment problem

We consider the minimum-cost λ-assignment problem, which is equivalent to the minimum-weight one-to-many matching problem on a complete bipartite graph Γ = (A, B), where A and B have n and k nodes (n ? k), respectively. Formulating the problem geometrically, we given an O(kn + k^2.5n^0.5 log^1.5 n) time randomized algorithm, which is better than the existing O(kn² + n² log n) time algorithm if n > k log k.     

The undirected two disjoint shortest paths problem

The $k$ disjoint shortest paths problem ($k$-DSPP) on a graph with $k$ source–sink pairs $(s_i,t_i)$ asks if there exist $k$ pairwise edge- or vertex-disjoint shortest $s_i$–$t_i$-paths. It is known to be NP-complete if $k$ is part of the input. Restricting to $2$-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for $2$-DSPP on undirected graphs with non-negative edge lengths.