I'm starting to read about column generation-based approaches to vehicle routing problems (VRP). Let's say that I want to solve very large instances of an intricate VRP, I'm not looking to always solve my problem to optimality, but I still want to estimate valid optimality gaps for my solutions. Please, allow me to ask you two questions in this regard.
Let's say that I implement a column generation-based approach where the pricing subproblem is always solved heuristically (because we are dealing with a very large and intricate problem); however, the pricing method still finds columns that are added to the master problem at each iteration. My first question is, can I still calculate valid lower bounds (for a minimization problem) if I opt for using such a heuristic pricing method? If so, how can I do it? correct me if I'm wrong, but as far as I know, when the subproblem is not solved to optimality, like in this case, we don't longer obtain a valid lower bound by solving the linear relaxation of the master problem. So, I wonder if it is possible at least to estimate a lower bound.
I think that the method I just described is a hybrid exact-heuristic approach based on column generation, still I don't know if it can provide lower bounds for the solutions. So, my second question is, are you aware of alternative hybrid exact-heuristic approaches that can solve a given problem heuristically, while providing optimality gaps of the solutions?
Thank you very much, I would highly appreciate if you can provide me with some references to guide my research. Kind regards.