[PPL-devel] PPL Library capabilities

[P M Hill]

On Fri, 19 Jun 2009, Michael Kalugin wrote:

> Hello
>
> We have polyhedral representation in our research work and use your
> library(PPL) through Java interface. We have the following problem:
>
> we have a solution set described by a constraint system. We want to
> obtain several different arbitrary integer points from this set. Is
> there a feture in PPL that allows to solve this problem? And if there is
> such feature can we use it through Java interface?

Dear Michael,

We do not have the precise functionality you describe, but there may be 
a way you can use the existing features of the PPL to achieve what you 
require. Here is a proposed possible sequence of actions for getting any 
number of integer points (if they exist):

The best domain you should use for trying to solve your problem will be 
the MIP solver.

0) Using the MIP methods, set up the feasible region by means 
of a set of constraints and set all the dimensions to be integral
(call this MIP problem 'mip0').

1) Use the method feasible_point() to get a first integer point (if it 
exists). Suppose (for example) this point is x == 4;

2) make two copies of the MIP problem mip0 (mip1, mip2);

3) construct two mutually exclusive constraints that exclude the feasible 
point (eg x >= 5 and x <= 3);

4) add one to each MIP problem mip1 and mip2;

5) go to step (1) and repeat with mip1 and mip2.

This suggestion can of course be varied to suit your specific 
requirements, such as in step (2) you may want to make more than two 
copies and in step (3) construct several exclusive sets of constraints. 
So take the above proposal as a guide only and adapt it as will be 
appropriate to your scenario.

All the MIP problem methods and structures mentioned above should be fully 
supported in the Java interface and will be described at: 
http://www.cs.unipr.it/ppl/Documentation/user/ 
ppl-user-java-interface-0.10.2-html/

Of course all the documentation is also available from the PPL sources and 
(assuming you are using the latest development sources) will include 
subsequent improvements to the PPL, including recent changes to the Java 
interface.

If you have problems in using any of these features, let us know.

Do keep us informed as to how the above proposal helps (or does not help) 
with solving your problems.

Thank you for your interest in the PPL and its development.

All the best,
   Pat