Combining column generation and metaheuristics

Abstract

In this Chapter, we consider the hybridization of column generation (CG) with metaheuristics (MHs) for solving combinatorial optimization problems. We describe a general framework entitled ”metaheuristic search by column generation” (for short, SearchCol). CG is a decomposition approach in which one linear programming master problem interacts with subproblems to obtain an optimal solution to a relaxed version of a problem. The subproblems may be solved by problem specific algorithms. After CG is applied, a set of subproblems solutions, optimal primal and dual values of the master problem variables and a lower bound to the optimal value of problem are available. In contrast with enumerative approaches (e.g, branch-and-price), in SearchCol the information provided by CG is used in a MH search. The search is based on representing a solution (to the overall problem) as being composed by one solution from each subproblem. After a search is conducted, a perturbation for CG is defined and a new iteration begins. The perturbation consists in forcing or forbidding attributes of the subproblems solutions and, in general, leads to the generation of new subproblems solutions and different optimal primal and dual values of the master problem variables. In this Chapter, we discuss (i) which models are suitable for decomposition approaches as SearchCol, (ii) different alternatives for generating initial solutions for the search (with different degrees of randomization, greediness and influence of CG) (iii) different search approaches based on local search, (iv) different alternatives for perturbing CG (influenced by CG, based on the incumbent, and based on the memory of the search).