Some question on column generation, branch and price, Coluna

[WalterMadelim]

Since I’m studying this topic recently. I wonder if there is anyone who is interested and can hence discuss with me.

Benders

I don’t think this structure is going to be handled by Benders decomposition.
For this structure, a more appropriate method is still Dantzig-Wolfe decomposition, if you add copy variables and copy constraints and then relax all complicating constraints to achieve blockwise decomposition.

Diving heuristic

As it is known that branch-and-bound becomes slow and hard, in practical applications we may not have enough time to exactly conduct a branch-and-price algorithm. Therefore some heuristics are entailed. I’m interested in this diving heuristic marked below

Could anyone offer some more details about this?

[odow]

The picture on the slide is correct. I suggest you look up some standard textbook about Benders.

You should also seach for “diving” in the context of solving a MIP and the branch and bound tree.

[WalterMadelim]

@odow

The picture on the slide is correct

You’re right. I misunderstood.

So Dual decomposition and Benders decomposition has their own fields of application.

Suppose we have a large number of blocks (say, N), and we have a small number of non-block shared variables (say, n). e.g. n = 3 while N = 10000. If the n variables are referred to in the constraints within all N blocks, then Benders decomposition is the fitting method. On the other hand, if a small number (n) of non-block constraints must be satisfied by the variables from within all N blocks, then Dual decomposition is the fitting method.

---

I noticed that in the slide above from JuMP-dev 2020, nested decomposition is mentioned. Personally I don’t think that is realistic, since the current Master-Subproblem two-layer structure is already very hard for large scale problems so that we aren’t prepared to handle the case Master-Middle-Subproblem three-layer nested formulation.

Instead, I think the following pairwise coupling case might worth more attention, this case is supposed to be a bit (or a lot?) harder than the single point of coupling cases discussed above.

(this image itself is ready to be solved by Dual decomposition. If you lean your head towards your left shoulder by 90 degrees, then the problem corresponding to the image you see is ready to be solved by Benders decomposition. The complexity can be tuned up by lengthening the orange blocks, which indicates denser coupling.)

The reason that pairwise coupling is harder is:
The coupling size is O(N), compared to O(1) in the single point of coupling case, where N represents the number of blocks.