forum.polymake.org

Posted: **22 Dec 2014, 16:47**

Dear all,

I am solving the following problem:

Input: Polytope P given in V-description, polytope Q given in V-description (P & Q may not be bounded)
Output: “Yes” if P ⊆ Q, “No” otherwise

I thought of enumerating the FACETS of P and checking whether each vertex of Q satisfies the constraints from P->FACETS. Is this the optimal way ?

Secondly, Is there an easy way (e.g. set of commands) to check whether Q->VERTICES satisfies P->FACETS in polymake ?

Thank you,

Satya

Posted: **23 Dec 2014, 15:12**

Hello Satya,

there is an (undocumented

) method

Code: Select all

$q->contains($v)

in polymake which checks whether a given point $v is contained in a polytope $q. Thus you can just iterate over the VERTICES of $p and pass them to this function.
This should also work in the unbounded case.

Internally this will use the facets if they are available, otherwise it will use the vertices of $q and solve one LP. Solving one LP per vertex of $p is in general better than enumerating the facets, but this of course depends on your example.

How to do such a check with the facets can be seen in the code of the contains method: apps/polytope/rules/common.rules starting from line 628.

Benjamin

Posted: **24 Dec 2014, 01:12**

Hi Benjamin, Thank you !

Posted: **24 Dec 2014, 03:36**

Hi, to be sure, Does the contains function also takes into account the AFFINE_HULL property ?

Posted: **25 Dec 2014, 11:49**

Yes, it will also check whether the point satisfies the affine hull equations.

Benjamin

Posted: **28 Dec 2014, 03:30**

Hello,

I tried using contains on a specific example. I read the lp file using lp2poly:

$f = convert_to<Rational>lp2poly('demo1.lp');
(below is the lp file, sorry could not attach it)

Code: Select all

Maximize
 
Subject To
 c0: - a1 + a2 - a11 = 2
 cc2l0: - a1 + a2 <= 1
 c1: a2 - a6 = 1
 cc2l1: - a1 + a2 <= 1
 c2: a3 + a5 - a7 = -1
 cc2l2: a3 + a5 - a18 <= -2
 cc3l2: a5 <= -1
 cc4l2: a3 - a4 + a5 <= -1
 c3: - a3 + a4 + a6 = -1
 cc1l3: a4 + a6 - a8 <= -1
 cc3l3: a6 <= -1
 c4: a3 + a5 - a7 = -1
 cc0l4: a3 <= -1
 cc3l4: a3 - a5 <= 0
 cc4l4: a3 + a5 - a6 <= -2
 cc5l4: a3 + a5 - a9 <= -1
 cc6l4: - a1 + a3 + a5 - a11 <= 0
 c5: a4 + a6 - a8 = -2
 cc0l5: a4 - a5 + a6 <= -1
 cc1l5: a4 <= -1
 cc3l5: a4 + a6 - a8 <= -1
 cc4l5: a4 <= -2
 cc5l5: a4 - a6 <= 0
 cc6l5: a4 + a6 - a10 <= -1
 c6: a3 + a5 - a7 = -1
 c7: a7 - a8 = -1
 cc1l7: - a4 - a6 + a7 <= 1
 cc2l7: a7 - a8 <= 0
 c8: 2 a5 - a9 = -1
 c9: 2 a6 - a10 = -1
 cc0l9: 2 a6 - a9 <= -1
 c10: a11 - a14 = -1
 c11: a11 - a12 - a13 = -4
 cc0l11: a11 <= 1
 cc2l11: a11 - a12 <= 0
 cc4l11: a11 - a15 <= 0
 cc5l11: a11 - a12 <= -1
 c12: a11 - a12 - a13 = -4
 cc0l12: a11 <= 1
 cc2l12: a11 - a13 <= 0
 cc4l12: a11 - a16 <= 0
 cc5l12: a11 - a13 <= -1
 c13: a12 + a13 - a14 = 3
 cc0l13: a12 + a13 - a14 <= 4
 c14: a12 - a15 = 1
 c15: a13 - a16 = 1
 c16: - a8 + a17 = -1
 c17: a17 - a18 = -1
 c18: - a7 = 2
 cc0l18: - a10 <= 2
 cc2l18: - a1 <= 2
 cc3l18: - a2 <= 2
 cc4l18: - a5 <= 2
 cc5l18: - a6 <= 2
 cc7l18: - a8 <= 2
 cc8l18: - a9 <= 2
 c19: - a3 = 2
 cc2l19: - a4 <= 2
 cc3l19: - a17 <= 2
 cc4l19: - a18 <= 2
 cc5l19: - a7 <= 2
 cc6l19: - a8 <= 2
Bounds
 a1 free
 a2 free
 a3 free
 a4 free
 a5 free
 a6 free
 a7 free
 a8 free
 a9 free
 a10 free
 a11 free
 a12 free
 a13 free
 a14 free
 a15 free
 a16 free
 a17 free
 a18 free
End

Thereafter, I want to check whether a point $v given by:

Code: Select all

$v = new Vector<Rational>([1, -1,0,-2,-2,-1,-1,-2,-1,-1,-1,-1,0,3,0,-1,2,-2,-1]);

is present in the polytope, for which I use:

Code: Select all

print $f->contains($v);

This doesn't return 1 but I guess the point satisfies the inequalities & equations above. Is there something wrong ?

Thanks,
Satya

Posted: **28 Dec 2014, 14:46**

Hello Satya,

the reason why this point is not in the polytope is that the coordinates are not in the order you are assuming for $v. You can check the coordinates with:

Code: Select all

polytope > print $f->COORDINATE_LABELS;
inhomog_var a1 a9 a11 a13 a10 a12 a15 a8 a14 a16 a17 a2 a5 a6 a3 a7 a18 a4

One way to reorder the coordinates is the following:

Code: Select all

@vars = ("inhomog_var",map {"a".$_} (1..18));
$perm = find_permutation($f->COORDINATE_LABELS,[@vars]);
shift @vars; // see PS below
$fperm = new Polytope(INEQUALITIES=>permuted_cols($f->INEQUALITIES,$perm), EQUATIONS=>permuted_cols($f->EQUATIONS,$perm), COORDINATE_LABELS=>[@vars]);

And after this transformation your vector is contained in the polytope:

Code: Select all

polytope > $v = new Vector<Rational>([1,-1,0,-2,-2,-1,-1,-2,-1,-1,-1,-1,0,3,0,-1,2,-2,-1]);
polytope > print $fperm->contains($v);
1

Benjamin

PS: I added the "shift @vars;" here to make sure that "print_constraints($fperm);" works correctly. With this command you can check whether all constraints have been parsed correctly. See also here.

PPS: There are two reasons why the order is messed up:

The code parsing the lp tries to sort the variables but it applies the reverse permutation.
The variables are sorted as strings and thus "a10" < "a2". So even with the above fixed this would not produce the ordering you want.

Posted: **28 Dec 2014, 18:26**

Hi Benjamin,

The line:

Code: Select all

 $perm = find_permutation($f->COORDINATE_LABELS,[@vars]);

gives the following error:

Code: Select all

polymake:  ERROR: Shared module compilation failed; see the error log below
make: g++: Command not found
make: *** [/tmp/poly23874Taaaa0013.o] Error 127

I am using polymake version 2.12, released on March 19, 2012

Best,
Satya

Posted: **29 Dec 2014, 11:31**

try using the function:

Code: Select all

included_polyhedra (P1, P2) → Bool
Tests if polyhedron P1 is included in polyhedron P2.

Parameters
  Polytope	P1	the first polytope
  Polytope	P2	the second polytope
  
Returns Bool	'true' if P1 is included in P2, 'false' otherwise

Posted: **29 Dec 2014, 11:42**

Hi,

Thanks for this new function. I am still interested to change the coordinate labels. This will ensure consistency because I read many polytopes and then check for equality and containment

Regards,
Satya

forum.polymake.org

Polytope Containment

Polytope Containment

Re: Polytope Containment

Re: Polytope Containment

Re: Polytope Containment

Re: Polytope Containment

Re: Polytope Containment

Re: Polytope Containment

Re: Polytope Containment

Re: Polytope Containment

Re: Polytope Containment