Preceding-Jump Simplex method

Abstract

A practical linear programming solver uses the simplex method to identify the optimal solution by iteratively searching among adjacent feasible vertices. It may visit numerous vertices before finding the optimal one for a large linear programming problem taking a long time to succeed. This research proposes a heuristic method to alleviate this issue by jumping to a new vertex close to the optimal one before performing the simplex method. The new vertex is identified by first jumping from the initial vertex along the gradient vector of the objective function or alternative direction if the objective direction points out of the feasible region and stops at the first feasible point binding at one constraint. It then shifts to a neighbor feasible point preserving previous binding constraints until it reaches the feasible vertex so the simplex method can start. The algorithm is tested on synthetic problems with the origin point as the initial vertex from 100 to 2500 variable having the same number of constraints. Moreover, the preceding jump simplex method is extended to solve general synthetic linear programming problems of 100 to 1000 variables. The experimental results show that the preceding-jump simplex method significantly reduces the number of iterations and total running time.