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

Consider a Linear Programme (LP) \begin{align} \min && \sum_{i \in I} c_i x_i \\ \text{s.t.} && \sum_{i \in I} a_{ij} x_i &\geq b_j & \quad & \forall j \in J \\ && x_i &\geq 0 & \quad & \forall i \in I \end{align}

Assume you are solving this problem via column generation. Let $$z$$ be the value of the optimal solution of the reduced problem (RLP), i.e., the problem obtained when only considering a subset of the variables, $$I' \subsetneq I$$. Let $$\bar{c}$$ be the lowest reduced cost of a variable of $$I' \setminus I$$ (i.e., which is not yet in RLP). Note that $$\bar{c} < 0$$ unless we are at the optimum. Finally, assume that a convexity constraint $$\sum_{i \in I} x_i \leq U$$ holds.

The Lagrangian bound is a dual bound on the value of the optimum $$z^*$$ of LP and states that it cannot be improved by more than $$U$$ times $$\bar{c}$$, i.e., $$$$z + U \cdot \bar{c} \leq z^* \leq z$$$$

Now assume that the set of variables can be partitioned as $$I = I_1 \cup \ldots \cup I_k$$ and that new variables can be priced solving $$k$$ independent subproblems. Further assume that we have $$k$$ convexity constraints $$$$\sum_{i \in I_\ell} x_i \leq U_\ell \quad \forall \ell \in \{1, \ldots, k\}$$$$ Denote with $$\bar{c}_\ell$$ the lowest reduced cost given by pricing subproblem $$\ell$$, i.e., the lowest reduced cost of a variable in $$I_\ell \setminus I'$$. Is it true that the following is a valid bound? $$$$z + \sum_{\ell = 1}^k U_\ell \cdot \bar{c}_\ell \leq z^* \leq z$$$$

• Note that traditionally $i$ corresponds to constraints (rows) and $j$ corresponds to variables (columns), the opposite of what you used. Aug 8, 2023 at 11:07

## 1 Answer

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 bound is still valid even if $$\bar{c}_\ell$$ is only a lower bound on the objective value of subproblem $$\ell$$. That is, you can obtain a valid bound even if you stop solving a subproblem early, as is common when the subproblem is MILP instead of LP.

• Another common situation when one has a lower bound on the objective value of the subproblem occurs in routing. If you solve the SP via labelling, state space relaxation provides a lower bound. Aug 9, 2023 at 1:37