Can't find a solution that's not full-dimensional

[jtuckerfoltz]

In the attached example, pypoman incorrectly says that the first LP is feasible but the second is not. However, they should both be feasible. In going from the first LP to the second, all I have done is added one new variable (first column of A_2) and two new constraints (last two rows of A_2 and last two entries of b_2) enforcing that the new variable be zero. Therefore, we can take a solution from the first LP and append a zero to the beginning to get a solution to the second LP. Yet when I enumerate the vertices, the second one comes up empty. The problem has something to do with decimal precision; if you round each decimal entry of b_2 to one less decimal place, the problem disappears. FYI, I am using Python 3.8.5.
pypoman_bug.zip

[stephane-caron]

Yes, compute_polytope_vertices won't work well with tight constraints such as the equality constraint you have formulated this way. If we relax the equality constraint a bit it will find a solution:

import pypoman
import numpy as np

# Original problem
A_1 = np.array([[-1, -1, -1], [1, 1, 1], [-1, 0, 0], [1, 0, 0], [0, -1, 0],
                [0, 1, 0], [0, 0, -1], [0, 0, 1], [1, 0, 0]])
b_1 = np.array([-1, 1, -0.0001, 0.4999, -0.0001, 0.4999, -0.0001, 0.4999,
                0.4999])
print("{} vertices".format(len(pypoman.compute_polytope_vertices(A_1, b_1))))

# Add new variable
A_2 = np.hstack([[[-1], [1], [0], [0], [0], [0], [0], [0], [1]], A_1])
b_2 = b_1

# Add (relaxed) constraint that new variable is == 0
epsilon = 1e-3
A_2 = np.vstack([A_2, [[-1, 0, 0, 0], [1, 0, 0, 0]]])
b_2 = np.hstack([b_2, epsilon, epsilon])
print("{} vertices".format(len(pypoman.compute_polytope_vertices(A_2, b_2))))

For me conversion of the second problem works down to epsilon = 1e-4, and starts to fail around epsilon = 1e-5.

For equality constraints, you could switch to pycddlib directly and use the linear set lin_set of equality-constraint generators. I'm not actively developing pypoman any more, but I'd be glad to merge a PR adding this feature to it as well 😉

[stephane-caron]

Closing this issue now, feel free to re-open for further discussion.