Hybrid-LP: Finding advanced starting points for simplex, and pivoting LP methods

摘要

The simplex method has proven its efficiency in practice for linear programming (LP) problems of various types and sizes. However, its theoretical worst-case complexity in addition to its poor performance for very large-scale LP problems has driven researchers to develop alternative methods for LP problems. In this paper, we develop the hybrid-LP; a two-phase approach for solving LP problems. Rather than following a path of extreme points on the boundary of the feasible region as in the simplex method, the first phase of the hybrid-LP moves through the interior of the feasible region to obtain an improved and advanced initial basic feasible solution (BFS). Then, in the second phase simplex or other LP methods can be used to find the optimal solution. Since the introduction of polynomial-time methods for LP, a considerable amount of research has focused on interior-point methods for solving large-scale LP problems. Although fewer iterations are needed for interior-point methods to converge to a solution, the iterations are computationally intensive. Our approach is a hybrid method that uses a computationally efficient pivot to move in the interior of the feasible region in its first phase. This single iteration is able to bypassing several extreme points to an improved BFS, which can then be used as a starting point in any LP method in the second phase of the method. Our approach can also be modified to perform a number of interior pivots in the first phase based on the trade-off between the number of iterations and the running time. The hybrid-LP uses an efficient pivoting iteration which is computationally comparable to the standard simplex iteration. Another feature is adaptability in finding the advanced starting point by avoiding the boundaries of the feasible region. In addition, the hybrid-LP has the ability to start from a feasible point which may not be a BFS. Our computational experiments demonstrate that the hybrid-LP reduces both the number of iterations and the running time compared to the simplex method on a wide range of test problems.