Skip to main content
4 votes
Accepted

Can one strengthen the Lagrangian dual bound in column generation when there are multiple subproblems?

Yes, that bound is valid, and you can prove it by exhibiting a dual feasible solution with that objective value. I don’t have my copy handy, but Wolsey’s Integer Programming shows this. In fact, the ...
RobPratt's user avatar
  • 32.7k
1 vote
Accepted

The dual values and change in the variables values

Let $\bar{A}$ and $\bar{x}$ be $A$ and $x$ augmented by slack variables, so that the constraints become $\bar{A} \bar{x} = b.$ The LP solution partitions $\bar{A} = [B N]$ (after permuting columns if ...
prubin's user avatar
  • 39.5k

Only top scored, non community-wiki answers of a minimum length are eligible