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?
$\begingroup$
$\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$– RobPrattMay 7, 2021 at 12:43
-
$\begingroup$ Corrected the dimensionality. $\mathbf{c} _i$ are element wise positive. Can't assume anything more. $\endgroup$– dineshdileepMay 7, 2021 at 15:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Assume that the problem is easily solvable without the coupling constraint. Then, is there a easy way out? $\endgroup$ May 8, 2021 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$– RobPrattMay 8, 2021 at 12:57