[PPL-devel] duals and DD

[Angela Stazzone]

P M Hill wrote:

> Hi,
>
> >
> > I'm a bit confused, maybe because I never think carefully enough about
> > use of duality in PPL. I can tell you what we do in the
> > implementation: do you help me to decide what we need?
> >
> > Several function in the PPL are used both to work on constraints and
> > generators without any difference (look, for example, at
> > conversion.cc) and we justify this with duality. In other words we
> > treat lines like equalities and rays like inequalities. I think this
> > is allowed for double representation and duality, but I can't put
> > these things together. Can you help me?
> >
>
> The concept of "dual" has a generic meaning and of course, there is a kind
> of duality between the two representations. But, in LP, the term "dual"
> has a very specific meaning converting between a max and a min
> computation. This does not seem to correspond exactly to
> the implicit duality observed in the DD method. I think it only
> corresponds when we have a polytope that includes the origin. I think I
> have read that somewhere. (Also, it is clear that a polytope always has a
> finite max and a min but a cone does not.)
>
> In the paper by Fukuda and Prodin you sent me, page 2, (A,R) is a DD pair
> iff (R^T,A^T) is a DD pair.
> So, of course, the same algorithms can be used to go from A to R and
> from R^T to A^T.
>
> However, if (A,R) is a DD pair, this is not saying that P(A) is a dual of
> P(R).
>
> > > > - first I have not clear the meaning of "feels up" (sorry!)
> > > > - moreover I don't understand what does it means that a ray is stable (even
> > > > it seems to be
> > > >     very easy! ;-))
> > > >
> > >
> > > Sorry, I should be more careful in using colloquial expressions...
> > > "feels up to" means (approximately) "is able to"
> > > but it also implies that the task is hard and you may not want to...
> > > I am sure it is hard - but maybe one of you young mathematicians can show
> > > us an easy way to understand this - just in the context of polyhedra.
> >
> > Well, in italian we say:"Posso parlare solo per me stessa"... in english
> > maybe:"I'm sure I'm not able to..., but maybe the others guys do!".
>
> Esattamente ;)
>
> >
> > If you have an idea of how it can be done, please let me know it. I will think
> > about it and I will try to improve the documentation.
>
> I will check the actual documentation and see if I can be of more
> direct help.
>
> ciao,
>   Pat

Thanks,
   Ange.

>
>
> _______________________________________________
> PPL-devel mailing list
> PPL-devel at cs.unipr.it
> http://www.cs.unipr.it/mailman/listinfo/ppl-devel