The pure integer programming problem is to find a vector X that

Minimizes C X

(1) subject to A X = b,

and X (GREATERTHEQ) 0 integer.

Let P be the convex hull of the solutions to (1). If one is able to discover a linear system

(2) (alpha) X (GREATERTHEQ) (beta)

which is sufficient to define P, then linear programming provides an optimality criterion.

The inequalities in a minimal system (2) defining P are called facet-inducing inequalities.

The main concern of the subadditive approach to integer programming is the characterization of the facet-inducing inequalities which define the convex hull of solutions for a large class of integer programs. It covers in a unified framework pure integer programs with bounded variables, packing and covering programs and, also, Gomory's group program.

We extend this subadditive approach in some new directions for the group case.

We first analyse general group polyhedra and the key role played by group homomorphisms. We find a new class of homorphic extensions. A main new theorem provides a characterization of facet-inducing inequalities for subpolyhedra P(G, N, b) with zero value on a subset of N. Thereby, generalizing a theorem of Gomory for which N = G. This result is used extensively in the sequal.

Secondly, we attack the question of finding the facets of the subpolyhedron from the ones of its master polyhedron, in the group cse nC(,2) (direct sum of the cyclic group of order 2). We also characterize the solutions in a face (Meiko Kwan's theorem) and adjacency of vertices.

We, next, show how these results can be used effectively to give a complete facet description of the Postman polyhedra (a class of subpolyhedra P(nC(,2), N, b) which generalize the well known Chinese postman polyhedron). In this development we give new properties satisfied by the solutions of Postman problems. It leads us to a property of {0, 1} matrices that we call the "Postman property". We show that every "graphic matroid" has a matrix representation with this property.

Finally, we give tables of facet-inducing inequalities for the smallest packing and covering master polyhedra.