[PPL-devel] PPL Library capabilities

[P M Hill]

On Tue, 5 May 2009, Vladimir Koshelev 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 matrix *A(n, m)* with *rank(A)* < *min(n, m).*
>
> Also we have system of equations *Ax = 0*.
>
> We need to find *x = Uy*, where *U* is integer upper triangular matrix,
> *x* is an integer solution of previous system and* y* is a vector of
> arbitrary integer constants.
>
>
>
> Can we solve this problem, using your library(Java interface)? We need
> only integer solutions.

Dear Vladimir,

Since you indicate here that you only use equalities and only require 
integer solutions, the Grid domain provides almost what you want.
This domain captures any regular lattice of points that can be defined by 
a set of linear congruence relations. In particular, equalities are 
represented as congruences whose modulus is 0 and non-relational 
congruences with modulus 1 can represent the condition that the variables 
are integral.

The congruence representation can be converted to the a (grid) generator 
representation which, in the case you describe above where the initial 
equalities are homogeneous, will contain the origin point and a set of 
parameters whose coefficients are in a triangular form.

The interface for Grids (for all the supported languages including Java) 
is very similar to that for Polyhedra and allows for the addition of 
equality constraints using add_constraint() and add_constraints(). To 
specify that the variables only take integer values, you have to add a 
congruence "X = 0 modulo 1" for each variable X.

To obtain the matrix "U", after building the grid, use 
minimized_grid_generators() to obtain the grid generator system that 
represents this grid where the coefficients of the parameters will already 
be in triangular form.

I include below a simple Java test that builds a grid as indicated above 
from equality constraints and integer congruences and then prints the grid 
generators. The point is the origin while the coefficients of the 
parameters will form the matrix U.

     public static void test00() {
 	Variable W = new Variable(0);
 	Variable X = new Variable(1);
 	Variable Y = new Variable(2);
 	Variable Z = new Variable(3);
 	Linear_Expression le_0
             = new Linear_Expression_Coefficient(new Coefficient(0));
 	Linear_Expression le_W = new Linear_Expression_Variable(W);
 	Linear_Expression le_X = new Linear_Expression_Variable(X);
 	Linear_Expression le_Y = new Linear_Expression_Variable(Y);
 	Linear_Expression le_Z = new Linear_Expression_Variable(Z);
 	Linear_Expression lhs1
             = le_W.times(new Coefficient(2)).sum(le_X).subtract(le_Z);
 	Linear_Expression lhs2
             = le_X.sum(le_Y).subtract(le_Z.times(new Coefficient(5)));
  	Grid ph = new Grid(4, Degenerate_Element.UNIVERSE);
 	ph.add_constraint(new Constraint(lhs1,
 					 Relation_Symbol.EQUAL,
 					 le_0));
 	ph.add_constraint(new Constraint(lhs2,
                                          Relation_Symbol.EQUAL,
 					 le_0));
 	ph.add_congruence(new Congruence(le_W, le_0, new Coefficient(1)));
 	ph.add_congruence(new Congruence(le_X, le_0, new Coefficient(1)));
 	ph.add_congruence(new Congruence(le_Y, le_0, new Coefficient(1)));
 	ph.add_congruence(new Congruence(le_Z, le_0, new Coefficient(1)));
         System.out.println(ph.congruences().toString());
         System.out.println(ph.minimized_grid_generators().toString());
     }

This will print

2*A + B - D = 0, B + C - 5*D = 0, A = 0 (mod 1), B = 0 (mod 1), C = 0 (mod 
1), D = 0 (mod 1)
p(0), q(A + 10*C + 2*D), q(B + 4*C + D)

where p(0) is the origin
and q(...) are the parameters

Therefore the matrix of coefficients of the parameters in this case is:
1, 10, 0, 2
0,  1, 4, 1
0,  0, 0, 0
0,  0, 0, 0

I guess this is not quite the format you want but if the variables were 
read in reverse order, it would be upper triangular. Otherwise a further 
matrix operation would be needed to convert it to the right format.

This solution uses the grids. If you also need to represent inequalities, 
then the grids cannot be used and the above proposal will not help.

All the best,
   Pat