Group for Research in Decision Analysis

G-2020-36

Stabilized column generation via the dynamic separation of aggregated rows

, , , and

Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely: vehicle routing with time windows, bin packing with conflicts, and multi-person pose estimation. Computational experiments show significant improvements in terms of CPU time and number of iterations when compared to a standard CG algorithm.

, 36 pages