lower bound

[mgalati13]

Is there a way to calculate a lower bound on the objective value for CSP?

In the case of stopping on time or threshold early, this can be useful in the context of a column generation algorithm (like in VRPY).

In addition, this might allow you to stop early if you have a valid path that is as low as your lower bound.

[torressa]

I don't think I know how to pre-compute a lower bound. One is kept on the fly for label pruning. I keep lower bounds from the shortest path problem, however this is not always very useful. https://github.com/torressa/cspy/blob/beb3cb829f3932bf07bf3951eb82aeba5a560a5d/src/cc/search.h#L31 Would be really interested if you founds / came up with something!

[the-soomin-woo]

Hi @torressa,

On a related note, I am computing the RMP objective function value (with linear relaxation) and the lagrangian lower bound.

The blue curve is the RMP objective function value with linear relaxation. The orange curve is the dual objective function value, i.e., RMP objective function value with linear relaxation + the minimum reduced cost found in the iteration.

Note in the title of the figure, the "LB" is the RMP objective function value with linear relaxation, and the "UP" is the RMP objective function value without linear relaxation in the last iteration of the column generation. My column generation always ends by failing to find a route with a negative reduced cost.

Somehow, I can't seem to close the dual gap (for which I calculate (blue - orange ) / blue * 100%) The gap never converges 0 (it's always somewhere like 0.5 to 5% dual gap), although no route is found with a negative reduced cost.

Have you found this situation before? Do you know if this is supposed to happen with a network with >= 30 nodes?

Thank you!

ADDED: I realize that the graph doesn't show the last iteration of the column generation, where there is no negative reduced cost. This means the minimum of the reduced cost in the last iteration is greater than or equal to 0 (or is it equal to zero?) and that the RMP objective value = the Lagrangian. Do you agree?

[mgalati13]

Without branching - there is no guarantee that you will close the gap.

[the-soomin-woo]

Hi @mgalati13,

Do you mean 'without branching' as in the branch-bound-and-price branching? In that case, I don't agree but correct me if I'm wrong, please.

Column generation solves each subproblem at the branch and bound search tree, and it needs to close the gap between the RMP objective function (with linear relaxation) and the dual objective function to prove that it's solved at optimality. That's the only way you can get the lower bound at each branch and bound search tree. For a more detailed explanation, here's a great video.

As the tree goes 'deeper', the lower bound at each node can remain the same or get worse. But the fact that you find a lower bound at each node means that you're at zero duality gap. You need to close the duality gap at each node - no matter how many bounding constraints you have.

If you use the exact algorithm (such as the labeling algorithm in cspy), you will close the gap in theory although it might take a while.

But please explain, why is there no guarantee that you will close the gap? Thank you.

[mgalati13]

I was assuming you were only doing the root node of branch-and-price. Yes, if you do full branch-and-price correctly, it should yield 0% gap eventually. How are you enforcing the branching? Note, I am talking about the integer gap. There is also the continuous gap in each B&B node.

As for your added comment, the bound is the RMP objective + the bounds from the subproblems. So, if you find no negative reduced cost columns, ignoring numeric issues, then the bounds from the subproblems should be 0, and you will have a 0% continuous gap.

As for your comment about "you need to close the duality gap at each node". No - you do not need to do that. You just need a valid bound and then you can branch.

[the-soomin-woo]

Hello @mgalati13! Yes, thank you for your feedback! Hope to solve this branch and bound algorithm well :)

[mgalati13]

Without branching - there is no guarantee that you will close the gap.

On Mar 10, 2022, at 7:39 PM, soomin-woo @.***> wrote:

 Hi @torressa,

On a related note, I am computing the RMP objective function value (with linear relaxation) and the lagrangian lower bound.

The blue curve is the RMP objective function value with linear relaxation. The orange curve is the RMP objective function value with linear relaxation + the minimum reduced cost found in the iteration.

Note in the title of the figure, the "LB" is the RMP objective function value with linear relaxation, and the "UP" is the RMP objective function value without linear relaxation in the last iteration of the column generation. I always end the column generation by failing to find a route with a negative reduced cost.

Somehow, I can't seem to close the dual gap. The gap never converge 0 (it's always somewhere like 0.5 to 5% dual gap), although no route is found with a negative reduced cost.

Have you found this situation before? Do you know if this is supposed to happen with a network with >= 30 nodes?

Thank you!

— Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you authored the thread.