Groupe d’études et de recherche en analyse des décisions

The Column Generation Improvement Heuristic (CGI)

Marcus V.S. Poggi De Aragao Pontifícia Universidade Católica do Rio de Janeiro, Brésil

One may propose column generation formulations for combinatorial problems where the pricing subproblem turns out to be another, although identical sometimes, instance of the original problem. When it is not, we point out that finding a profitable new solution for the subproblem implies an improvement on the current (LP) solution. We discuss this instance repetition behavior over applications of CGI to routing problems and nonlinear 0-1 programs (UBQP, MAX-CUT, MAX-CLIQUE). We explore the consequences of this embedded instance transformation in branch-and-price approaches where problem solutions are associated to single columns. Uniting implications on variables coming from different related instances is the current challenge.