This arises from an engineering problem I am working on. Let $\mathbf{c}\_i,\mathbf{a}\_i,\mathbf{b}\_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the polyhedrons (indexed over $i$)
$$
\mathcal{Q}\_i\,=\,\{\mathbf{x}\_i\in\mathbb{R}^d ~\lvert~ \mathbf{b}\_i^T\mathbf{x}\_i\leq 0,~\mathbf{e}^T\mathbf{x}\_i-1\leq 0,~\mathbf{x}\_i\geq 0 \}
$$
where $\mathbf{e}$ is the all-ones vector of appropriate dimension. Now, consider the optimization problem
\begin{align}
\max\_{\mathbf{x}\_i} ~&\sum\_{i=1}^{n}\mathbf{c}\_i^T\mathbf{x}\_i ~\\
~~&\sum\_{i=1}^{n}\mathbf{a}\_i^T\mathbf{x}\_i~\leq~0 \\
~~&\mathbf{x}\_i\in\mathcal{Q}\_i~,~~\forall i \in \{1,\dots,n\}
\end{align}
You can see that this can be converted to the standard input form for the Dantzig-Wolfe Decomposition (DWD). However, I am curious to know given the even more specialized structure of this problem, can we specialize the iterations of the DWD?



Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem
You could specialize Dantzig-Wolfe by solving the subproblems (one per $i$) with an oracle other than LP. If the constraint $\mathbf{b}\_i^\top \mathbf{x}\_i \le 0$ weren't there, you could enumerate the resulting $d+1$ extreme points implied by $\mathbf{e}\_i^\top \mathbf{x}\_i \le 1$. You can also solve the subproblems in parallel, but I think it will be tough to beat just solving the original problem with a traditional LP algorithm like dual simplex or interior point. Dantzig-Wolfe is generally much more useful for MILP than for LP.


