TITLE:
A Class of Algorithms for Solving LP Problems by Prioritizing the Constraints
AUTHORS:
Dimitris G. Tsarmpopoulos, Christina D. Nikolakakou, George S. Androulakis
KEYWORDS:
Linear Programming, Binding Constraints, Redundant Constraints, Proximity Technique, Constraint Ranking, Constraint Detection
JOURNAL NAME:
American Journal of Operations Research,
Vol.13 No.6,
November
24,
2023
ABSTRACT: Linear programming is a method for solving linear optimization problems
with constraints, widely met in real-world applications. In the vast majority
of these applications, the number of constraints is significantly larger than the number of
variables. Since the crucial subject of these
problems is to detect the constraints that
will be verified as equality in an optimal solution, there are methods for
investigating such constraints to accelerate the whole process. In this
paper, a technique named proximity technique is addressed, which under a
proposed theoretical framework gives an ascending order to the constraints in
such a way that those with low ranking are characterized of high priority to be
binding. Under this framework, two new Linear programming optimization
algorithms are introduced, based on a proposed Utility matrix and a utility
vector accordingly. For testing the addressed algorithms firstly a generator of
10,000 random linear programming problems of dimension n with m constraints,
where , is introduced in order to simulate as many as possible
real-world problems, and secondly, real-life linear programming examples from
the NETLIB repository are tested. A discussion of the numerical results is
given. Furthermore, already known methods for solving linear programming
problems are suggested to be fitted under the proposed framework.