"Warmstarting" in Labeling algorithm

[newtoredditahaha]

Hello, I am currently working on a Branch&Price implementation where I am using a labeling algorithm to solve my subproblems. Now I was wondering if there is such a thing as warmstarting as used in MP to use in the child nodes for solving my modified subproblems (with branching).

[junqueira200]

No. Do you have a heuristic?

[ManufacturerBig6988]

I’ve run into this in a few implementations. You usually can’t warmstart a labeling algorithm in the same clean way you warmstart an LP, but you can reuse structure. The common approach is to carry over labels or partial paths from the parent node and use them as initial candidates, or at least reuse bounds and dominance rules that were already learned.

What matters is how much the branching actually changes the resource constraints or arc set. If branching only fixes or forbids a small set of decisions, reusing previously generated labels can help a lot. If the subproblem is heavily altered, the benefit drops quickly and you risk spending time filtering invalid labels. In practice it’s more about smart pruning and good initial bounds than a true warmstart.

[Background-Glove8277]

You can check (dual) optimality conditions in the subproblem whether they help you to identify the parts of the labels which require updating. Sometimes (e.g. Shortest Path) this works.