0
$\begingroup$

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?

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

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.

$\endgroup$
2
  • $\begingroup$ Assume that the problem is easily solvable without the coupling constraint. Then, is there a easy way out? $\endgroup$ – dineshdileep May 8 at 5:14
  • $\begingroup$ 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? $\endgroup$ – RobPratt May 8 at 12:57

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.