An LP Problem Is Called Degenerate If a Basic Variable Is Driven to Zero at Some Dictionary

MSIS 685 : LINEAR PROGRAMMING

LECTURE 4

10/1/98

Scribe : Boubakar S. Fofana

I. DEGENERACY

An LP problem is called degenerate if a basic variable is zero at some dictionary.

As a result, we may not be able to improve the objective function (noted here z) from that dictionary.

This causes a problem. Normally, any dictionary improves the value of the objective function produced by: in a finite number of iterations the algorithm converges to the optimum point without ever coming back to the points already visited. In a degeneracy situation we may end up in an infinite loop.

Example of degeneracy :

Basic variables x and x were driven to zero from the previous dictionary to the current one :

z = 1 + x + 3x

x = 3 +2x + 3 x (1)

x = 0 - x - x (2)

x = 0 + 3 x -x (3)

Solution associated with this dictionary :

Basic variables : x = 3 , x = x = 0;

Non-basic : x = x =0;

Objective function : z=1.

This solution calls for a number of observations :

1) It is not necessarily optimal, since both the coefficients of x and x in z are positive.

2) Since the non-basic variables are characterized by the fact that they take on the value of zero,

switching x and xshould not matter since they lead to the same value of z , with a vector solution geometrically similar to the previous ,although different algebraically. There lies the ambiguity of degeneracy.

Degenerate dictionary may produce a new one, or even lead to the initial dictionary, causing an infinite loop, called cycling. However, cycling is a very rare occurrence : the process may stall, but rarely does it come back to previous point. It is even very difficult to manufacture an example of cycling . An example can be found in the text book, page 27. ( Linear Programming,Foundations and Extensions,by Robert J. Vanderbei)

Geometric interpretation of Degeneracy .

Each constraint of the dictionary represents a hyperplane. Consider a system of three hyperplanes in the 3-dimensional space :

x + x+ x =

x + x + x =

x + x + x=

The solution P(x, x, x) is unique, assuming that the constraint matrix is not singular (i.e. determinant non zero). Such point, where 3 hyperplanes meet in the 3-dimensional space, is called simplicial point. Degeneracy occurs if there was a 4th hyperplane that goes through P, affecting the path of the algorithm, but not the value of the objective function.

How often does degeneracy occur ?

In the general case of a n-dimensional space, adding a (n+1)th hyperplan to the system, by choosing its coefficient randomly from [0,1] for instance, it can be shown that the probability of getting a solution for the augmented system is zero. In other words , the probability for the (n+1)th hyperplan to go through P is zero.

.However, since the coefficients of real-life LP problems are not the product of randomness, degeneracy is not rare. In fact, there exist classes of problems, such as cost flow optimization, in which degeneracy is inherent.

How do we deal with degeneracy ?

Two methods help the simplex algorithm to converge in a degeneracy situation.

Method 1 : Pertubation/ lexicographic method

This method consists of removing the degeneracy as it were, by adding an infinitesimal amount to

each constraint : aX = b+ , with i = 1,2,…m . While such pertubating amounts are too negligible to affect the structure of the problem,they allow us to further carry out the simplex method with no zero-valued basic variables.

Let us apply this method to our example :

z = 1 + x + 3x

x = 3 + +2x + 3 x (1)

x = 0 + - x - x (2)

x = 0 + + 3 x -x (3)

With the highest coefficient in the objective function, xis the entering variable. Since

a)there is no restriction on (1),

b) constraint (2) limits the maximum value of xto ,

c)constraint (3) limits the maximum value of xto ,

and , then x leaves the basis.

The new dictionary becomes after pivoting :

z = 1 + 3 -3 x -2 x

x = 3 + +3 - x + x (1)

x = 0 + - x - x (2)

x = 0 - + + x +4 x (3)

Solution associated with this dictionary :

Basic variables : x = 3 , x = , x = - +;

Non-basic : x = x =0;

Objective function : z = 1 + 3 : improved by 3. With the coefficients of the objective function all negative, no further improvement is possible. That is not always the case : the convergence could take more dictionaries.

Since the ’s are negligible, we disregard them. As a result, the optimal is reached at

x = 3 , x =0, x = 0;

x = x =0;

z = 1

If the convergence takes many iterations, especially in large problems, linear combinations of ’s will show up,. How do we know that their sizes won’t produce numbers large enough to disrupt the structure of the problem ? To deal with this issue, we could choose the ’s such that

=, =, … == . This construct insures that the magnitude of any multiple of is negligible compared to that of .

In reality, we need not pick specific ’s . Rather, we treat them as symbols representing numbers that satisfy the suitable properties.

Also, combinations like xk = such that all =0 is impossible. To show this, consider matrix

R=

This matrix is singular if and only if any row =0, or if such row can be obtained by iterations, i.e. by performing elementary linear operations on rows (Gauss method).Such occurrence is impossible. This claim stems from the fact that R, the product of elementary operations applied to the non-singular matrix , is necessarily a non-singular matrix :

=

Method 2 : Bland’s Rule:

This rule, immune to cycling, provides a criterion for choosing the pivot, i.e. to decide which variable enters the basis and which one exits :

Step1 : impose an arbitrary order on the variables.

Step 2 : always choose, in the objective function, the variable with the smallest index as the entering variable.

Step 3 : always choose the variable with the smallest index as the exiting variable.

II. DUALITY

Duality is a central concept in Linear Programming.Every LP problem is associated with another LP problem called dual. The former is called primal.

Consider a primal problem (P-problem) :

Max Xc and X R

ST

AX bb R; A (n,m)

X 0 where

The D-problem is obtained by “rotating” the P-problem as follow :

Min Y Y R

ST

AY cA(n,m)

Y 0

The Weak Duality Lemma:

If X is P-feasible ( i.e. AX b and X 0 ), and Y D-feadible, then X Y

Proof :

c AY X X( AY) = (AX)Y = Y

Corollary 1:

If X is P-feasible, Y D-feasible, and X = Y then X is the optimal solution of the P-problem, and Y the optimal solution of the D-problem.

Proof :

X P-feasible, andY D-feasible X Y by virtue of the Weak Duality Lemma.Therefore, the equality implies that X has reached its maximum value, i.e. X is the optimal solution of the P-problem.

Similarly, the equality implies that Y has reached its minimum, i.e. Y is the optimal solution of the D-problem.

Corollary 2:

(1)If the P-problem is unbounded, then the D-problem is infeasible.

(2)If the D-problem is unbounded, then the P-problem is infeasible.

Proof :

(1)Suppose P-problem is unbounded, and there exist a Y D-feasible. Because of the unboundedness, we can always find an X P-feasible such that X > Y, in contradiction with the weak duality lemma. Therefore there is no feasible Y.

(2)Similar reasoning as (1).

Note : it is possible that both P and D-problem are infeasible. (Cf Question 5, Homework Set 1).

The Duality Theorem:

If both the P and D-problems are bounded and feasible, then, at optimum, we obtain X = Y

Note : there are two methods to prove this theorem :

1)The constructive proof (provided in Lecture 5):

From the last dictionary (optimal dictionary), we extract a Y D-feasible, show that X =Y, and then apply Corollary 1.This method proves the existence of a solution and constructs one.

2)The existence proof :

This method , more general, uses methods on convexity, beyond Linear Programming.