14
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Would you see Vehicle Routing instance using SCIP? Or the column generation textbook? they may be interesting. $\endgroup$
    – A.Omidi
    Dec 16, 2019 at 8:59

2 Answers 2

Reset to default
11
$\begingroup$

You are right. If you solve the pricing heuristically, you do not have a valid lower bound.

One approach to obtain a lower bound would be to solve a relaxation of the pricing problem exactly. Usually, the faster a relaxation can be solved, the worse in the resulting bound.

Another (but still similar) approach is to calculate a lower bound on the pricing solution value. The Lagrangian lower bound then can be calculated. You can check the "Lagrangian duality" chapter 10 of the Laurence Wolsey "Integer Programming" book: https://www.wiley.com/en-us/Integer+Programming-p-9780471283669, or some other textbook on Lagrangian duality in Integer Programming.

It is not needed to calculate the lower bound in every iteration of column generation. The best would be to converge using a heuristic pricing and calculate the lower bound in the last column generation iteration, or in several last iterations.

To calculate the gap, you need also upper bounds. For large instances, I recommend to use more conventional VRP heuristics, like local search, genetic algorithm, etc.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your help. I liked the idea of generating columns heuristically and then using and exact method to solve the pricing subproblem. In that regard, consider this heuristic method: 1. generate an initial solution heuristically; 2. using the dual variables, generate more columns heuristically during a fixed number of iterations; 3. solve the subproblem exactly to obtain a lower bound from the linear relaxation; 4. get a solution by solving a MIP with the final set of columns. Is the calculated lower bound valid for assessing our solution, given that we didn't use branch-and-price? $\endgroup$
    – vulpith
    Dec 18, 2019 at 0:41
  • $\begingroup$ Yes, the bound is valid. Note that solving the subproblem exactly even in a single col.gen. iteration can be very time consuming for large instances, especially if route elementarity constraint is imposed (this constraint can be relaxed to speed-up the solution of the subproblem at the expense of having worse bound). Initial heuristic solution does not usually help much to speed-up the convergence of column generation. Artificial variables with high cost can also be used to initialize the master problem. A typical gap obtained by column generation for vehicle routing problems is 2-3%. $\endgroup$
    – Ruslan Sadykov
    Dec 18, 2019 at 9:21
8
$\begingroup$

Even if you solve the pricing heuristically, you can still obtain a valid lower bound in certain cases. However, it depends on your pricing heuristic whether this is possible.

You have found the optimal solution to the linear relaxation of the master problem if there are no more columns with negative reduced costs. Suppose you have a heuristic that always underestimates the reduced cost of a column and according to this heuristic all columns have positive reduced costs. Then, the current solution is optimal and hence a valid lower bound. If instead, your heuristic always overestimates the reduced cost of a column, it is possible to miss negative reduced cost columns so the solution is not a valid lower bound, even when the heuristic cannot find new columns to be added.

In case you have a heuristic that overestimates reduced costs, people will often first try to find negative reduced costs columns using the heuristic. Once the heuristic fails to find new columns, they switch to an exact pricing method to still find the correct lower bound. I can recommend the book Column Generation. You may also consider this question on OR.SE.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.