Lectures and Colloquia during the semester

Technische Universität Berlin

Straße des 17. Juni 136, 10623 Berlin

Math building - Room MA 042

*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)

[top]