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?

  • $\begingroup$ Cross-posted: mathoverflow.net/questions/392133/… $\endgroup$
    – RobPratt
    May 15 at 12:51
  • $\begingroup$ @RobPratt can you please help? $\endgroup$ May 17 at 5:28
  • $\begingroup$ Not sure how to help here. The steps are the same as traditional DWD, iterating between master LP solves and subproblem LP solves, except that for the subproblems you will call your oracle instead of a standard LP solver. $\endgroup$
    – RobPratt
    May 17 at 12:18
  • $\begingroup$ @RobPratt do you mind pointing to a good reference in this regard? $\endgroup$ May 18 at 4:04
  • 1
    $\begingroup$ See Chapter 26 of Chvatal's Linear Programming (1983). Chapter 17 of Network Flows (1993) discusses DWD in the context of the minimum-cost multicommodity flow problem, which was the motivating application, having block-angular structure with network blocks. $\endgroup$
    – RobPratt
    May 19 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.