[PPL-devel] Polyhedra with non-integral coefficients

[Pat Hill]

On Mon, 7 Nov 2011, Alet Roux wrote:

> Dear Dr. Hill
>
> I am working in Mathematical Finance at the University of York, in the
> area of asset pricing under proportional transaction costs. As part of
> our work, we have developed algorithms that perform certain operations
> on polyhedra, most notably intersection and taking convex hulls. (I also
> have high hopes that we might one day be able to handle unions in some
> way...)
>
> Part of my contribution to the project is to implement our algorithms in
> C/C++. I was very pleased to come across the the well-documented and
> easy-to-use Parma Polyhedra Library. I note that the library allows
> integral coefficients only. However, for our needs, we require floating
> point or (probably more practical from a precision point of view)
> rational coefficients.

It is good to know you find it well-documented and easy-to-use.

Yes, the coefficients of constraints and generators have to be integers 
(mpz_class in the default configuration). However, the PPL implements a 
domain of convex _rational_ polyhedra. The restriction to integer 
coefficients is just for the representation and input/output. We can do 
this since any constraint having rational coefficients can be normalized 
so as to have integer coefficients. For generators, the same is achieved 
by including an integer divisor, (which by default is 1, but not 
necessarily so).

I see from your email that you already have written your own algorithms 
for intersection and convex-hull. These as well as union are operations 
provided by the PPL. Documentation for these is in the PPL; but if you 
miss the exact information needed to make full use of the PPL, you should 
not hesitate to ask.

>
> It appears to me that it may be possible to tweak the Parma Polyhedra
> Library for our use by simply changing the data type Variable, but I am
> a bit nervous about this (I am a mathematician, and enthusiastic C++
> programmer, but not a computer scientist by any means). My question is,
> in your view, is this a reasonable thing to try out? Any health
> warnings? Or will it simply not work?

There is no need (nor would it be advisable) to change the data types.

> I would be very grateful for any other advice that you might have on
> this issue.

Note that I am cc'ing this to the PPL-devel mailing list in case other 
users/developers may wish to give more advice.

I hope this helps,

Pat

>
> Thank you very much in advance,
>
> Alet Roux
>
>