High performance algorithms for set covering-like optimization problems with many variables

covering constraints and with many variables appear in a number of
applications. The work presented here was originally intended for
crew scheduling problems which are important tasks faced by airlines
and railways. A possible future application could be the multiple
sequence alignment problem from computational biology. Although these
problems are NP-hard, high quality approximations can be achieved in
practice with an iterative lagrangian based algorithm developed at
Chalmers University in Gothenburgh. The talk surveys approaches to
adapt to the memory hierarchy of modern workstations, to solve the
problem in parallel and to reduce the overall work to be done.