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

Question

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}

Answer 1

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.