Return to Answer

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.

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.

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\right)^{T}\hat{\mathbf{x}}_i \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.

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.

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.

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\right)^{T}\hat{\mathbf{x}}_i \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.