The Structure of Integer Programs under the Hermitian Normal Form

This paper discusses the structure of integer programming under the Hermitian normal form. It shows that this formulation is akin to the simplex technique for linear programming in that there is a basis and a basic solution associated with each Hermitian normal matrix, and that this Hermitian basis forms a set of natural cutting planes; these cutting planes are strong in that they provide facets for at least one of the corner polyhedra associated with a linear programming basis B. In addition, the cofactors of the Hermitian basis are group elements under a homomorphism of the original group structure. The Hermitian basis also allows one to characterize the values of the right-hand side for which the present solution is feasible. Finally, for an optimal Hermitian basis, one can perform sensitivity analysis on the cost coefficients.