Abstract: We introduce an algorithm that solves the maximum flow problem without generating flows explicitly. The algorithm solves directly a problem we call the maximum s-excess problem. That problem is equivalent to the minimum cut problem, and is a direct extension of the maximum closure problem. A new certificate of optimality and a novel solution approach were influenced by the work of Lerchs and Grossmann, 1964, on the maximum closure problem. The concepts used also lead to a new parametric analysis algorithm generating all breakpoints in the amount of time of a single run.
The complexities of the pseudoflow algorithm, and the parametric analysis pseudoflow algorithm are O(mn log n) on a graph with n nodes and m arcs. The amount of time required for the generation of maximum flow, once the maximum s-excess solution is available, is O(m log n).
The pseudoflow algorithm leads to a pseudoflow-simplex algorithm that solves the maximum s-excess problem and has the best complexity known for parametric analysis using simplex. It can be used to solved the minimum cost network flow problem and several other related problems as well.
The pseudoflow algorithm is flexible and can start from any initial solution. This makes it particularly useful as a "warm start" algorithm for sensitivity analysis or within Lagrangean relaxation or branch and bound procedures applied to integer programming problems.
Colloquium - 16:00
Abstract: This talk addresses a Lagrangian relaxation approach to a very general class of scheduling problems. The Lagrangian relaxation is a scheduling problem with start-time dependent costs, and it turns out that this problem reduces to a minimum cut problem in a directed graph.
To compute lower bounds on the optimum objective value of precedence- and resource-constrained scheduling problems via Lagrangian relaxation, a standard subgradient optimization can be used. In its core, this algorithm repeatedly solves minimum cut problems on the same graph with varying arc capacities.
In fact, this approach provides reasonable strong lower bounds in moderate computation times, and its efficiency is strongly correlated to the used minimum cut algorithm. In addition to the lower bound computation, the dual information from solutions of the Lagrangian relaxations can be used to obtain feasible solutions as well.
(Based on joint work with R. H. Möhring, A. S. Schulz, and F. Stork)