Inhalt des Dokuments
Preprint 42-2003
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Dual Variable Based Fathoming in Dynamic Programs for Column Generation
- Author
- Publication
- Appears in European J. Oper. Res.
- Classification
-
MSC: primary: 90C39 Dynamic programming secondary: 90C08 Special problems of linear programming 65K05 Mathematical programming algorithms - Keywords
-
Dynamic programming, column generation, state space reduction
- Abstract
-
In this note, we aim at reducing the state space of dynamic programming algorithms used as column generators in solving the linear programming relaxation of set partitioning problems arising from practical applications. We propose a simple generic lower bounding criterion based on the respective dual optimal solution of the restricted master program.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe