P M Hill wrote:
I have been looking at the definition in Wilde for dual. Comparing this with the definition of a polar, makes me think that what we want is to talk about a polar (also defined by Wilde) rather than a dual.
When the polyhedra is a polytope that includes the origin, then it is likely that a polar and a dual (wrt LP) are the same thing. I'm not certain. However, if we want to generalise to any polyhedra, the polar seems what we want. It is also clearly defined and illustrated in the text books.
Looking in Schrijver (do you have a copy of this book?) chapter 9, page 112/3, if P* is a polar of a polyhedron P, then the face-lattice of P* is the reverse of the face-lattice of P.
Also, If C \sseq R^n is a polyhedral cone, then the polar C* is also a polyhedra cone in R^n such that there is a 1-1 correspondence between the faces of C and C* In this case, a face of dimension k in C is mapped to a face in C* of dimension n-k. This means that there is a correspondence between the extreme rays of P with the facets of P* and vice-versa.
In Nemhauser, page 99, there is a theorem 5.2 that says that if the dimension of P = {x | Ax =< b} is n and rank of A is n and pi \in R^n not= 0, then (pi,pi_0) is an extreme ray of P* iff (pi,pi_0) defines a facet of P.
Also, that if P is a full-dimensional polytope, then after normalising, P* is also a full-dimensional polytope. There is a nice illustration on page 102 of two such polytopes.
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?
[...]
Does anyone feels up to rewriting a specialised version of this definition just for its application to rational polyhedra?
??? I can't answer this question for two reasons:
- 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!".
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.
Ciao, Ange.
PPL-devel mailing list PPL-devel@cs.unipr.it http://www.cs.unipr.it/mailman/listinfo/ppl-devel