Publication
Operations Research Letters
Paper

On the ε-perturbation method for avoiding degeneracy

View publication

Abstract

Although it is NP-complete to decide whether a linear programming problem is degenerate, the ε-perturbation method can be used to reduce in polynomial time any linear programming problem with rational coefficients to a nondegenerate problem. The perturbed problem has the same status as the given one in terms of feasibility and unboundedness, and optimal bases of the perturbed problem are optimal in the given problem. © 1989.

Date

01 Jan 1989

Publication

Operations Research Letters

Authors

Topics

Share