A faster capacity scaling algorithm for minimum cost submodular flow

We describe an O(n ⁴ hmin{logU,n ²logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow. Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001     

A polynomial cycle canceling algorithm for submodular flows

Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems, Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems. Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999     

A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

A note on Faigle and Kern’s dual greedy polyhedra

U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella and have shown that a dual greedy algorithm works for a system of linear inequalities with {:0,1}-coefficients defined in terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional condition on the submodular function.?In this note we show that Faigle and Kern’s dual greedy polyhedra belong to a class of submodular flow polyhedra, i.e., Faigle and Kern’s problem is a special case of the submodular flow problem that can easily be solved by their greedy algorithm. Received: February 1999 / Accepted: December 1999?Published online February 23, 2000     

A fast algorithm for minimum weight odd circuits and cuts in planar graphs

We give a simple algorithm for finding a minimum weight odd circuit in planar graphs. By geometric duality, the same algorithm can be used to find minimum weight odd cuts. For general sparse graphs, the fastest known algorithms for these two problems take time and time, respectively.     

Parallel and fast sequential algorithms for undirected edge connectivity augmentation

1 ,E₂,..., such that ⋃_i≤τE_i optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all E_i are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs. Received November 1995 / Revised version received July 1998 Published online March 16, 1999     

A .699-approximation algorithm for Max-Bisection

We present a .699-approximation algorithm for Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson. Received: October 1999 / Accepted: July 2000?Published online January 17, 2001     

A polynomial dual simplex algorithm for the generalized circulation problem

This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation of this algorithm is given that has a worst-case running time of O(m ²(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized circulation problem. Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001     

A branch and cut algorithm for nonconvex quadratically constrained quadratic programming

We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality. Received December 19, 1997 / Revised version received July 26, 1999?Published online November 9, 1999     

A branch-and-cut algorithm for capacitated network design problems

We present a branch-and-cut algorithm to solve capacitated network design problems. Given a capacitated network and point-to-point traffic demands, the objective is to install more capacity on the edges of the network and route traffic simultaneously, so that the overall cost is minimized. We study a mixed-integer programming formulation of the problem and identify some new facet defining inequalities. These inequalities, together with other known combinatorial and mixed-integer rounding inequalities, are used as cutting planes. To choose the branching variable, we use a new rule called “knapsack branching”. We also report on our computational experience using real-life data. Received April 29, 1997 / Revised version received January 9, 1999? Published online June 28, 1999     

Optimization via enumeration: a new algorithm for the Max Cut Problem

We present a polynomial time algorithm to find the maximum weight of an edge-cut in graphs embeddable on an arbitrary orientable surface, with integral weights bounded in the absolute value by a polynomial of the size of the graph.</ The algorithm has been implemented for toroidal grids using modular arithmetics and the generalized nested dissection method. The applications in statistical physics are discussed. Received: June 1999 / Accepted: December 2000?Published online March 22, 2001     

A branch-and-cut algorithm for the Undirected Rural Postman Problem

The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported. Received: December 1, 1997 / Accepted: October 13, 1999?Published online January 27, 2000     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

On a homogeneous algorithm for the monotone complementarity problem

Received May 15, 1995 / Revised version received May 20, 1998 Published online October 21, 1998     

On the complexity of a class of combinatorial optimization problems with uncertainty

We consider a robust (minmax-regret) version of the problem of selecting p elements of minimum total weight out of a set of m elements with uncertainty in weights of the elements. We present a polynomial algorithm with the order of complexity O((min {p,m-p})² m) for the case where uncertainty is represented by means of interval estimates for the weights. We show that the problem is NP-hard in the case of an arbitrary finite set of possible scenarios, even if there are only two possible scenarios. This is the first known example of a robust combinatorial optimization problem that is NP-hard in the case of scenario-represented uncertainty but is polynomially solvable in the case of the interval representation of uncertainty. Received: July 1998 / Accepted: May 2000?Published online March 22, 2001     

A cutting plane algorithm for the General Routing Problem

The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it is capable of providing very strong lower bounds and, in most cases, optimal solutions. Received: November 1998 / Accepted: September 2000?Published online March 22, 2001     

A BFGS-IP algorithm for solving strongly convex optimization problems with feasibility enforced by an exact penalty approach

This paper introduces and analyses a new algorithm for minimizing a convex function subject to a finite number of convex inequality constraints. It is assumed that the Lagrangian of the problem is strongly convex. The algorithm combines interior point methods for dealing with the inequality constraints and quasi-Newton techniques for accelerating the convergence. Feasibility of the iterates is progressively enforced thanks to shift variables and an exact penalty approach. Global and q-superlinear convergence is obtained for a fixed penalty parameter; global convergence to the analytic center of the optimal set is ensured when the barrier parameter tends to zero, provided strict complementarity holds. Received: December 21, 2000 / Accepted: July 13, 2001?Published online February 14, 2002