Nondegeneracy of Polyhedra and Linear Programs

This paper deals with nondegeneracy of polyhedra andlinear programming (LP) problems. We allow for the possibilitythat the polyhedra and the feasible polyhedra of the LPproblems under consideration be non-pointed.(A polyhedron is pointed if it has a vertex.) With respect to a given polyhedron, we consider two notions ofnondegeneracy and then provide several equivalent characterizationsfor each of them. With respect to LP problems, we study thenotion of constant cost nondegeneracy first introduced byTsuchiya [25] under a different name, namelydual nondegeneracy. (We do not follow this terminology sincethe term dual nondegeneracy is already used to refer to a relatedbut different type of nondegeneracy.) We show two main results about constant cost nondegeneracy of an LP problem.The first one shows that constant cost nondegeneracy of an LPproblem is equivalent to the condition that the union of all minimal faces of the feasible polyhedron be equal to the set of feasible points satisfying a certain generalized strict complementarity condition.When the feasible polyhedron of an LP is nondegenerate,the second result showsthat constant cost nondegeneracy is equivalent to the conditionthat the set of feasible points satisfying the generalizedcondition be equal to the set of feasible points satisfyingthe same complementarity condition strictly.For the purpose of giving a preview of the paper,the above results specialized to the context of polyhedra and LP problems in standard form are described in the introduction.