# 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., $$\begin{equation} z + U \cdot \bar{c} \leq z^* \leq z \end{equation}$$

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 $$\begin{equation} \sum_{i \in I_\ell} x_i \leq U_\ell \quad \forall \ell \in \{1, \ldots, k\} \end{equation}$$ 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? $$\begin{equation} z + \sum_{\ell = 1}^k U_\ell \cdot \bar{c}_\ell \leq z^* \leq z \end{equation}$$

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

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.