7
$\begingroup$

I have a polytope given by some equalities and inequalities, how can I get all the vertices of the polytope? If there's a way to deal with the one given by inequalities only, how can I reduce the equalities and inequalities to inequalities only?

--Updated 2013.12.11--

m=SparseArray[Automatic,{28,56},0,{1,{{0,6,12,18,24,39,50,61,67,73,79,94,105,116,122,128,143,154,165,185,205,234,257,268,279,302,313,324,335},{{1},{2},{3},{4},{5},{6},{1},{7},{8},{9},{10},{11},{2},{7},{12},{13},{14},{15},{3},{8},{12},{16},{17},{18},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{13},{14},{16},{17},{19},{1},{2},{3},{5},{7},{8},{10},{12},{14},{17},{20},{1},{2},{3},{4},{7},{8},{9},{12},{13},{16},{21},{1},{22},{23},{24},{25},{26},{2},{22},{27},{28},{29},{30},{3},{23},{27},{31},{32},{33},{1},{2},{3},{4},{5},{22},{23},{24},{25},{27},{28},{29},{31},{32},{34},{1},{2},{3},{5},{22},{23},{25},{27},{29},{32},{35},{1},{2},{3},{4},{22},{23},{24},{27},{28},{31},{36},{7},{22},{37},{38},{39},{40},{8},{23},{37},{41},{42},{43},{1},{7},{8},{9},{10},{22},{23},{24},{25},{37},{38},{39},{41},{42},{44},{1},{7},{8},{10},{22},{23},{25},{37},{39},{42},{45},{1},{7},{8},{9},{22},{23},{24},{37},{38},{41},{46},{1},{2},{3},{4},{7},{8},{9},{12},{13},{16},{22},{23},{24},{27},{28},{31},{37},{38},{41},{47},{1},{2},{3},{5},{7},{8},{10},{12},{14},{17},{22},{23},{25},{27},{29},{32},{37},{39},{42},{48},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{13},{14},{16},{17},{22},{23},{24},{25},{27},{28},{29},{31},{32},{37},{38},{39},{41},{42},{49},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{16},{17},{22},{23},{24},{25},{27},{31},{32},{37},{41},{42},{50},{1},{3},{5},{8},{10},{17},{23},{25},{32},{42},{51},{1},{3},{4},{8},{9},{16},{23},{24},{31},{41},{52},{1},{2},{3},{4},{5},{7},{8},{9},{10},{12},{13},{14},{22},{23},{24},{25},{27},{28},{29},{37},{38},{39},{53},{1},{2},{5},{7},{10},{14},{22},{25},{29},{39},{54},{1},{2},{4},{7},{9},{13},{22},{24},{28},{38},{55},{1},{2},{3},{7},{8},{12},{22},{23},{27},{37},{56}}},{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-2,-2,-2,-1,-1,-2,-2,-1,-1,-1,-1,-1,-1,-1,-2,-2,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-2,-1,-2,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,-2,-2,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-2,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}}]; b={-(2/7),-(2/7),-(2/7),-(2/7),-(5/7),3/7,3/7,-(2/7),-(2/7),-(2/7),-(5/7),3/7,3/7,-(2/7),-(2/7),-(5/7),3/7,3/7,-(20/21),-(20/21),34/21,25/21,-(11/21),-(11/21),25/21,-(11/21),-(11/21),-(11/21)};

The equalities are m.x==b and the inequalities are x>=0

$\endgroup$
6
2
$\begingroup$

To put Daniel's comment into code:

x = Array[C, Length@First@m];
constr = First@Solve[m.x == b]
(*
  {C[6] -> -(2/7) - C[1] - C[2] - C[3] - C[4] - C[5], <<26>>,
   C[56] -> -(11/21)-C[1]-C[2]-C[3]-C[7]-C[8]-C[12]-C[22]-C[23]-C[27]-C[37]}
*)

Reduce[Thread[x >= 0] /. constr, Variables[x /. constr]]
(*  False  *)

Easy, fast, and disappointing. The polytope is an empty set.

The closest point to the origin consists of the vector with coordinates all equal to -1/21:

PseudoInverse[m].b
(*  {-(1/21), -(1/21), <<25>>, -(1/21)}  *)

This vector is normal to the affine subspace m.x == b, so the subspace does not intersect the positive orthant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.