Page 1 of 1

Content of Cone::RAYS if there are no extreme rays

Posted: 26 Aug 2019, 16:32
by Florian
I am working on a Dantzig-Wolfe decomposition and one of my subproblems is a polyhedral cone. Until recently, I thought the Dantzig-Wolfe decomposition would add new columns based on extreme rays of the cone and terminate eventually because the number of extreme rays is finite. Then I learned that a cone doesn't necessarily have extreme rays if it is not pointed and that it could be generated by a set of non-extreme rays instead. As the set of generators is not unique and the set of (extreme and non-extreme) rays is infinite, I'm worried that the Dantzig-Wolfe decomposition would lose its termination guarantee.

My question is about how polymake deals with this: are there any guarantees about the rays returned in Cone::RAYS when the cone has no extreme rays? Is there a property that distinguishes those rays from other sets of rays that would generate the cone?

Re: Content of Cone::RAYS if there are no extreme rays

Posted: 26 Aug 2019, 23:25
by paffenholz
polymake splits the information about the generating set of a cone C into two parts: For any cone we can find a pointed cone D and a linear space L such that C is the Minkowski sum of those two (Minkowski-Weyl-Theorem).

The cone D has a unique (up to scaling of the individual generators by a positive factor) minimal generating set. This is the set returned if you ask for the RAYS of a cone. The linear space is spanned by a basis, unique up to multiplication with a non-singular matrix. You get one basis if you ask for LINEALITY_SPACE in polymake.

The splitting into D and L is not unique. D is the intersection of C with some hyperplane transversal to L. The exact result depends on the input and the chosen algorithm, if the input is redundant. E.g.

Code: Select all

polytope > $c=new Cone(INPUT_RAYS=>[[1,0,0],[-1,0,0],[1,1,0],[2,-1,0],[1,2,3]]); polytope > print $c->RAYS; 1 2 3 polytope > print $c->LINEALITY_SPACE; 1 0 0 0 1 0
If you look at polyhedra instead of cones you get a third part in the decomposition, which is a polytope. In this case you get both the polytope and the cone when asking for VERTICES. The bounded part is defined by the rows with a leading 1, while the cone part is given by the rows with a leading 0.

If you don't know whether your input is irredundant you should use INPUT_RAYS as the input property. This may also contain rays that actually beling to the lineality space. polymake with split the sets when asked for RAYS/LINEALITY_SPACE. For polytopes the corresponding input property is POINTS.

Re: Content of Cone::RAYS if there are no extreme rays

Posted: 29 Aug 2019, 09:12
by Florian
Thank you for the excellent answer. Is there a way to generate rays from some fixed choice of (D, L) in a column generation approach? My concern is that generating just "some ray" might generate rays from different choices of (D,L) and the column generation might not terminate.

Re: Content of Cone::RAYS if there are no extreme rays

Posted: 03 Sep 2019, 13:19
by paffenholz
I am not sure I understand what you intend to do. Without own programming polymake does not do any incremental generation of extreme rays or generators (some convex hull codes used by polymakemay do this internally, but we don't provide access to this).

You however get the following guarantee: If you start with some redundant set of generators for your cone or polytope (which may include lineality), then the irredundant output returned from this will be a subset of your input. There is one exception to this: If your input is only a linear space and does not have any pointed part, then you additionally get the ray (1,0,0,...,0) in the irredundant list, i.e. for polymake any cone has a pointed part (which may be just the origin).

You may get different subsets in every run of the convex hull algorithms though, in particular if you (or polymake) choses a different algorithm.

Re: Content of Cone::RAYS if there are no extreme rays

Posted: 15 Sep 2019, 15:43
by Florian
I'm trying to use polymake to analyze a problem that I want to solve with column generation. In the end, I would like to generate the rays with a problem-specific method (not with polymake) and I'm currently trying to figure out if this is possible in my case. To do so, I generated small instances of the subproblems and used polymake to find their extreme rays. My hope was to see a pattern in the small solutions and then prove that this pattern characterizes the extreme rays of the subproblems. I thought I was making progress by proving some necessary properties of extreme rays but then ran into an example without unique extreme rays. This surprised me because so far I had assumed that the set of extreme rays was unique and finite.

My follow-up question was more about the underlying mathematics, not about polymake specifically. My understanding of the Dantzig-Wolfe decomposition so far was that the extensive formulation of the problem has a finite number of columns and solving a subproblem will generate one of these (or signal that no new column is necessary). From your answer, I gather that every choice of (D,L) will lead to different extensive formulation (each finite, but there might be infinitely many choices of (D,L)). Then, solving a subproblem will generate a column that is a valid dual constraint but not necessarily one of the columns of a particular extensive formulation. Does this mean that the procedure is not guaranteed to terminate?