Polytope Containment

Questions and problems about using polymake go here.
satya123999
Posts: 25
Joined: 02 Apr 2013, 17:30

Polytope Containment

Postby satya123999 » 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

blorenz
Developer
Posts: 139
Joined: 10 Jan 2011, 17:21

Re: Polytope Containment

Postby blorenz » 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

satya123999
Posts: 25
Joined: 02 Apr 2013, 17:30

Re: Polytope Containment

Postby satya123999 » 24 Dec 2014, 01:12

Hi Benjamin, Thank you !

satya123999
Posts: 25
Joined: 02 Apr 2013, 17:30

Re: Polytope Containment

Postby satya123999 » 24 Dec 2014, 03:36

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

blorenz
Developer
Posts: 139
Joined: 10 Jan 2011, 17:21

Re: Polytope Containment

Postby blorenz » 25 Dec 2014, 11:49

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

Benjamin

satya123999
Posts: 25
Joined: 02 Apr 2013, 17:30

Re: Polytope Containment

Postby satya123999 » 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

blorenz
Developer
Posts: 139
Joined: 10 Jan 2011, 17:21

Re: Polytope Containment

Postby blorenz » 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.

satya123999
Posts: 25
Joined: 02 Apr 2013, 17:30

Re: Polytope Containment

Postby satya123999 » 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

User avatar
assarf
Developer
Posts: 74
Joined: 12 Oct 2011, 15:52

Re: Polytope Containment

Postby assarf » 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
no signature

satya123999
Posts: 25
Joined: 02 Apr 2013, 17:30

Re: Polytope Containment

Postby satya123999 » 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


Return to “Helpdesk”