7
$\begingroup$

Most descriptions of the Dantzig-Wolfe decomposition, I have seen end up with subproblems like this:

$$\min_{x_j \in \mathbb{R}^n} \{ (\pi A_j - c_j)x_j \mid x_j \in P_j \}$$

They argue that $P_j$ can be described with a finite number of extreme points and extreme rays, so the process of repeatedly generating columns as optimal solutions of the subproblems will terminate eventually. However, most of these descriptions make the assumption that the variables $x_j$ are bounded (non-negative) or that $P_j$ is bounded. I understand that a free variable can be replaced by the difference of two non-negative ones and this seems to be a standard way to satisfy this assumption; for example in [Teb01]. In my case it would be simpler to think about free variables, though.

My question is about the case where all variables $x_j$ are free, so we did not do the transformation to bounded variables. Is the algorithm of repeatedly adding a column to the master problem still finite, if the added column is either (1) an extreme point of $P_j$, or (2) a ray (but not necessarily an extreme ray) of $P_j$ where $(\pi A_j - c_j)x_j < 0$?

I looked in the original paper [DW60] where Theorem 3 seems to say as much but I don't understand it sufficiently well to be sure that there are no addition assumptions about $P_j$.

References

[Teb01] James R. Tebboth, A Computational Study of Dantzig-Wolfe Decomposition, Ph.D. thesis, University of Buckingham, 2001.

[DW60] George B. Dantzig and Philip Wolfe. Decomposition Principle for Linear Programs, Operations Research 8 (1960), no. 1, 101-111.

Improve this question
$\endgroup$
2
  • $\begingroup$ You mean free as in unbounded in the positive or negative direction? With $x = x^+ - x^-$ where $x^+, x^- \geq 0$, the substitution variables are still unbounded. $\endgroup$
    – ktnr
    Jan 24, 2020 at 14:51
  • $\begingroup$ Yes, that is what I meant. I'll replace "the difference of two bounded ones" with "the difference of two non-negative ones". Does that make it more clear? $\endgroup$
    – Florian Pommerening
    Jan 24, 2020 at 14:57

1 Answer 1

Reset to default
6
$\begingroup$

The assumption that the subproblem polyhedron $P_j$ is bounded is for simplicity of exposition (or implementation). Whether or not the variables themselves have explicit bounds, if $P_j$ is bounded, then extreme points suffice, and you do not need extreme rays. In practical applications, all variables have implicit bounds that are implied either by the explicit constraints or by the fact that there aren't enough people on Earth to buy $10^{100}$ widgets even if you had the ability to produce them.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer but I think my question is on a more general problem: if all variables are free, $P_j$ might not have a unique set of extreme rays. In my case, $P_j$ is a cone. Every cone can be split into a pointed cone and a linear space but the linear space may not have extreme rays. So in this case "the set of all extreme points and extreme rays" is not sufficient to represent $P_j$, you also need a basis of the linear space. My question is if picking vectors as described in my question will be sufficient in this case or might end up not terminating. $\endgroup$
    – Florian Pommerening
    Jan 24, 2020 at 17:35
  • 1
    $\begingroup$ Also, I understand your point about all variables being bounded in practice. This is true but it is like saying the answer to the halting problem is "every program halts" (xkcd.com/1266). In practice, this is the case but it is still interesting to look at the halting problem in a theoretical view where a program can run forever. In my case, my problem is completely theoretical and all my variables happen to be unbounded. I'm not after a solution to a specific problem but after a set of theorems about a class of problems. $\endgroup$
    – Florian Pommerening
    Jan 24, 2020 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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