Extreme rays in polymake

Question

I am trying to find extreme rays of a polyhedral cone using polymake. My understanding is that in a cone, every feasible solution is also a ray and an extreme ray is a ray that cannot be written as the convex combination of two other rays. The methods RAYS and LINEARITY_SPACE give me some rays that generate the cone but I found an example where one of the rays can be written as the combination of two other rays. Are the results of RAYS not guaranteed to be extreme rays? If so, is there a method to get the extreme rays?

Example

declare $cone=new Cone<Rational>(INEQUALITIES=>[[1, 0, 1], [2, 1, 0]]);
# Note that all variables are unbounded.

print_constraints($cone);
Inequalities:
0: x0 + x2 >= 0
1: 2 x0 + x1 >= 0

print $cone->RAYS; 
1 -2 0
0 1 0

print $pq->LINEALITY_SPACE; 
-1 2 1

The first returned ray $(1, -2, 0)$ can be written as $(1, -2, -1) + (0, 0, 1)$ so it cannot be extreme.

Are you sure that $(0,0,1)$ is an extreme ray, your print statement for cone->RAYS outputs $(0,1,0)$. — batwing, Aug 25 '19 at 14:23
I don't think $(0,0,1)$ is an extreme ray but it satisfies the constraints, so it is a ray (not necessarily extreme). As far as I know, a ray is extreme if it cannot be written as a convex combination of two other non-zero rays (not extreme rays). So $(0,0,1)$ doesn't have to be extreme to show that $(1, -2, 0)$ cannot be extreme. Do I have the definition of extreme rays wrong? — Florian Pommerening, Aug 25 '19 at 19:53
Not all polyhedral cones possess extreme rays. Take for instance the half-space x = 0 in R^3. There are no extreme rays, but there are lineality rays (0, 1, 0), (0,0,1). The pair (0, 1, 0), (0,0,1) isn't unique, in fact they can be rotated by any angle about X- axis, and you still get a valid lineality space. There exist polyhedral cones that can be decomposed into a minkowski sum of lineality space and conic combination of a bunch of rays say R, where R is not unique. In such cases, you need to check what polymake will return. An example would be is z >= x, z >= 0 in (x,y,z) space. — batwing, Aug 25 '19 at 21:39
To add further to the comment above, the concept of extreme rays is relevant mostly to pointed cones i.e cones that do not contain a line segment passing through the origin. — batwing, Aug 25 '19 at 21:49
Ahh, that makes a lot of sense. Could you turn your comment into an answer so I can accept it? Also, does this mean that column generation building on the minkowski sum is not finite because you could generate columns as non-extreme rays approaching such a set R but never enough to describe the cone? — Florian Pommerening, Aug 25 '19 at 22:06
By column generation do you mean the double description method? Also, I believe it is always possible to represent the cone exactly using say the double description method, and obtain a lineality rays L and conic rays R. The property returned by these methods is that, even if one ray from L or R are removed, we no longer represent the input polyhedral cone. — batwing, Aug 25 '19 at 22:14
I was thinking of the Dantzig-Wolfe decomposition with such a cone as a subproblem. So far, I assumed that the decomposition would generate one extreme ray of the cone in every iteration and terminate at the latest when all extreme rays are generated. But if the cone has no extreme rays (i.e., it is generated by non-extreme rays), that means the decomposition has to add non-extreme rays and there is an infinite number of them. So what, if anything, prevents it from generating more and more rays/columns without ever having enough rays to generate the cone? — Florian Pommerening, Aug 26 '19 at 08:59

score 4 · Accepted Answer · edited Aug 26 '19 at 06:16

Not all polyhedral cones possess extreme rays. Take for instance the half-space $x = 0$ in $\Bbb R^3$. There are no extreme rays, but there are lineality rays $(0, 1, 0)$, $(0,0,1)$. The pair $(0, 1, 0)$, $(0,0,1)$ isn't unique, in fact they can be rotated by any angle about $x$-axis, and you still get a valid lineality space. There exist polyhedral cones that can be decomposed into a Minkowski sum of lineality space and conic combination of a bunch of rays (say $R$), where the set $R$ is not unique. In such cases, you need to check what polymake will return. An example would be is $z\ge x$, $z\ge0$ in $(x,y,z)$ space. The concept of extreme rays is relevant mostly to pointed cones i.e cones that do not contain a line segment passing through the origin.

Extreme rays in polymake

1 Answers1