9
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Are you sure that $(0,0,1)$ is an extreme ray, your print statement for cone->RAYS outputs $(0,1,0)$. $\endgroup$ – batwing Aug 25 '19 at 14:23
  • $\begingroup$ 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? $\endgroup$ – Florian Pommerening Aug 25 '19 at 19:53
  • $\begingroup$ 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. $\endgroup$ – batwing Aug 25 '19 at 21:39
  • $\begingroup$ 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. $\endgroup$ – batwing Aug 25 '19 at 21:49
  • $\begingroup$ 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? $\endgroup$ – Florian Pommerening Aug 25 '19 at 22:06
4
$\begingroup$

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.

Improve this answer
$\endgroup$

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.