Every convex polyhedron has two representations, one as
the intersection of finite halfspaces and the other
as Minkowski sum of the convex hull of finite points
and the nonnegative hull of finite directions. These are
called H-representation and V-representation, respectively.
Naturally there are two basic Polyhedra formats, H-format for H-representation and V-format for V-representation. These two formats are designed to be almost indistinguishable, and in fact, one can almost pretend one for the other. There is some asymmetry arising from the asymmetry of two representations.
First we start with the H-representation.
Let be an
matrix, and let
be a column
-vector.
The Polyhedra format (H-format ) of
the system
of
inequalities in
variables
is
various comments | ||
H-representation | ||
(linearity ![]() ![]() ![]() ![]() ![]() |
||
begin | ||
![]() |
![]() |
numbertype |
![]() |
![]() |
|
end | ||
various options |
where numbertype can be one of integer, rational or real.
When rational type is selected, each component
of and
can be specified by the usual integer expression
or by the rational expression ``
'' or ``
'' where
and
are arbitrary long positive integers (see the example
input file rational.ine). In the 1997 format,
we introduced ``H-representation'' which must appear
before ``begin''.
There was one restriction in the old polyhedra format
(before 1997): the last
rows must determine
a vertex of
. This is obsolete now.
In the new 1999 format, we added the possibility of specifying linearity.
This means that
for H-representation, some of the input rows can be specified as equalities:
for all
.
The linearity line may be omitted if there are no equalities.
Option lines can be used to control computation of a specific program. In particular both cdd and lrs use the option lines to represent a linear objective function. See the attached LP files, samplelp*.ine.
Next we define Polyhedra V-format. Let be
represented by
gerating points and
generating directions (rays) as
.
Then the Polyhedra V-format for
is
various comments | ||
V-representation | ||
(linearity ![]() ![]() ![]() ![]() ![]() |
||
begin | ||
![]() |
![]() |
numbertype |
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
end | ||
various options |
Here we do not require that
vertices and rays are listed
separately; they can appear mixed in arbitrary
order.
Linearity for V-representation specifies a subset of generators
whose coefficients are relaxed
to be free: for all
, the
th generator (
or
whichever is the
th generator) is a free generator.
This means for each such a ray
,
the line generated by
is in the polyhedron,
and for each such a vertex
, its coefficient is no longer nonnegative
but still the coefficients for all
's must sum up to one.
When the representation statement, either ``H-representation'' or ``V-representation'', is omitted, the former ``H-representation'' is assumed.
It is strongly suggested to use the following rule for naming H-format files and V-format files: