# Bounds on the number of vertices of perturbed polyhedra

Paul Armand

► To cite this version:

Paul Armand. Bounds on the number of vertices of perturbed polyhedra. Annals of Operations Research, 1993, 47, pp.249-269. 10.1007/BF02023098. hal-00110668

HAL Id: hal-00110668

https://hal.science/hal-00110668v1

Submitted on 17 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Bounds on the number of vertices of perturbed polyhedra

Paul Armand

Département de Mathématiques, Faculté des Sciences de Limoges,
123, rue Albert Thomas, 87060 Limoges Cédex, France

Finding the incident edges to a degenerate vertex of a polyhedron is a non-trivial problem. So pivoting methods generally involve a perturbation argument to overcome the degeneracy problem. But the perturbation entails a bursting of each degenerate vertex into a cluster of nondegenerate vertices. The aim of this paper is to give some bounds on the number of these perturbed vertices.

**Keywords:** Convex polytopes, degeneracy, linear programming, simplex method.

## 1. Introduction

Degeneracy of a polyhedron is a source of difficulties for both theory and computation in mathematical programming. This phenomenon may be avoided by considering slight perturbations of degenerate polyhedra, that is, by approximating the degenerate polyhedron by a nondegenerate one. This method was applied to a well-known proof of finiteness of the simplex algorithm [5, 7]. Another application is a connectedness result of Gal [9-11, 15] concerning graphs of bases associated to the degenerate vertices of a polyhedron, which had induced an algorithm for finding all incident edges to a degenerate vertex [20]. So the pivoting methods which require the search of all or part of the incident edges to a given vertex, for example the vertex enumeration methods (see for example [3, 21] and a survey in [8]), the linear multiobjective methods (see for example [1] and references given therein), frequently need a perturbation argument such that the polyhedron is simple. But the perturbed polyhedron has generally many more vertices than the initial polyhedron. Here we give one lower and two upper bounds on the number of vertices of perturbed polyhedra. In our study, we resolutely adopt a geometric viewpoint. This permits the use of some basic facts in the field of convex polytopes as well as a strong result of Klee [19] concerning the number of vertices of unbounded polyhedra (see also [2]).

This paper is organized as follows. In section 2 we extend the right hand side perturbation principle by introducting a perturbation function of a polyhedron and we define the corresponding perturbed polyhedron. We show that, for a given function, the family of perturbed polyhedra belongs to an equivalence class under the
combinatorial polyhedral equivalence relation. The perturbation entails a "bursting" of each degenerate vertex into several nondegenerate vertices, called the broken-vertices. From an algorithmic viewpoint, a perturbation corresponds to a choice of lexicographic order on the set of bases that selects certain bases associated with a degenerate vertex.

In section 3 we establish a connection between the redundant constraints in a representation of a polyhedron and the facets of the perturbed polyhedron. We show that for any representation of a full-dimensional polyhedron, there exist perturbation functions which preserve redundancy. In this case, the initial polyhedron and the perturbed polyhedron have the same number of facets.

Section 4 is devoted to the minimum and maximum number of broken-vertices. We show that this number can be equal to the number of vertices of some particular unbounded polyhedra.

## 2. Perturbed polyhedra

Here we call a *polyhedron* a convex subset of $\mathbb{R}^n$ defined by the intersection of a finite number of closed halfspaces. We shall say that a polyhedron is *full-dimensional* if it is *n*-dimensional. A *face* of a polyhedron $P$ is the empty set $\emptyset$, $P$ itself, or the intersection of $P$ with a supporting hyperplane. The faces $\emptyset$ and $P$ are called *improper faces*, while the others are called *proper*. *Vertices* and *edges* of a polyhedron are respectively 0- and 1-dimensional faces. A *facet* is a maximal proper face. The *recession cone* of a polyhedron $P$ is the polyhedral cone defined by

$$ \mathrm{rec} P = \{y : x + y \in P, \text{ for all } x \in P\}. $$

A *pointed polyhedron* is a polyhedron with a line-free recession cone (i.e., $\mathrm{rec} P \cap -\mathrm{rec} P = \{0\}$). A polyhedron is pointed if and only if its vertex set is non-empty. Throughout this paper the polyhedra are implicitly assumed to be pointed. A bounded polyhedron (i.e., $\mathrm{rec} P = \{0\}$) is called a *polytope* and it is the convex hull of its vertices. A *d*-dimensional polyhedron is said to be *simple* if it is pointed and if its vertices are incident to precisely *d* edges, or equivalently, to precisely *d* facets. Two pointed polyhedra $P$ and $Q$ are said to be *equivalent* if there exists a one-to-one correspondence $\phi$ between the set of all faces of $P$ and the set of all faces of $Q$ such that $\phi$ preserves the inclusion. Equivalently, $P$ and $Q$ are equivalent if their face-lattices are isomorphic. For background material on the theory of polyhedra see [4, 17].

Any nonempty pointed polyhedron in $\mathbb{R}^n$, defined by a set of $n+m$ linear inequalities, can be transformed to an equivalent polyhedron described in the *standard form* of the feasible region of a linear program, namely

$$ P = \{x \in \mathbb{R}^n : Ax \leq b, x \geq 0\}, \qquad (2.1) $$

where $A$ is an $m \times n$-matrix and $b$ is an $m$-column vector with nonnegative
components. Such a transformation can be achieved by exactly *n* pivots of the Gaussian elimination method and by a Phase I linear programming (see for example [8]). Adding slack variables, the above representation can be transformed to the canonical form,

$$ \bar{P} = \{y \in \mathbb{R}^{n+m} : \bar{A}y = b, y \ge 0\}, \quad (2.2) $$

with $\bar{A} = (A, I)$, $I$ being the $m \times m$ identity matrix. A basis $B$ is a regular $m \times m$-submatrix of $\bar{A}$. Using the basic-nonbasic partition, $\bar{A}$ becomes $(B, N)$, so if $\bar{A}y = b$ then $y_B = B^{-1}b - B^{-1}Ny_N$. With a basis $B$ we associated the following set

$$ K(B) = \{z \in \mathbb{R}^m : B^{-1}z \ge 0\}. $$

It is a full-dimensional polyhedral cone, thus it is a closed convex cone with a non-empty interior defined by

$$ \mathrm{int} K(B) = \{z \in \mathbb{R}^m : B^{-1}z > 0\}. $$

The basis $B$ is feasible (with respect to $P$) if $b \in K(B)$. In this case, the vector $y$ such that $(y_B, y_N) = (B^{-1}b, 0)$ is a vertex of $\bar{P}$, and the vector $x$ such that $y = (x, b - Ax)$ is a vertex of $P$. The basis $B$ is said to be degenerate if $b$ lies on the boundary of $K(B)$. In this case we denote by $\sigma$ the number of null components of $B^{-1}b$ and say that the associated vertex is $\sigma$-degenerate [10, 20]. Equivalently, a vertex $x$ is $\sigma$-degenerate if and only if precisely $n + \sigma$ constraints are tight at $x$. Recall that a vertex is non-degenerate if and only if a unique basis is associated with it, on the other hand, at least 2 and at most $(n+\sigma)$ bases may define the same $\sigma$-degenerate vertex. A polyhedron is said to be degenerate if at least one vertex is degenerate. Denote by $\mathcal{B}$ the set of feasible bases $(B^{-1}b \ge 0)$ and by $\mathcal{B}'$ the one of infeasible bases $(B^{-1}b \not\ge 0)$. We define the stability cone of polyhedron $P$ by

$$ S(A, b) = \bigcap_{B \in \mathcal{B}} K(B) \setminus \bigcup_{B \in \mathcal{B}'} K(B), \quad (2.3) $$

so it is the intersection of all the “feasible cones” with all the complements of “infeasible cones”. Since $b \in S(A, b)$, it is a nonempty cone but not necessarily convex. The following two conditions are equivalent.

* $P$ (or $\bar{P}$) is a nondegenerate polyhedron.

* $b \in \mathrm{int} S(A, b)$.

### LEMMA 2.1

If the polyhedron $P$ defined by (2.1) is nondegenerate, then for all $c \in \mathrm{int} S(A, b)$, the polyhedron $\{x : Ax \le c, x \ge 0\}$ is equivalent to $P$.
## Proof

Let $Q = \{x : Ax \leq c, x \geq 0\}$. For convenience we use the canonical representation of $P$ and $Q$ and prove that $\bar{P}$ and $\bar{Q}$ are equivalent polyhedra. Let $B$ be any basis. If $B^{-1}b \geq 0$ then $c \in K(B)$, which implies $B^{-1}c \geq 0$. Conversely, if $B^{-1}b \neq 0$ then $c \notin K(B)$, which implies $B^{-1}c \neq 0$. Therefore a basis is feasible with respect to $P$ if and only if it is feasible with respect to $Q$, whence $S(A, b) = S(A, c)$. As $c$ is an interior point of $S(A, c)$, the polyhedron $\bar{Q}$ is nondegenerate. Now, let $F$ be a non-empty face of $\bar{P}$ and let $B$ be a basis associated with a vertex of $F$. By the non-degeneracy assumption, there exists a unique index subset $I$ of the nonbasic index set such that

$$F = \{y \in \bar{P} : y_i = 0, \text{ for all } i \in I\},$$

(see for example [23]). The basis $B$ is also associated with a vertex of polyhedron $\bar{Q}$ and the set $\{y \in \bar{Q} : y_i = 0, \text{ for all } i \in I\}$ determines a unique face of $\bar{Q}$. Obviously, this correspondence between the faces of $\bar{P}$ and $\bar{Q}$ preserves the inclusion and because of symmetry of $c$ and $b$, it is one-to-one. $\square$

The perturbation principle consists in moving the vector $b$ such that it never lies on the boundary of any cone $K(B)$. Denote by $x^T$ the transpose vector of $x$. Let $h^T = (h_1, \dots, h_m)$, where each $h_i$ is a continuous function from $[0, +\infty)$ to $\mathbb{R}$, such that $h(0) = 0$ and, for any hyperplane $H$ of $\mathbb{R}^m$, there is at most a finite number of $t > 0$ such that $h(t) \in H$. Such a function will be called a *perturbation function*.

## LEMMA 2.2

Let $z$ be a nonzero vector of $\mathbb{R}^m$. Then there exists $\epsilon > 0$ such that for all $t \in (0, \epsilon]$, the scalar product $\langle z, h(t) \rangle$ has constant sign.

## Proof

Suppose that the continuous function $t \to \langle z, h(t) \rangle$, defined for $t \geq 0$, changes sign in any neighborhood of $t = 0$. Then there exists a nonfinite number of $t > 0$ such that $h(t) \in \{x : \langle z, x \rangle = 0\}$, which contradicts the definition of a perturbation function. $\square$

From the standard form (2.1) of polyhedron $P$ we define the family of perturbed polyhedra

$$P(h(t)) = \{x \in \mathbb{R}^n : Ax \leq b + h(t), x \geq 0\}. \quad (2.4)$$
Throughout the sequel it will be implicitly assumed that the perturbed polyhedra are nonempty. Usually the perturbation function is defined by $h(t) = (t, t^2, \dots, t^m)^T$, see [6, 16, 18]. (Other perturbation functions are used in the literature, see [5, 24, 26]).

### PROPOSITION 2.3

There exists $\epsilon > 0$ such that $[P(h(t))]_{0<t\le\epsilon}$ is a family of equivalent nondegenerate polyhedra.

#### Proof

It suffices to show that there exists $\epsilon > 0$ such that any basis is either feasible and nondegenerate with respect to $P(h(t))$ for all $t \in (0, \epsilon]$, or infeasible for all $t \in (0, \epsilon]$. Indeed, for all $t \in (0, \epsilon]$, the vector $b+h(t)$ will be an interior point of the stability cone $S(A, b+h(\epsilon))$, from which the conclusion will follow, cf. lemma 2.1.

Let $B$ be a basis. Every component of $B^{-1}(b+h(t))$ is the scalar product of $h(t)$ with a row vector of $B^{-1}$. By lemma 2.2, there exists $\epsilon(B) > 0$ such that the basis $B$ is either feasible and nondegenerate or infeasible. Then we take $\epsilon$ equal to the smallest $\epsilon(B)$ over all of the bases $B$. $\square$

Throughout the sequel we shall denote by $P(h)$ the perturbed polyhedron. It will indicate an element of this equivalence class. This result shows that the combinatorial structure of a perturbed polyhedron is independent of the value of $t > 0$ in a neighborhood of 0. This fact appears in the proof of the equivalence of the perturbation method with the lexicographic pivoting rule of the simplex algorithm, see for example [6, chap. 10; 18, chap. 6], where it is shown that it is never necessary to compute the perturbation explicitly.

Another well-known geometrical interpretation of the perturbation is the following. A vertex of $P$ is degenerate if more than $n$ bounding hyperplanes pass through the vertex. Perturbing $P$ consists in translating each hyperplane parallel to itself, such that there is no degeneracy. This entails a "bursting" of a degenerate vertex into a cluster of nondegenerate vertices. If $x(h)$ is a vertex of the perturbed polyhedron then the basis associated with $x(h)$ is also associated with a vertex $x$ of the initial polyhedron. In this case $x(h)$ will be called a *broken-vertex* of $x$. Note that when $h(t) = (t, t^2, \dots, t^m)^T$ the broken-vertices correspond one-to-one to the lexicographic bases.

### PROPOSITION 2.4

For any vertex $x$, the set of broken-vertices of $x$ is nonempty.
### Proof

Let $x^0$ be a vertex of $P$ (2.1) and let $c$ be a normal vector to a supporting hyperplane of $P$ such that, for all $x \in P x^0$, $\langle c, x \rangle > \langle c, x^0 \rangle$. Since the polyhedra $P$ and $P(h)$ have the same recession cone, namely the set $\{x: Ax \le 0, x \ge 0\}$, the problem $\min \{\langle c, x \rangle, x \in P(h)\}$ has at least one minimal solution. Therefore, there exists a basis $B$ associated with a vertex of $P(h)$ which satisfies the dual-optimality condition, namely $\bar{c}_N - \bar{c}_B B^{-1} N \ge 0$, where $\bar{c} = (c, 0) \in \mathbb{R}^{n+m}$. Note that this condition does not depend on the perturbation, thus the basis $B$ is also dual-optimal with respect to the problem $\min \{\langle c, x \rangle, x \in P\}$. But $x^0$ is the unique solution of the problem, therefore the basis $B$ is necessarily associated with $x^0$. $\square$

The following result is fundamental for establishing the bounds of theorem 4.4. Given a nondegenerate polyhedron $P$, it allows us to produce a polyhedron $Q$ with a degenerate vertex such that the perturbed polyhedron $Q(h)$ is equivalent to $P$.

### THEOREM 2.5

Let $P = \{x: Ax \le b, x \ge 0\}$ be a nondegenerate polyhedron and let $Q = \{x: Ax \le 0, x \ge 0\}$ be the recession cone of $P$. Then there exists a perturbation function $h$ such that $Q(h)$ and $P$ are equivalent polyhedra.

### Proof

Without loss of generality we may suppose that $P = \{x: Ax \le e, x \ge 0\}$, where $e = (1, \dots, 1)^T$. Let $K = S(A, e)$ be the stability cone (2.3) associated with $P$. By the nondegeneracy assumption, $e$ is an interior point of $K$. Denote by $(e_i)$ the canonical basis of $\mathbb{R}^m$. Let us choose $\eta > 0$ sufficiently small such that the vectors $c_i = e + \eta e_i$, $i \in \{1, \dots, m\}$, are interior points of $K$. Consider the perturbation function $h(t) = \sum_{i=1}^m t^i c_i$. Clearly $h(t) \in \text{int } K$ for all $t > 0$, and therefore the perturbed polyhedron $Q(h)$ is equivalent to $P$ (cf. lemma 2.1). $\square$

## 3. Stability of redundancy

Let $Q$ be a polyhedron in $\mathbb{R}^n$ with the following representation,

$$Q = \bigcap_{i=1}^{P} K_i,$$

where each $K_i$ is a closed halfspace (also named constraint) with bounding hyperplane $H_i$. Throughout the sequel it will be assumed that no two constraints of a
representation of a polyhedron are identical. The constraint $K_r$ is said to be *redundant* if

$$Q = \bigcap_{i \neq r} K_i.$$

The redundancy is said to be *weak* if $Q \cap H_r \neq \emptyset$, in the other case it is *strong*. It is well-known that if $K_r$ is weakly redundant, then all the vertices of $Q$ contained in $H_r$ are degenerate (see for example [13]). Given a vector $y$ and a scalar number $\alpha$, we shall denote by $\{\langle y \rangle \le \alpha\}$ the closed halfspace $\{x : \langle y, x \rangle \le \alpha\}$. Given a perturbation function $h$, the standard representation (2.1) of polyhedron $P$ and the representation (2.4) of perturbed polyhedron $P(h)$ may be rewritten in the following form,

$$P = \bigcap_{i=1}^{m} \{\langle a_i \rangle \le b_i\} \cap \bigcap_{i=1}^{n} \{\langle e_i \rangle \ge 0\} \quad (3.1)$$

and

$$P(h) = \bigcap_{i=1}^{m} \{\langle a_i \rangle \le b_i + h_i\} \cap \bigcap_{i=1}^{n} \{\langle e_i \rangle \ge 0\}, \quad (3.2)$$

where $(a_i)$ are the row vectors of the matrix $A$ and $(e_i)$ is the canonical basis of $\mathbb{R}^n$.

Note that redundancy is always strong for the representation (3.2) since the perturbed polyhedron is nondegenerate.

## PROPOSITION 3.1

If a constraint is nonredundant for the representation (3.1) of $P$, then the corresponding perturbed constraint is nonredundant for the representation (3.2) of $P(h)$.

### Proof

Denote by $K_i$ the halfspaces in representation (3.1) and by $K_i(h)$ those in (3.2). Suppose that $K_r(h)$ is redundant, then

$$P(h) = \bigcap_{i \neq r} K_i(h) \subset K_r(h).$$
But when $h$ tends to zero we have,

$$P = \bigcap_{i \neq r} K_i \subset K_r,$$

whence the redundancy of $K_r$.

<figure><img src="image_2.png" /></figure>

We shall say that a perturbation function *preserves redundancy* if for any redundant constraint in (3.1) the corresponding perturbed constraint remains redundant in (3.2). Such a perturbation function will be called *stable*.

**PROPOSITION 3.2**

Any perturbation function preserves strong redundancy.

*Proof*

Let $K$ be a constraint of a representation of polyhedron $P$, and let $H$ be its bounding hyperplane. Suppose that the perturbed constraint is not strongly redundant. Then its bounding hyperplane $H(h)$ is a supporting hyperplane of $P(h)$. Therefore there exists a vertex $x(h)$ of $P(h)$ contained in $H(h)$. When $h$ tends to zero, $x(h)$ tends to a vertex $x(0)$ of $P$ contained in $H$, then $K$ is not strongly redundant for the representation of $P$.

<figure><img src="image_3.png" /></figure>

On the other hand, a weakly redundant constraint can be transformed into a nonredundant one for the perturbed polyhedron. Before establishing the next result, note that the deletion of one weakly redundant constraint can make other redundant constraints nonredundant. However, if a polyhedron is full-dimensional and no two constraints of its representation are identical, then all the redundant constraints can be deleted at the same time, without changing the polyhedron. Indeed, under the above assumptions there exists a one-to-one correspondence between the facets and the nonredundant constraints defining $P$ (3.1) (see for example [4, theorem 8.2]).

**THEOREM 3.3**

For any standard representation of a full-dimensional polyhedron, there exists a stable perturbation function. In this case, the polyhedron and the perturbed polyhedron have the same number of facets.

*Proof*

It follows from the above remark that for a stable perturbation function the two polyhedra have the same number of facets.
We may assume that the $n$ nonnegativity constraints $\{\langle e_i \rangle \ge 0\}$ in (3.1) are nonredundant. Indeed, since $P$ is $n$-dimensional, there exist at least $n$ facets containing any vertex $x$ of $P$. From among these facets, let us choose $n$ of them such that their normal vectors are linearly independent (such a choice exists, otherwise the dimension of $P$ would be smaller than $n$). All these facets are defined by the intersection of $P$ with the bounding hyperplanes of $n$ nonredundant constraints. This choice corresponds to the choice of a basis associated with the vertex $x$. Denote by $B$ this basis. Using the canonical form of $P$ and the basic-nonbasic partition, we can write $P$ in the following equivalent form,

$$P(B) = \{x \in \mathbb{R}^n : B^{-1}Nx \le B^{-1}b, x \ge 0\}.$$

The transformation from $P$ to $P(B)$ maps the vertex $x$ onto the origin of $\mathbb{R}^n$, and the $n$ preceding constraints are mapped onto the nonnegativity constraints of $P(B)$. Since the redundancy is invariant under a change of basis, we then have a polyhedron equivalent to $P$ with nonredundant nonnegativity constraints.

Now, assume that the constraints $\{\langle a_i \rangle \le b_i\}, i = 1, \dots, r$, are weakly redundant. Define the perturbation function as follows: $h_i(t) = t^i$ ($t$ to the $i$th power). Note that $h$ has only positive components, so the constraints are moved away from any interior point of polyhedron $P$. Let

$$Q(h) = \bigcap_{i=r+1}^{m} \{\langle a_i \rangle \le b_i + h_i\} \cap \bigcap_{i=1}^{n} \{\langle e_i \rangle \ge 0\}.$$

By assumption and from the above mentioned remark, all the redundant constraints can be deleted at the same time in (3.1), hence $P = Q(0)$. Now it suffices to show that $Q(h)$ is included in $\cap_{i=1}^r \{\langle a_i \rangle \le b_i + h_i\}$. In order to do this, we shall show that

$$Q(h) \subset P + \alpha h_{r+1} \mathbb{B}, \quad (3.3)$$

where $\mathbb{B}$ is the closed unit ball and $\alpha$ is a positive number. Indeed, as

$$\{\langle a_i \rangle \le b_i\} + \frac{h_i}{\|a_i\|} \mathbb{B} = \{\langle a_i \rangle \le b_i + h_i\}, \quad \text{for all } i = 1, \dots, m,$$

and

$$\lim_{t \to 0} \frac{h_{r+1}(t)}{h_i(t)} = 0, \quad \text{for all } i = 1, \dots, r,$$

then when $t$ tends to zero, $P + \alpha h_{r+1} \mathbb{B} \subset \{\langle a_i \rangle \le b_i + h_i\}$ for all $i = 1, \dots, r$. Actually, we shall show that the vertices $x(h)$ of $Q(h)$ verify

$$x(h) \in P + \alpha h_{r+1} \mathbb{B}, \quad (3.4)$$
which implies (3.3). let $x$ be a vertex of $P$ and let $x(h) \in Q(h)$ be a broken-vertex of $x$. As $Q(h)$ is nondegenerate and so $n$-dimensional, there are exactly $n$ constraints of $Q(h)$ which are tight at $x(h)$, say

$$ \begin{cases} \langle x(h), e_i \rangle = 0, & i \in I_0, \\ \langle x(h), a_j \rangle = b_j + h_j, & j \in J_0, \end{cases} $$

with $|I_0| + |J_0| = n$. If $J_0 = \emptyset$, then $x(h) = 0$ which implies $x = 0$. Now suppose that $J_0$ is nonempty. The system above can be written $Gx(h) = g(h)$, where $G$ is the $n \times n$-matrix with row vectors $e_i$ and $a_j$, and $g(h)$ is the corresponding column vector. Since $x(h)$ is a vertex, the matrix $G$ is invertible, hence $x(h) = G^{-1}g(h)$. Since $x(h)$ is a broken-vertex of $x$ it follows that $x = G^{-1}g(0)$. We then have

$$ \begin{aligned} \|x(h) - x\| &= \|G^{-1}(g(h) - g(0))\| \\ &\le \|G^{-1}\| \|g(h) - g(0)\| \\ &\le \alpha \|g(h) - g(0)\|, \end{aligned} $$

where $\alpha$ is an upper bound of $\|G^{-1}\|$ for all matrices $G$ corresponding to the vertices of $Q(h)$. Since the constraints which are tight at $x(h)$ are among those which are tight at $x$, and since $\lim_{t \to 0}(h_i(t)/h_{r+1}(t)) = 0$, for all $i = r+2, \dots, m$, it follows that $\|x - x(h)\| \le \alpha h_{r+1}$, which implies (3.4). $\square$

## 4. Bounds on the number of broken-vertices

Using a result of Klee about the number of vertices of a class of unbounded polyhedra [19, theorem 1], we derive some bounds for the number of broken-vertices of a degenerate vertex.

This study is motivated by an algorithm of Kruse [20, p. 97] which finds all adjacent vertices of a degenerate vertex of a polytope ("N-tree method"). Starting from a basic $B_0$ associated to a $\sigma$-degenerate vertex $x^0$ and using the lexicographic pivoting rule of Dantzig, Orden and Wolfe, the N-tree algorithm enumerates the whole set of lexicographic bases associated to $x^0$ (that is, the bases which can be found from $B_0$ by means of a finite sequence of "lexicographic pivoting operations"). Kruse emphasizes that the number of lexicographic bases depends on the starting basis $B_0$ and on the arrangement of rows in the corresponding initial simplex tableau. He conjectures that there exists a starting basis $B_0$ and an arrangement of rows such that this number is not greater than $r/\sigma$, where $r$ is the number of feasible bases associated to the $\sigma$-degenerate vertex $x^0$. Since the lexicographic variant is formally equivalent to the right hand side perturbation method, the conjecture can be rephrased as follows. There exists a perturbation function such that the number of broken vertices of $x^0$ is not greater than $r/\sigma$. The following
example invalidates the conjecture in the particular case of a polytope which is not full-dimensional.

EXAMPLE 4.1

Consider the polytope

$$
P = \{x \in \mathbb{R}^n : Ix \le b, x \ge 0\}, \quad n \ge 3,
$$

where *I* is the identity matrix of *R*ⁿ and *b*ᵀ = (1, 0, ..., 0). Let *x* be a point of *P*, then

$$
\left.
\begin{array}{l}
x_1 \le 1, \\
x_i \le 0, \quad i = 2, \dots, n, \\
x_i \ge 0, \quad i = 1, \dots, n.
\end{array}
\right\}
$$

Thus *P* is the line segment [*x*⁰, *x*¹], where *x*⁰ = 0 and *x*¹ = *b*. These two vertices are both (*n* − 1)-degenerate since (2*n* − 1) constraints are tight at *x*⁰ or *x*¹. By means of slack variables, the above system is transformed onto

$$
[I, I]y = b, \quad y \ge 0,
$$

where $y^T = (x_1, \dots, x_{2n})$. There are precisely $2^n$ regular $n \times n$-submatrices of $[I, I]$, each of them corresponding to a feasible basis. Moreover, a variable $x_i, i \in \{1, \dots, n\}$, is basic if and only if $x_{n+i}$ is nonbasic. Therefore $2^{n-1}$ bases are associated with $x^0$ (resp. $x^1$). For any perturbation function (such that the perturbed polytope is nonempty), the perturbed polytope will be defined by

$$
Ix \le b(h), \quad x \ge 0,
$$

where $b(h)$ is an $n$-column vector with only positive components. Therefore the perturbed polytope is equivalent to the $n$-dimensional cube. Since the latter has $2^n$ vertices, the number of vertices of $P(h)$ is equal to the number of feasible bases. In particular, for any starting basis $B_0$ associated to $x^0$ and for any arrangement of rows in the initial simplex tableau, the number of bases enumerated by Kruse's $N$-tree algorithm is equal to the number of feasible bases associated to $x^0$.

<figure><img src="image_4.png" /></figure>

Following Klee [19] (see also [2]), for $3 \le d \le u < p$, a pair $(Q, G)$ is called a *polytope pair* of class $(d, p, u)$ provided $Q$ is a simple polytope of dimension $d$ with $p$ facets and $G$ is a facet intersecting precisely $u$ other facets of $Q$. Klee has shown that
the minimal and maximal numbers of vertices of $Q\G$ are respectively equal to

$$ \varphi(d, p, u) = (p - u - 2)(d - 1) + u, $$

$$ \phi(d, p, u) = \left( p - 1 - \left[ \frac{d+1}{2} \right] \right) + \left( p - 1 - \left[ \frac{d+2}{2} \right] \right) + d - u - 1, $$

where $[\alpha]$ stands for the greatest integer less than $\alpha$, and $()$ denotes the binomial coefficient.

### LEMMA 4.2

For $3 \le d \le u < p$,

$$ \phi(d, p, u) < \phi(d, p, u-1), \quad (4.1) $$

$$ \phi(d, p, u) < \phi(d, p+1, u), \quad (4.2) $$

$$ \phi(d, p, p-1) < \phi(d, p+1, p). \quad (4.3) $$

### Proof

$\phi(d, p, u) = \phi(d, p, u-1) - 1$, implying (4.1). To show (4.2), consider

$$ \psi(d, p) = \phi(d, p, u) - (d - u - 1). $$

Thus $\phi(d, p+1, u) - \phi(d, p, u) = \psi(d, p+1) - \psi(d, p)$, with

$$ \psi(d, p+1) = \left( p - \left[ \frac{d+1}{2} \right] \right) + \left( p - \left[ \frac{d+2}{2} \right] \right). $$

Since

$$ \binom{n}{k} = \frac{n}{n-k} \binom{n-1}{k}, $$

it follows that

$$ \psi(d, p+1) = q \left( p - 1 - \left[ \frac{d+1}{2} \right] \right) + r \left( p - 1 - \left[ \frac{d+2}{2} \right] \right), $$
with

$$q = \frac{p - \left[ \frac{d+1}{2} \right]}{p - \left[ \frac{d+1}{2} \right] - \left[ \frac{d}{2} \right]}$$

and

$$r = \frac{p - \left[ \frac{d+2}{2} \right]}{p - \left[ \frac{d+2}{2} \right] - \left[ \frac{d-1}{2} \right]}$$

For every integer $n$ we have:

$$n = \left\lfloor \frac{n}{2} \right\rfloor + \left\lceil \frac{n+1}{2} \right\rceil.$$

Whence

$$q = \frac{p - \left\lfloor \frac{d+1}{2} \right\rfloor}{p-d} \quad \text{and} \quad r = \frac{p - \left\lfloor \frac{d+2}{2} \right\rfloor}{p-d}.$$

As $q \ge r$, we deduce

$$\psi(d, p+1) \ge r\psi(d, p), \quad (4.4)$$

and finally,

$$r = \frac{p - \left\lfloor \frac{d+2}{2} \right\rfloor}{p-d} \ge \frac{p - \frac{d+2}{2}}{p-d} = 1 + \frac{d-2}{2(p-d)}.$$

But $d \ge 3$ and $p > d$, therefore $r > 1$.

To show (4.3) consider

$$\phi(d, p+1, p) = \psi(d, p+1) + d - p - 1 \ge r\psi(d, p) + d - p - 1,$$

the inequality be derived from (4.4). As $\psi(d,p) = \phi(d,p,p-1) - (d-p)$, we have

$$\phi(d, p+1, p) \ge r\phi(d, p, p-1) + k,$$

with $k = (d-p)(1-r) - 1$. Replace $r$ by its value, we have $k = [(d+1)/2] - 2$. Since $d \ge 3$, then $r > 1$ and $k \ge 0$, which implies (4.3). $\square$
### LEMMA 4.3

For $3 \le d \le u < p$,

$$ \varphi(d, p, u) < \varphi(d, p, u-1), $$

$$ \varphi(d, p, u) < \varphi(d, p+1, u), $$

$$ \varphi(d, p, p-1) < \varphi(d, p+1, p). $$

### Proof

$\varphi(d, p, u) = (d-1)(p-2) - u(d-2)$, thus $\varphi$ decreases with respect to $u$ and increases with respect to $p$. A simple calculation shows that $\varphi(d, p, p-1) = p-d$ and $\varphi(d, p+1, p) = p-d+1$. $\square$

We shall say that a constraint is weakly redundant at a vertex, provided the latter is contained in its bounding hyperplane.

### THEOREM 4.4

Let $x^0$ be a $\sigma$-degenerate vertex of a full-dimensional polyhedron of $\mathbb{R}^n$, $n \ge 3$. Let $0 \le r \le \sigma$ be the number of weakly redundant constraints at $x^0$. Then for any perturbation function, the minimum and maximum number of broken-vertices of $x^0$ are respectively equal to:

$$ \varphi(n, n + \sigma - r + 1, n + \sigma - r) = \sigma + 1 - r, $$

$$ \phi(n, n + \sigma + 1, n + \sigma - r) = \left( \left[ \frac{n}{2} \right] + \sigma \right) + \left( \left[ \frac{n-1}{2} \right] + \sigma \right) - (\sigma + 1 - r). $$

If the perturbation function is stable, then the maximum is equal to

$$ \phi(n, n + \sigma - r + 1, n + \sigma - r) = \left( \left[ \frac{n}{2} \right] + \sigma - r \right) + \left( \left[ \frac{n-1}{2} \right] + \sigma - r \right) - (\sigma + 1 - r). $$
## Proof

The proof is divided into two parts. Firstly, we establish the bounds; then we prove the existence of degenerate vertices for which the bounds are attained. Throughout the proof we denote by $v$ the number of broken-vertices of $x^0$.

*Establishing the bounds.* Since $x^0$ is a vertex of $P$, there exists a supporting hyperplane $\{\langle y \rangle = \alpha\}$ of $P$ such that

$$P \cap \{\langle y \rangle = \alpha\} = \{x^0\} \quad \text{and} \quad P \setminus \{x^0\} \subset \{\langle y \rangle < \alpha\}.$$

There exists $\beta < \alpha$ such that all vertices of $P$ except $x^0$ are contained in the open halfspace $\{\langle y \rangle < \beta\}$. Given a perturbation function $h(t)$, when $t$ tends to 0, the broken-vertices of a vertex $x$ of $P$ tend to $x$, thus we can choose the perturbed polyhedron such that the hyperplane $\{\langle y \rangle = \beta\}$ separates the broken-vertices of $x^0$ from the remaining vertices of $P(h)$. The set $Q = P(h) \cap \{\langle y \rangle \ge \beta\}$ is a polytope, indeed if $z$ is a recession direction of $Q$ then $\langle y, z \rangle \ge 0$. But $z$ is also a recession direction of $P$, then $\langle y, x^0 + z \rangle < \alpha$, whence $z = 0$. Moreover, $Q$ is of dimension $n$, the set $F = P(h) \cap \{y = \beta\}$ is a facet of $Q$ and any vertex of $Q$ is either a broken-vertex of $x^0$ or a vertex of the facet $F$ [4, theorem 11.11]. By proposition 3.1, a nonredundant constraint is also nonredundant for the perturbed polyhedron, so each facet of $P$ incident to $x^0$ corresponds to a facet of $Q$. Moreover, such a facet intersects the facet $F$. Therefore, $(Q, F)$ is a polytope pair of class $(n, p, u)$ with

$$p \ge p_1 = n + \sigma - r + 1 \quad \text{and} \quad u \ge p_1 - 1.$$

If the perturbation function preserves redundancy, it follows from theorem 3.3 that $p = p_1$ and $u = p_1 - 1$. So $v$ is bounded from above by $\phi(n, p_1, p_1 - 1)$, which gives the supremum for a stable perturbation function. Now for any perturbation function, a weakly redundant constraint at $x^0$ may define a facet of $Q$ and such a facet may or may not intersect the facet $F$. Thus

$$p \le p_2 = n + \sigma + 1 \quad \text{and} \quad u \le p - 1.$$

Therefore $v$ is bounded from below by

$$\min \{\varphi(n, p, u) : p_1 \le p \le p_2, p_1 - 1 \le u \le p - 1\}.$$

By virtue of lemma 4.3 we have

$$\varphi(n, p_1, p_1 - 1) \le \varphi(n, p_1 + 1, p_1) \le \dots \le \varphi(n, p_2, p_2 - 1),$$
and

$$ \varphi(n, p_1 + 1, p_1) \le \varphi(n, p_1 + 1, p_1 - 1), $$

...

$$ \varphi(n, p_2, p_2 - 1) \le \varphi(n, p_2, p_2 - 2) \le \dots \le \varphi(n, p_2, p_1 - 1). $$

It follows that the infimum is equal to $\varphi(n, p_1, p_1 - 1)$. Note that this case corresponds to a stable perturbation function.

In the same way, $v$ is bounded from above by

$$ \max \{ \phi(n, p, u) : p_1 \le p \le p_2, p_1 - 1 \le u \le p - 1 \}. $$

As $\phi$ increases with respect to $p$ and decreases with respect to $u$, cf. lemma 4.2, the maximum is attained for $p = p_2$ and $u = p_1 - 1$ which gives the supremum.

*Attaining the bounds.* First we shall show that the first upper bound is attained. We have to produce a full-dimensional polyhedron, with a $\sigma$-degenerate vertex $x^0$ and with $0 \le r \le \sigma$ weakly redundant constraints at $x^0$. Let $p = n + \sigma + 1$, $u = n + \sigma - r$ and consider a polytope pair $(Q, F)$ of class $(n, p, u)$ for which the number of vertices of $Q \setminus F$ is equal to $\phi(n, p, u)$. Then we shall prove that there exists a perturbation function such that $v = \phi(n, p, u)$.

Let $U$ be the unbounded simple polyhedron obtained from $Q$ by applying a projective transformation that sends the facet $F$ into the hyperplane at infinity [17, 19]. Then $U$ has precisely $u$ unbounded facets and its recession cone is full-dimensional [2], moreover $U$ and $Q \setminus F$ have the same number of vertices. Let

$$ U = \bigcap_{i=1}^{p-1} \{ \langle y_i \rangle \le \alpha_i \} $$

be a representation of $U$ such that each set $F_i = \{ \langle y_i \rangle = \alpha_i \} \cap U$ is a facet of $U$. We may assume that each $n$ of the hyperplanes $\{ \langle y_i \rangle = \alpha_i \}$ have a unique common point; if not, the vectors $y_i$ can be slightly perturbed such that each $n$ of them are linearly independent (the vectors $y_i$ are said to be in general position). The recession cone of $U$ is defined by

$$ \mathrm{rec} \, U = \bigcap_{i=1}^{p-1} \{ \langle y_i \rangle \le 0 \}. $$

Clearly, the unique vertex $x^0 = 0$ of $\mathrm{rec} \, U$ is $\sigma$-degenerate. Now we shall show that a facet $F_j$ of $U$ is bounded if and only if the constraint $\{ \langle y_j \rangle \le 0 \}$ is redundant for the representation of $\mathrm{rec} \, U$. Therefore the number of weakly redundant constraints at
$x^0$ will be equal to $r = p - 1 - u$. The facet $F_j$ is bounded if and only if its recession cone is equal to $\{0\}$, namely

$$ \mathrm{rec} F_j = \{\langle y_j \rangle = 0\} \cap \bigcap_{i \neq j} \{\langle y_i \rangle \le 0\} = \{0\}. $$

This implies $\{\langle y_j \rangle = 0\} \cap \bigcap_{i \neq j} \{\langle y_i \rangle < 0\} = \emptyset$, which is just a rephrasing of the redundancy of $\{\langle y_j \rangle \le 0\}$ [4, theorem 8.1]. Conversely, suppose that $\{\langle y_j \rangle \le 0\}$ is redundant, namely

$$ \bigcap_{i \neq j} \{\langle y_i \rangle \le 0\} \subset \{\langle y_j \rangle \le 0\}. $$

Using polarity of cones [25, chap. 14], the above inclusion is equivalent to $y_j \in C$, where $C$ is the cone generated by the vectors $y_i$, $i \in \{1, \dots, p-1\} \setminus \{j\}$. The cone $C$ is the polar cone of the pointed and full-dimensional cone $\mathrm{rec} U$, so it is also pointed and full-dimensional. Let us show that $y_j$ is an interior point of $C$. Since $C$ is pointed, it is the conical hull of its extremal directions [25, theorem 18.5] and each of them is among the vectors $y_i$, $i \neq j$. Suppose that $y_j$ is on the boundary of $C$. Then there exists a facet $D$ of $C$ which contains $y_j$. Since $C$ is full-dimensional, the facet $D$ has dimension $(n-1)$ and so has at least $(n-1)$ extremal directions. Therefore the hyperplane defined by $D$ contains at least $n$ vectors $y_i$, which contradicts the general position of $y_i$. Using again polarity, to say that $y_j$ is an interior point of $C$ is equivalent to

$$ \forall x \neq 0, \langle x, y_i \rangle \le 0, i \in \{1, \dots, p-1\} \setminus \{j\} \Rightarrow \langle x, y_j \rangle < 0. $$

This implies $\mathrm{rec} F_j = \{\langle y_j \rangle = 0\} \cap \bigcap_{i \neq j} \{\langle y_i \rangle \le 0\} = \{0\}$, therefore $F_j$ is bounded. Finally the vertex $x^0 = 0$ of $\mathrm{rec} U$ is $\sigma$-degenerate and precisely $r$ constraints are weakly redundant at $x^0$. Now its suffices to find a standard representation of $\mathrm{rec} U$ and apply theorem 3.3, which implies the existence of a perturbation function $h$ such that the perturbed polyhedron $(\mathrm{rec} U)(h)$ is equivalent to $U$.

Now for the situation with a stable perturbation function (lower bound and second upper bound), it suffices to restart the above procedure with a polytope pair $(Q, F)$ of class $(n, p, p-1)$, with $p = n + \sigma - r + 1$, for which the number of vertices of $Q \setminus F$ is equal to $\varphi(n, p, p-1)$ (resp. $\phi(n, p, p-1)$). Then we choose a representation of the unbounded polyhedron $U$ and add $r$ strongly redundant constraints. Obviously, the latter correspond to weakly redundant constraints for the recession cone of $U$. $\square$

Using the notation of the proof above, by lemma 2.2 we can easily derive the following formula,

$$ \phi(n, p_1, p_1 - 1) = \min \{\phi(n, p, u) : p_1 \le p \le p_2, p_1 - 1 \le u \le p - 1\}. $$
Therefore we might think that a stable perturbation function generates fewer vertices than any other. This is true for the dimensions 2 and 3 (see below), but the following example shows that this is false for the dimension 4.

### EXAMPLE 4.5

Consider $P = \{x \in \mathbb{R}^4 : Ax \leq b, x \geq 0\}$ with

$$A = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 49 & 23 & 42 & 11 \\ 40 & 17 & 36 & 3 \\ 103 & 35 & 14 & 96 \\ 123 & 21 & 77 & 94 \\ 56 & 16 & 34 & 42 \end{pmatrix}$$

and

$b = a^1$ (the first column of $A$).

$P$ is a 4-dimensional polytope and is the convex hull of the vertex $x^0 = (1, 0, 0, 0)^T$ with a 3-dimensional polytope contained in the hyperplane $\{\langle e_1 \rangle = 0\}$. There are 8 facets of $P$ containing $x^0$. The first constraint $\{\langle (1, 0, 0, 0) \rangle \le 1\}$ is redundant at $x^0$. Hence 9 constraints are tight for $x^0$, thus $x^0$ is 5-degenerate. For the stable perturbation function $h(t) = (t, t^2, \dots, t^6)^T$ there are 15 broken-vertices of $x^0$, although for the non-stable perturbation function $g(t) = (t^6, t^5, \dots, t)^T$, this number is only equal to 8. $\square$

Before dimension 3, consider full polytopes of $\mathbb{R}^2$. If $x^0$ is $\sigma$-degenerate, then its degeneracy is only due to redundancy. Therefore a stable perturbation function generates only one broken-vertex. If it is not stable the number of broken-vertices is bounded from above by $(\sigma + 1)$. Now we consider the three-dimensional case.

### PROPOSITION 4.6

Let $x^0$ be a $\sigma$-degenerate vertex of a full-dimensional polyhedron of $\mathbb{R}^3$. Let $r$ be the number of weakly redundant constraints at $x^0$. For any stable perturbation function the number of broken-vertices of $x^0$ is equal to $v = \sigma - r + 1$. Moreover, for any perturbation function this number is always greater than $v$.

#### Proof

Suppose the perturbation function stable, then the upper and lower bounds of theorem 4.4 are both equal to $v = 1 + \sigma - r$. Now suppose that among the
redundant constraints, there are $1 \le k \le r$ nonredundant constraints for the perturbed polyhedron. Let $(Q, F)$ be the polytope pair as in the proof of theorem 4.4. Then $(Q, F)$ is of class $(3, p, u)$ with $p = 4 + \sigma - r + k$ and $3 + \sigma - r \le u \le p - 1$. Since $\varphi$ decreases with respect to $u$, cf. lemma 4.3, then the number of broken-vertices of $x^0$ is lowered by $\varphi(3, 4 + \sigma - r + k, 3 + \sigma - r + k) = \sigma - r + k + 1 \ge v$. $\square$

The case of higher dimensions contradicts somewhat our intuition. For if a redundant constraint for the perturbed polyhedron becomes nonredundant (by a change of perturbation function), the perturbed polyhedron is in a way truncated such that the new polyhedron has one additional facet. Now, if a simple $d$-dimensional polytope $P$ is truncated to obtain a polytope $P'$ such that $P'$ is simple and has one more facet than $P$, then

* if $d = 2$ or $3$, $P'$ has more vertices than $P$,

* if $d \ge 4$, $P'$ may have fewer vertices than $P$.

For a polyhedron $P$ we denote by $p_k$ the number of $k$-dimensional faces. The above remark is trivial for $d = 2$ and for dimension 3 follows from the Dehn-Sommerville relations (see for example [4, §17]),

$$p_0 = 2p_2 - 4 \quad \text{and} \quad p_1 = 3p_2 - 6. \qquad (4.5)$$

Now suppose that $d = 4$. Let $P$ be a simple dual neighbourly polytope with $k$ facets (for example the dual of a cyclic polytope with $k$ vertices), see [4, §§13–14]. Then

$$p_3 = k \quad \text{and} \quad p_0 = \frac{1}{2}k(k-3).$$

Let $F$ be a facet of $P$. Translate the hyperplane determined by $F$ onto a hyperplane $H$, such that $F$ is one one side of $H$ and the vertices of $P\setminus F$ are on the other side, $H$ containing no vertex. Let $Q = H' \cap P$, where $H'$ is the closed halfspace bounded by $H$ and including $F$. Since any facet of $P$ intersects the others, $H$ intersects every facet different from $F$, and $G = H \cap P$ is a facet of $Q$. Hence $Q$ is a simple polytope with one additional facet. Vertices of $Q$ are the union of those of $F$ and those $G$. The latter result from the intersection of the hyperplane $H$ with external edges of $F$. Since $F$ is simple, there is precisely one external edge per vertex, therefore $q_0 = 2f_0$. The facet $F$ is a 3-dimensional simple polytope with $k-1$ facets, therefore by (4.5) we have $q_0 = 4(k-3)$. At last we have $p_0 > q_0$ as soon as $k \ge 9$. $\square$

This example is based on a counterexample of Mattheiss and Schmidt [22] invalidating a conjecture of Mattheiss [21] about a vertex enumeration algorithm. A similar construction can be found in [8, p. 388].
## Acknowledgements

The author is grateful to the referees for their helpful comments and suggestions concerning the presentation of the paper.

## References

[1] P. Armand and C. Malivert, Determination of the efficient set in multiobjective linear programming, J. Optim. Theory Appl. 70 (1991) 467-489.

[2] D. Barnette, P. Kleinschmidt and C.W. Lee, An upper bound theorem for polytope pairs, Math. Oper. Res. 11 (1986) 451-464.

[3] M.L. Balinski, An algorithm for finding all vertices of convex polyhedral sets, SIAM J. Appl. Math. 9 (1961) 72-88.

[4] A. Brondsted, *An Introduction to Convex Polytopes* (Springer, New York/Heidelberg/Berlin, 1983).

[5] A. Charnes, Optimality and degeneracy in linear programming, Econometrica 20 (1952) 160-170.

[6] G.B. Dantzig, *Linear Programming and Extensions* (Princeton University Press, Princeton, NJ, 1963).

[7] G.B. Dantzig, A. Orden and P. Wolfe, The generalized simplex algorithm for minimizing a linear form under linear inequality restraints (RAND Corporation Report, 1954) Pacific J. Math. 5 (1955) 183-195.

[8] H.E. Dyer, The complexity of vertex enumeration methods, Math. Oper. Res. 8 (1983) 381-402.

[9] T. Gal, Determination of all neighbors of a degenerate extreme point in polytopes, Discussion Paper 17b, FernUniversität Hagen, Germany (1978).

[10] T. Gal, On the structure of the set bases of a degenerate point, J. Optim. Theory Appl. 45 (1985) 577-589.

[11] T. Gal, Degeneracy graphs – Theory and application. A state-of-the-art survey, Diskussionsbeitrag 142, FernUniversität Hagen, Germany (1989).

[12] T. Gal, Degeneracy problems in mathematical programming and degeneracy graphs, Orion 6 (1990) 3-36.

[13] T. Gal, Weakly redundant constraints and their impact on postoptimal analyses in LP, Diskussionsbeitrag 151, FernUniversität Hagen, Germany (1990).

[14] T. Gal and F. Geue, The use of the TNP-rule to solve various degeneracy problems, Diskussionsbeitrag 149a, FernUniversität Hagen, Germany (1990).

[15] T. Gal, H.-J. Kruse and P. Zörnig, Survey of solved and open problems in the degeneracy phenomenon, Math. Progr. 42 (1988) 125-133.

[16] D. Gale, How to solve linear inequalities, Amer. Math. Monthly 76 (1969) 589-599.

[17] B. Grünbaum, *Convex Polytopes* (Wiley, London/New York/Sidney, 1967).

[18] G. Hadley, *Linear Programming* (Addison-Wesley, MA, 1962).

[19] V. Klee, Polytopes pairs and their relationship to linear programming, Acta Math. 133 (1974) 1-25.

[20] H.-J. Kruse, *Degeneracy Graphs and the Neighbourhood Problem*, Lecture Notes in Economics and Mathematical Systems 260 (Springer, Berlin, 1986).

[21] T.H. Mattheiss, An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities, Oper. Res. 21 (1973) 247-260.

[22] T.H. Mattheiss and B.K. Schmidt, Computational results on an algorithm for finding all vertices of a polytope, Math. Progr. 18 (1980) 308-329.

[23] K.G. Murty, *Faces of a polyhedron*, Math. Progr. Study 24 (1985) 30-42.
[24] M.R. Osborne and D.M. Ryan, On the solution of highly degenerate linear programmes, Math. Progr. 41 (1988) 385-392.

[25] R.T. Rockafellar, *Convex Analysis* (Princeton, NJ, 1972).

[26] P. Wolfe, A technique for resolving degeneracy in linear programming, SIAM J. 11 (1963) 205-211.