# Iterations of Dantzig-Wolfe Decomposition for a Simple Linear Programming problem

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?

• Can you say anything more about $c$, $a$, and $b$? Also, do you mean instead that $x_i\in\mathbb{R}^d$? – RobPratt May 7 at 12:43
• Corrected the dimensionality. $\mathbf{c} _i$ are element wise positive. Can't assume anything more. – dineshdileep May 7 at 15:33

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.
• Without the coupling constraint, the problem decomposes into $n$ disjoint $2$-constraint LPs, which should be easy even without a specialized solver. It is unclear whether it is easy enough to overcome the fact that you have to do this many times in the course of DWD. How big are $n$ and $d$? How long does it take to solve the original problem directly with an LP solver? – RobPratt May 8 at 12:57