ALCOMFT-TR-02-134

Meinolf Sellmann, Georg Kliewer and Achim Koberstein
Capacitated Network Design - Cardinality Cuts and Coupled Variable Fixing Algorithms based on Lagrangian Relaxations
Paderborn. Work packages 2 and 3. June 2002.

Abstract: We present a branch-and-bound approach for the Capacitated Network Design Problem. We focus on tightening strategies such as variable fixing and local cuts that can be applied in every search node. Different variable fixing algorithms based on Lagrangian relaxations are evaluated solitarily and in combined versions. Moreover, we develop cardinality cuts for the problem and evaluate their usefulness empirically by numerous tests.

Postscript file: ALCOMFT-TR-02-134.ps.gz (83 kb).