System Engineering 3(3+0)

LESSON 3. Degeneracy

2.2 The Finiteness of the Simplex Algorithm when there is no degeneracy

Recall that the simplex algorithm tries to increase a non-basic variable x’s. If there is no degeneracy, then x’s will be positive after the pivot, and the objective value will improve. Recall also that each solution produced by the simplex algorithm’s a basic feasible solution with m basic variables, where m is the number of constraints. There are a finite number of ways of choosing the basic variables. (An upper bound is n! / (n-m)! m! , which is the number of ways of selecting m basic variables out of n.) So, the simplex algorithm moves from bfs to bfs. And it never repeats a bfs because the objective is constantly improving. This shows that the simplex method is finite, so long as there is no degeneracy.

2.3 Procedure to avoid cycling

A computation procedure to avoid cycling at any stage consists of the following steps

Step 1:

Step 2:

Re arrange the column vectors of A, so that the starting initial basis B is chosen by selecting the first m column vectors of A. Then

                        y_j = B^-1 a_j = e_j (j = 1,2…,m)

Step 3:

If this minimum is unique for some I = k, then the vector y_k leaves the basis. Otherwise go to next step.

Step 4:

If this minimum is unique for some i = k, then the vector y_k leaves the basis. Otherwise go to next step.

Step 5:

If this minimum is unique for some I = k, then the vector y_k leaves the basis. Otherwise continue the procedure until a unique minimum nonnegative replacement ratio is obtained.

Note:

The above procedure is applicable to any iteration. However we have to maintain the same ordering of the column vectors in every iteration. Any artificial vector, if included, should also not be removed at any stage.

 2.4 Degeneracy and the Simplex Algorithm

The simplex method without degeneracy	The simplex method without degeneracy
The solution changes after each pivot. The objective value strictly improves after a pivot.	The solution may stay the same after a pivot. The objective value may stay the same.
The Simplex method is guaranteed to be finite.	The Simplex method may cycle and be finite. But it becomes finite if we use the perturbation approach or several other approaches.
Two different tableaus in canonical form give two different solutions.	It is possible that there are two different sets of basic variables that give the same solution.

 

Degeneracy is important because we want the simplex method to be finite, and the generic simplex method is not finite if bases are permitted to be degenerate.

In principle, cycling can occur if there is degeneracy. In practice, cycling does not arise, but no one really knows why not. Perhaps it does occur, but people assume that the simplex algorithm is just taking too long for some other reason, and they never discover the cycling.

 Researchers have developed several different approaches to ensure the finiteness of the simplex method, even if the bases can be degenerate. One such method is called the perturbation approach. The perturbation approach (in the form described here) is not practical, but it serves its purpose. It does give a way of doing simplex pivoting that is guaranteed to be finite.