%0 Journal Article
%T A Class of Algorithms for Solving LP Problems by Prioritizing the Constraints
%A Dimitris G. Tsarmpopoulos
%A Christina D. Nikolakakou
%A George S. Androulakis
%J American Journal of Operations Research
%P 177-205
%@ 2160-8849
%D 2023
%I Scientific Research Publishing
%R 10.4236/ajor.2023.136010
%X 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</span></span><span><span><span style=\"font-family:&quot;\">,</span></span></span><span><span><span style=\"font-family:&quot;\"> the number of constraints is significantly larger than the number of
variables. Since the crucial subject </span></span></span><span><span><span style=\"font-family:&quot;\">of</span></span></span><span><span><span style=\"font-family:&quot;\"> these
problems is to detect th<span>e constraints that
will be verified as equality in an optimal solution, there are methods for
investigating such constraints to accelerate the whole proces</span>s. 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 <i>n</i> with <i>m</i> constraints,
where <span></span>, 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.
%K Linear Programming
%K Binding Constraints
%K Redundant Constraints
%K Proximity Technique
%K Constraint Ranking
%K Constraint Detection
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=129238