Search

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]