On Friday, 16 May 2014 18:11:58 UTC+1, Volker Braun wrote: > > I'm implementing the double description algorithm in that ticket. Its of > course not entirely unrelated, but doesn't do the inequality-reshuffling > part for you. >
There is an alternative to Fourier-Motzkin: compute the cone spanned by the inequalities, and intersect it with the subspace spanned by the variable which are not to be eliminated. This looks like something very easy to implement with the existing Sage functionality. > > > > On Friday, May 16, 2014 4:52:20 PM UTC+1, Dima Pasechnik wrote: >> >> On 2014-05-16, Jeroen Demeyer <[email protected]> wrote: >> > On 2014-05-15 11:33, Volker Braun wrote: >> >> On Thursday, May 15, 2014 8:45:47 AM UTC+1, Jeroen Demeyer wrote: >> >> >> >> > IMHO, Jeroen needs to use Fourier-Motzkin elimination. >> >> Yes, something like that. Elimination based purely on the H-rep >> without >> >> first computing the V-rep. Is this implemented in Sage? In PPL? >> >> >> >> >> >> So is that the question, you have a problem where you can not compute >> >> the V-representation of the initial set of inequalities? >> > Essentially yes, although it is also a matter of patience... >> > The projected polyhedron is much simpler than the original polyhedron >> > before projecting. >> > >> >> There is no special support for doing the Fourier-Motzkin elimination >> of >> >> variables in Sage, but then its a pretty straightforward reshuffling >> of >> >> the inequalities. Then one can hope to apply double description in >> lower >> >> dimension. >> > Of course, but I personally don't feel like implementing this (I also >> > don't really know about the algorithms behind this). >> >> Perhaps Volker's http://trac.sagemath.org/ticket/16101 >> can be used as a good starting point. >> I didn't read the code, but how else does he go between V and >> H-representations, if not by Fourier-Motzkin... >> >> Dima >> >> -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
