# Specializing Iterations of Dantzig-Wolfe Decomposition with an Oracle

This arises from an engineering problem I am working on. Let $$\mathbf{c}_i,\mathbf{a}_i\in \mathbb{R}^{d}$$ be a given set (collection) of vectors where $$i\in\{1,\dots,n\}$$. Define the bounded polyhedrons (indexed over $$i$$) $$\mathcal{Q}_i\,=\,\{\mathbf{x}_i\in\mathbb{R}^d ~\lvert~ \mathbf{A}_i\mathbf{x}_i\leq \mathbf{b}_i,~\mathbf{x}_i\geq 0 \}$$ where $$\mathbf{A}_i$$ and $$\mathbf{b}_i$$ is a matrix and vector defining the bounded polyhedron $$\mathcal{Q}_i$$ (over all $$i$$) with appropriate dimensions and assume their interiors are non-empty. Now, consider the optimization problem ($$\alpha$$ is a positive constant) \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~\alpha \\ ~~&\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). Due to the properties of $$\mathcal{Q}_i$$, it turns out that I can assume access to an oracle that can solve the collection of $$n$$ subproblems extremely fast compared to a standard LP solver \begin{align} \max_{\mathbf{x}_i} ~&\mathbf{c}_i^T\mathbf{x}_i ~\\ ~~&\mathbf{x}_i\in\mathcal{Q}_i~ \end{align} Given the Oracle, how should I modify the steps of DWD? can you please provide the details?

I can also assume that the oracle is extremely fast at giving the extreme points of $$\mathcal{Q}_i$$. Given these two facts, can I further specialize the iterations of DWD. Do you mind providing the steps of the DWD then?

• Cross-posted: mathoverflow.net/questions/392133/… – RobPratt May 15 at 12:51