Optimality gap between a joint linear program and decoupled sub programs

Question

Let $\mathbf{c}_i,\mathbf{s}_i$ be given entry-wise positive $n\times 1$ vectors for $i\in[1,\dots,d]$. Let $\tau, \alpha_1,\dots, \alpha_d$ be given positive constants. Consider the linear programming problem to find vectors $\mathbf{x}_1,\dots,\mathbf{x}_d$ for the joint optimization problem \begin{align} \max_{\mathbf{x}_i,\forall i\in[1,\dots,d]}~\sum_{i=1}^{d}\mathbf{c}_i^T\mathbf{x}_i \\ s.t.~~&\sum_{i=1}^{d}\left(\mathbf{s}_i-\tau\mathbf{c}_i\right)^{T}\mathbf{x}_i \leq 0,\\ &\mathbf{s}_i^T\mathbf{x}_i\leq \alpha_i~,~\forall i \in[1,\dots,d] \\ &\mathbf{1}^T\mathbf{x}_i\leq 1~,~\mathbf{x}_i\geq \mathbf{0} \end{align} where $\mathbf{1}$ is the all-ones vector.

Due to the hardware/resource limitations we have, we need to resort to (assume this limitation is non-negotiable) solving a set of $d$ linear optimization problems which is somewhat a decoupled form of the original. Essentially, we solve for each $\mathbf{x}_i$ using the optimization problem \begin{align} \max_{\mathbf{x}_i}~\mathbf{c}_i^T\mathbf{x}_i \\ s.t.~~&\left(\mathbf{s}_i-\tau\mathbf{c}_i\right)^{T}\mathbf{x}_i \leq 0,\\ &\mathbf{s}_i^T\mathbf{x}_i\leq \alpha_i \\ &\mathbf{1}^T\mathbf{x}_i\leq 1~,~\mathbf{x}_i\geq \mathbf{0} \end{align} Our engineering solution now is to use the sub-optimal solutions $\mathbf{x}_1,\dots,\mathbf{x}_d$ from the decoupled sub problems as the solution to the original one. Note that any set of such solutions from the decoupled subproblems is a feasible solution to the original. How much of a blunder are we making? Is there any study on such problems. Simulating on sample data from our system doesn't show much degradation. But, we would like to understand the technical aspect of it.

Answer 1

This idea is the essence of Dantzig-Wolfe decomposition, which is an exact algorithm for solving linear and mixed integer linear programming problems with such block-angular structure. The $\le 0$ constraints in your original problem are called complicating or linking constraints. If these constraints are removed, the resulting subsystem decomposes into $d$ disjoint subproblems. Instead of imposing a stronger version of the linking constraints in each subproblem (which can lose optimality, as you noted), Dantzig-Wolfe relaxes the linking constraints and uses column generation to find improving columns, as in the primal simplex method. A master problem uses the existing columns generated so far and finds optimal dual variables for the linking constraints. Each subproblem is then solved independently (and, optionally, in parallel) to minimize the reduced cost based on the dual values. The process repeats, iterating between master and subproblem until convergence. Upper and lower bounds are available at each stage, so you always have a measure of the current optimality gap.

By the way, this algorithm is implemented in SAS software (disclaimer: I work for SAS). The user can just specify the block id for each constraint, and the solver takes care of the rest. In fact, several automatic block-detection methods are also provided.

---

If you can afford to solve the subproblems twice and the master problem (a tiny LP with $d$ fixed variables) once, you can get an upper bound and hence an optimality gap as follows. (This is essentially one iteration of Dantzig-Wolfe.)

Step 1: Solve the subproblem for each $i$ as you propose, yielding a feasible solution $\mathbf{\hat{x}_i}$.

Step 2: Solve the (restricted) master problem with $d$ variables $\lambda_i$ to get objective value $\hat{z}$ and dual variables $\hat{\pi}$ and $\hat{\beta}_i$.

\begin{align} &\text{maximize} &\sum_{i=1}^{d} \left(\mathbf{c}_i^T\hat{\mathbf{x}}_i\right) \lambda_i \\ &\text{subject to} &\sum_{i=1}^{d}\left((\mathbf{s}_i-\tau\mathbf{c}_i)^{T}\hat{\mathbf{x}}_i\right) \lambda_i &\leq 0 && &&(\pi \ge 0)\\ &&\lambda_i &= 1 &&\text{for $i\in\{1,\dots,d\}$} &&(\text{$\beta_i$ free})\\ &&\lambda_i &\ge 0 &&\text{for $i\in\{1,\dots,d\}$} \\ \end{align} (This has a unique feasible solution $\lambda_i=1$. The point is to get the dual variables.)

Step 3: Solve the subproblem for each $i$ again, but without the modification of the linking constraint and with the objective of maximizing the reduced price of $\lambda_i$, yielding objective values $\hat{w}_i$.

\begin{align} &\text{maximize} &\left(\mathbf{c}_i^T - \hat{\pi} (\mathbf{s}_i-\tau\mathbf{c}_i)\right)^{T}\mathbf{x}_i - \hat{\beta}_i\\ &\text{subject to} &\mathbf{s}_i^T\mathbf{x}_i &\leq \alpha_i \\ &&\mathbf{1}^T\mathbf{x}_i &\leq 1\\ &&\mathbf{x}_i &\geq \mathbf{0} \end{align}

Now $\hat{z}+\sum_{i=1}^d \hat{w}_i$ is an upper bound on the objective value of the original problem. In particular, if $\hat{w}_i = 0$ for all $i$, your heuristic feasible solution with objective value $\hat{z}$ is optimal.