Title
Dual Variable Based Fathoming in Dynamic Programs for
Column Generation
Author
-
Publication
Appears in European J. Oper. Res.
Source
-
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
-
-
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.
