johnyf
commented
3 years ago Thank you for reporting this error. I confirm that zero volume is computed using commit f981f434a270ee005076b9c534383aeaba314f40. The reason appears to be a missing else branch at (within the computation of the bounding box, which is in turn used to compute the polytope's volume):
The consequence of this missing branch is that if the optimization does not succeed, then the value of 0 is used for all bounds, because this is how the bounds are initialized within that function:
Running the lines of code from that area in ipython, when using scipy I get:
>>> sol
{'status': 3,
'x': array([-6.37083e+07, 4.27238e+07, 4.38813e+06, -1.10456e+08,
-1.77619e+08, -3.76229e+07, -1.46560e+08, -1.02404e+07,
-1.70243e+08, -1.55426e+08, -3.99459e+08, -6.16730e+07,
3.36853e+05, -7.07112e+08]),
'fun': -707111604.4008977}and when using cvxopt, I get:
>>> sol
{'status': 3, 'x': None, 'fun': None}Quoting from the documentation of the function scipy.optimize.linprog:
3 : Problem appears to be unbounded.
and the documentation of the function cvxopt.solvers.lp says:
With the GLPK option, the solver does not return certificates of primal or dual infeasibility: if the status is
'primal infeasible'or'dual infeasible', all entries of the output dictionary areNone.
which is relevant to the lines:
So:
- the bounding box computation needs to be corrected to take into account solver failure
- the bounding box computation could be updated to handle unbounded polytopes, though that may better be discussed as a separate issue
- if the polytope described above (https://github.com/tulip-control/polytope/issues/69#issue-902614042) is indeed unbounded, then its volume would be unbounded. So I presume that the Volesti package would be expected to return an infinite volume. However, I am not familiar with the Volesti package, and so I do not know whether it supports unbounded polytopes. The manual of Volesti does not mention unbounded polytopes. Its volume computation is either exact for zonotopes and simplices in V-representation (which are bounded sets), or approximate for other cases. Moreover, in the literature it is not unusual for "polytope" to be be defined as a bounded set, i.e., one that can be described in V-representation. A polytope in H-representation can be unbounded.
I had been aware that unbounded polytopes are currently unsupported by the package polytope, and intended to consider that topic in a separate issue at some point in the future.
In conclusion, the simplest approach for now seems to be to raise an exception from within the function polytope.polytope.bounding_box if no solution is found (until unbounded polytopes become supported).
Regarding the polytope given above (https://github.com/tulip-control/polytope/issues/69#issue-902614042), if indeed it is unbounded, then its volume is infinite.
alhaas
necozay
Dear polytope devs,
I hope this is the right place for this. I have created an example similar to the one in the tutorial for a convex polytope in H-representation, however it gives me a volume of 0.0 and also, there is no warning in case the dimensions do not match. I think I am missing something here, as the same problem gives a nonzero volume with the Volesti package in R.
My Python version is 3.7.6.