[PPL-devel] duals and DD

[P M Hill]

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