2
$\begingroup$

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}

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

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 9, 2023 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.