Iterative jump to binding point for simplex method

Abstract

The basic idea of an iterative jump method is moving a feasible point along the direction that improves the objective value maintaining the feasibility. It is applied for solving a linear programming (LP) model without artificial variables by applying the iterative jump on the LP relaxation having only acute constraints with respect to the objective direction and reinsert all non-acute constraints to find the optimal solution which is named SAJS. However, it may cause the last jump point to locate far away from the optimal solution so another approach for initially finding a suitable starting point is proposed. The new proposed method, AJSP use this technique together with the perturbation of the right-hand side values of violated constraints to be able to start at the feasible point before applying the iterative jump method. Both SAJS and AJSP outperform the standard simplex method and the artificial-free simplex algorithm based on the non-acute constraint relaxation on synthetic linear programming problems and Netlib problems.