tulip-control / polytope

Geometric operations on polytopes of any dimension
https://pypi.org/project/polytope
Other
73 stars 19 forks source link

`.project` can return redundant hyperplanes despite `minrep == True` #75

Open matthewearl opened 2 years ago

matthewearl commented 2 years ago

When attempting to construct the Minkowski sum of two [-1, 1]^3 cubes using the method described in section 2 of this paper, I end up projecting a 6D polytope with 12 constraints, as constructed below. The polytope returned by project claims to be in minimal representation however it contains 8 redundant hyperplanes.

import numpy as np
from polytope import Polytope, reduce

pt = Polytope(
    np.array([[ 0,  0,  0,  1,  0,  0],
              [ 0,  0,  0,  0,  1,  0],
              [ 0,  0,  0,  0,  0,  1],
              [ 0,  0,  0, -1,  0,  0],
              [ 0,  0,  0,  0, -1,  0],
              [ 0,  0,  0,  0,  0, -1],
              [ 1,  0,  0, -1,  0,  0],
              [ 0,  1,  0,  0, -1,  0],
              [ 0,  0,  1,  0,  0, -1],
              [-1,  0,  0,  1,  0,  0],
              [ 0, -1,  0,  0,  1,  0],
              [ 0,  0, -1,  0,  0,  1]]),
    np.ones((12,))
)

projected_pt = pt.project([1, 2, 3], solver='exthull')

print('is projected_pt minrep?', projected_pt.minrep)
print('projected_pt:')
print(projected_pt)
print('reduced projected pt after unsetting minrep:')
print(reduce(Polytope(projected_pt.A, projected_pt.b)))

The above prints:

is projected_pt minrep? True
projected_pt:
Single polytope 
  [[ 0. -0. -1.] |    [[2.]
   [-1.  0. -0.] |     [2.]
   [ 0. -1. -0.] |     [2.]
   [ 0.  1. -0.] |     [2.]
   [ 1. -0. -0.] |     [2.]
   [-1.  0. -0.] |     [2.]
   [-0. -1. -0.] x <=  [2.]
   [-0. -0.  1.] |     [2.]
   [ 0.  0. -1.] |     [2.]
   [ 0.  1. -0.] |     [2.]
   [ 1.  0. -0.] |     [2.]
   [ 0.  1.  0.] |     [2.]
   [ 1.  0.  0.] |     [2.]
   [ 0. -0.  1.]]|     [2.]]

reduced projected pt after unsetting minrep:
Single polytope 
  [[-1.  0. -0.] |    [[2.]
   [-0. -1. -0.] |     [2.]
   [ 0.  0. -1.] x <=  [2.]
   [ 0.  1.  0.] |     [2.]
   [ 1.  0.  0.] |     [2.]
   [ 0. -0.  1.]]|     [2.]]
matthewearl commented 2 years ago

This occurs with the exthull and iterhull solvers, but not fm.