Locating Binding Constraints in LP Problems

作     者：Eirini I. Nikolopoulou George E. Manoussakis George S. Androulakis 

作者机构：Department of Business Administration University of Patras Patras Greece 

出 版 物：《American Journal of Operations Research》 (美国运筹学期刊（英文）)

年 卷 期：2019年第9卷第2期

页      面：59-78页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Linear Programming Simplex Binding Constraints Weighted Average 

摘      要：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%.