Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
1  
Wikipedia article: Vertex enumeration problem. MATLAB code that purports to solve the problem: Representing Polyhedral Convex Hulls by Vertices or (In)Equalities. –  Rahul Narain Dec 7 '13 at 8:23
    
a little related plot the boundaries of piecewise function –  Kuba Dec 7 '13 at 9:18
    
Please post one example of such a polytope (defined by both equalities and inequalities) so we can work on some real object. –  belisarius Dec 7 '13 at 19:46
    
Related, but only inequalities and convex polytopes: stackoverflow.com/questions/3815496/… –  belisarius Dec 7 '13 at 19:50
    
You can use the equalities to eliminate variables. Then you are left with just inequalities, in fewer variables. –  Daniel Lichtblau Dec 7 '13 at 21:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.