Search

The primary objective of this study is to propose the use of nonlinear functions to find a feasible interior point in a region defined by the constraints of linear programming problems with the advantage of not having to use slack or surplus variables. The feasible region of linear programming problems is defined by convex sets named polyhedra that have the form Ax ≤ b and that can be bounded or unbounded. Finding an interior point (even extreme or frontier point) is not a trivial issue but is a necessary condition to initialize algorithms for solving a linear programming problem. To achieve this, unrestricted nonlinear penalty functions are applied and optimized. As a result, it is demonstrated that the optimal solution point corresponds to an interior point of the original polyhedron. It is concluded that the proposed algorithmic procedure possesses features that provide advantages for solving linear programming problems. [ABSTRACT FROM AUTHOR]

The aim of this paper is to propose a procedure to create escape vectors specifically developed to perform an orthogonal projection from an Ax≤b type polyhedron's edge to its interior. The proposed procedure can be implemented in interior-point methods for solving linear programming problems since in these methods various strategies are used to avoid reaching the borders of the polyhedron. A projection procedure was developed to the polyhedron's interior starting from three scenarios and it was used on a context case demonstrating its applicability. The results show that the projection carried out in the iteration in which the escape is done not only allows abandoning from a suboptimal solution but it also kept the same objective function value. Therefore, it can be concluded that interior-point methods do not need to avoid the frontier or to adjust values, as it occurs in other applications. [ABSTRACT FROM AUTHOR]

This paper presents a study done to find an interior point in the feasible region of linear programming problems is an aspect that should be solved in the initial stage of the implementation of the interior point algorithms used to optimize them. Consequently, it is proposed a methodology that starts with a formulation that does not require adding surplus or slack variables. It only includes an additional variable to generate a polyhedron in a new expanded space and with simple projections finds an interior point in the same polyhedron. It is demonstrated that the optimal solution of the extended linear programming problem allows obtaining a feasible point of the original problem or concluding that it has no feasible solutions. [ABSTRACT FROM AUTHOR]