TITLE:
Locating Binding Constraints in LP Problems
AUTHORS:
Eirini I. Nikolopoulou, George E. Manoussakis, George S. Androulakis
KEYWORDS:
Linear Programming, Simplex, Binding Constraints, Weighted Average
JOURNAL NAME:
American Journal of Operations Research,
Vol.9 No.2,
March
7,
2019
ABSTRACT: In this work, a new method is presented for determining the binding constraints
of a general linear maximization problem. The new method uses only
objective function values at points which are determined by simple vector
operations, so the computational cost is inferior to the corresponding cost of
matrix manipulation and/or inversion. This method uses a recently proposed
notion for addressing such problems: the average of each constraint. The
identification of binding constraints decreases the complexity and the dimension
of the problem resulting to a significant decrease of the computational
cost comparing to Simplex-like methods. The new method is highly useful
when dealing with very large linear programming (LP) problems, where only
a relatively small percentage of constraints are binding at the optimal solution,
as in many transportation, management and economic problems, since
it reduces the size of the problem. The method has been implemented and
tested in a large number of LP problems. In LP problems without superfluous
constraints, the algorithm was 100% successful in identifying binding constraints,
while in a set of large scale LP tested problems that included superfluous
constraints, the power of the algorithm considered as statistical tool of
binding constraints identification, was up to 90.4%.