Polyhedra H- and V-Formats (Version 1999)

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 $A$ be an $m \times d$ matrix, and let $b$ be a column $m$-vector. The Polyhedra format (H-format ) of the system $\; b - A x \ge {\bf0}\;$ of $m$ inequalities in $d$ variables $x =(x_1, x_2, \ldots, x_d)^T$ is

various comments
H-representation
(linearity $t\;$ $i_1\;$ $i_2\;$ $\ldots$ $\;i_t$)
begin
$m$	$d+1$	numbertype
$b$	$-A$
end
various options

where numbertype can be one of integer, rational or real. When rational type is selected, each component of $b$ and $A$ can be specified by the usual integer expression or by the rational expression ``$p / q$'' or ``$-p / q$'' where $p$ and $q$ 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 $d$ rows must determine a vertex of $P$. 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: $b_{i_j} - A_{i_j} = 0 \;$ for all $j=1,2, \ldots, t$. 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 $P$ be represented by $n$ gerating points and $s$ generating directions (rays) as $P = conv(v_1,\ldots,v_n) + nonneg(r_{n+1},\ldots,r_{n+s})$. Then the Polyhedra V-format for $P$ is

various comments
V-representation
(linearity $t\;$ $i_1\;$ $i_2\;$ $\ldots$ $\;i_t$ )
begin
$n+s$	$d+1$	numbertype
$1$	$v_1$
$\vdots$	$\vdots$
$1$	$v_n$
$0$	$r_{n+1}$
$\vdots$	$\vdots$
$0$	$r_{n+s}$
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 $j=1,2, \ldots, t$, the $k=i_j$th generator ($v_{k}$ or $r_k$ whichever is the $i_j$th generator) is a free generator. This means for each such a ray $r_k$, the line generated by $r_k$ is in the polyhedron, and for each such a vertex $v_k$, its coefficient is no longer nonnegative but still the coefficients for all $v_i$'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:

(a)

use the filename extension ``.ine'' for H-files (where ine stands for inequalities), and

(b)

use the filename extension ``.ext'' for V-files (where ext stands for extreme points/rays).