TITLE:
A Dimensional Reduction Approach Based on Essential Constraints in Linear Programming
AUTHORS:
Eirini I. Nikolopoulou, George S. Androulakis
KEYWORDS:
Linear Programming, Binding Constraints, Dimension Reduction, Cosine Similarity, Decision Analysis, Decision Trees
JOURNAL NAME:
American Journal of Operations Research,
Vol.14 No.1,
January
17,
2024
ABSTRACT: This paper presents a new dimension reduction strategy for medium and
large-scale linear programming problems. The proposed method uses a subset of
the original constraints and combines two algorithms: the weighted average and
the cosine simplex algorithm. The first approach identifies binding constraints
by using the weighted average of each constraint, whereas the second algorithm
is based on the cosine similarity between the vector of the objective function
and the constraints. These two approaches are complementary, and when used
together, they locate the essential subset of initial constraints required for
solving medium and large-scale linear programming problems. After reducing the
dimension of the linear programming problem using the subset of the essential
constraints, the solution method can be chosen from any suitable method for
linear programming. The proposed approach was applied to a set of well-known
benchmarks as well as more than 2000 random medium and large-scale linear
programming problems. The results are promising, indicating that the new
approach contributes to the reduction of both the size of the problems and the
total number of iterations required. A tree-based classification model also
confirmed the need for combining the two approaches. A detailed numerical
example, the general numerical results, and the statistical analysis for the
decision tree procedure are presented.