[PPL-devel] Zero-dimensional constraint systems.

[Enea Zaffanella]

In various places in the source files, we have assertions requiring that
matrices (of constraints and generators) have a number of columns <> 1.
These assertions can be violated by the following code, that should be
considered legal, since it builds the simplest form of an always-flase
constraint:

  LinExpression e0 = LinExpression(0);
  LinExpression e1 = LinExpression(1);
  Constraint c0(e0 == e1);
  // Built the always-false 0-dim constraint c0, that is 0 = 1.
  ConSys cs;
  cs.insert(c0);
  Polyhedron ph(cs);

error6: ../../ppl/src/Polyhedron.cc:155:
Parma_Polyhedra_Library::Polyhedron::Polyhedron
(Parma_Polyhedra_Library::ConSys &): Assertion `cs.num_columns() != 1'
failed.

There are three ways to solve such a situation:

1. We prevent the creation of 0-dim constraints, throwing an exception
when executing
     Constraint c0(e0 == e1);

2. we force the creation of a dimension when building constraints (e.g.,
we force c0 to be the 1-dim constraint ``0*Variable(0) == 1''). This is
not a very clean solution, since in the code above the user thinks ph to
be a 0-dim polyhedron. By silently converting it to a 1-dim polyhedron,
we probably trigger some dimension-incompatibility problems later in the
code.

3. we remove all assertions of this kind. Non-empty 0-dim constraint
systems will be legal and will contain constraints that are either
always false (like the one above) or always true (like the positivity
constraint 1 >= 0). Note that the representation of the empty polyhedron
needs not to be changed, i.e., we just look at the status flag and do
not need to explicitly insert have a matrix for the always false
constraint.

The easiest-to-implement solution is 1.
The cleanest one, in my opinion, is solution 3. Here are some other
reasons:

a) consider an 0-dim empty polyhedron ph; if a user invokes the method
ph.constraints(), the user will obtain an exception. If a 0-dim
constraint can be built, the implementation can return a constraint
system including it.

b) the same considerations can be extended to systems of generators. The
following code build the 0-dim vertex (the only point of the 0-dim
universe polyhedron):

  LinExpression e0 = LinExpression(0);
  Generator g0(vertex(e0));
  // Built the 0-dim vertex.
  GenSys gs;
  gs.insert(g0);
  Polyhedron ph(gs);

error6: ../../ppl/src/Polyhedron.cc:183:
Parma_Polyhedra_Library::Polyhedron::Polyhedron
(Parma_Polyhedra_Library::GenSys &): Assertion `gs.num_columns() != 1'
failed.

Also, we now throw an exception when we inkoke ph.generators() for a
0-dim universe polyhedron. In constrast, we could just return the system
of generators containing the 0-dim vertex.
It seems to me that, when inserting an n-dimension (n > 0) generator in
a 0-dim system of generators,
the 0-dim vertex (if present in the system) would be correctly
dimension-expanded to the origin of the space \Rset^n.

Is anyone foreseeing other problems for such a change ?


--
Enea Zaffanella
Dipartimento di Matematica - Universita' di Parma
Via M. D'Azeglio, 85/A
I 43100 - PARMA (Italy)
Tel: +39 0521 032317 Fax: +39 0521 032350