Fourier-Motzkin Elimination and the projection method

[bgkagy3]

I am trying to eliminate 7 variables using Fourier-Motzkin elimination. I have a cone in 17 total variables with the first 7 variables greater or equal to 0 and then 14 equalities, some involving just the first 7 variables and some involving one of the last 10 variables and the first 7 variables.

I defined my cone as $C18 and then ran $C2 = projection($C18,[7,8,9,10,11,12,13,14,15,16]);
This runs for a while and then gives a killed: 9 . I am running this on a macbook. I'm not sure what exactly the problem is, it doesn't feel like it should be too big of example for it to run successfully and i've tried various other examples that were smaller 2 and it did the same thing. Do any of you know what mistake I might be making or another way I could eliminate my first 7 variables?

[gawrilow]

Could you share one of the failed examples please? The smaller, the better

[bgkagy3]

Sure, here is one of the smaller examples I've tried.
$C = new Cone(INEQUALITIES =>[[1,0,0,0,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0,0,0,0,0]],
EQUATIONS => [[1,-1,-1,0,1,0,0,0,0,0,0,0],[1,0,-1,1,0,1,0,0,0,0,0,0],[0,1,0,1,-1,1,0,0,0,0,0,0],[1,0,1,1,0,1,-1,0,0,0,0,0],[1,0,1,1,0,1,0,-1,0,0,0,0],[1,1,1,0,1,0,0,0,-1,0,0,0],[0,0,0,0,0,2,0,0,0,-1,0,0],[0,0,0,1,1,1,0,0,0,0,-1,0],[0,0,0,1,1,1,0,0,0,0,0,-1]]);


print_constraints($C);


$C2 = projection($C,[6,7,8,9,10,11]);

print $C2 -> RAYS;



Everything runs fine until the line with the projection method which runs for a long time before giving a killed: 9.

[gawrilow]

Indeed, the process "explodes", allocating about 1GB memory every second. Adding "nofm" option did not help either. Keep investigating...

[gawrilow]

It turns out that the projection function in polymake is severely broken: it treats the input with EQUALITY property in a highly inefficient manner, leading to a combinatorial exposion. The "nofm" option is also implemented wrongly, it produces just an empty cone object when the input is a cone in H-representation.

However, your case seems to have a rather specific structure which does not require application of Fourier-Motzkin elimination: you are effectively getting rid of all inequalities, leaving a complete linear subspace. While we'll be fixing the function, you can maybe just use direct matrix manipulations to obtain what you want?

[bgkagy3]

I see, well I would appreciate it if you could let me know when projection is fixed!

I'm sure I understand what you are suggesting. My first 3 equations only involve the variables being eliminated. So i need to eliminate both all of the inequalities and those equalities. All for larger examples there are many more of these equations involving only the variables i need to eliminate.

Maybe I'm misunderstanding you though, could you elaborate on what you are suggesting? I have a guess for what the answer is in some examples using more dubious means and it is not linear. tho I wanted to use Fourier motzkin to either confirm or deny my intuition.

[joswig]

Of course, we will fix those errors in polymake. However, your specific computation can be rescued as follows:

Code: Select all

polytope > $C = new Cone(INEQUALITIES =>[[1,0,0,0,0,0,0,0,0,0,0,0],[0,1,0,0,0,0,0,0,0,0,0,0],[0,0,1,0,0,0,0,0,0,0,0,0],[0,0,0,1,0,0,0,00,0,0,0],[0,0,0,0,1,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0,0,0,0,0]], polytope (2)> EQUATIONS => [[1,-1,-1,0,1,0,0,0,0,0,0,0],[1,0,-1,1,0,1,0,0,0,0,0,0],[0,1,0,1,-1,1,0,0,0,0,0,0],[1,0,1,1,0,1,-1,0,0,0,0,0,[1,0,1,1,0,1,0,-1,0,0,0,0],[1,1,1,0,1,0,0,0,-1,0,0,0],[0,0,0,0,0,2,0,0,0,-1,0,0],[0,0,0,1,1,1,0,0,0,0,-1,0],[0,0,0,1,1,1,0,0,0,0,0,-1]); polytope > print $C->N_RAYS; 4 polytope > $C2 = projection($C,[6,7,8,9,10,11],nofm=>1); polytope > print $C2->RAYS; 0 0 1 0 1/2 1/2 1 1 1 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1

The trick is to compute the dual convex hull upstairs, i.e., before the projection. Then projecting is easy.

[bgkagy3]

Ok Thank you for the help! This worked for some of my medium sized examples as well!