search

jomavera / branchAndPriceVRP

Test on how to implement Branch and Price for VRP with Gurobi (work in progress)
24 stars 8 forks source link

Is tree structure and pruning necessary? #4

Open Lsc12358 opened 9 months ago

Lsc12358 commented 9 months ago

Hi, jomavera

Thank you very much for the code, but I have some questions. In some textbooks on branch pricing algorithms, it seems that the nodes are stored in a tree structure and pruned using upper and lower bounds. In your algorithm, priority queue is used and there seems to be no upper bound and pruning logic, are both correct?

Looking forward to your recovery, thank you very much!

jomavera commented 9 months ago

Hi, what you describe seems like Branch and Bound algorithm where you keep upper and lower bounds. In Branch and Price you have a Restricted Master Problem (RMP) where you keep adding columns or branching depending if the solution of the RMP is integral or not.