Simplex Method With Objective Jump

Abstract

We propose an idea of “objective jump”, a novel approach to obtain an initial basic feasible solution from the origin point before starting the simplex method. For a linear programming problem expressed in the canonical form, if its right-hand-side vector is non-negative, the origin point is guaranteed to be in the feasible region and is normally used as the starting point of the simplex method. Our objective jump procedure aims to start at another basic feasible solution by jumping from the origin along the objective gradient direction. This procedure requires additional constraints to construct a sub-LP problem with a smaller feasible region where an additional edge of this smaller region is formed such that it aligns with the gradient vector of the objective function. Then, a special matrix manipulation is performed to move from the origin to another extreme point on this edge. After this procedure is done, some special pivots are required to move to a nearby extreme point, which becomes our new initial basic feasible solution for the simplex method. The numerical examples have shown that the new initial basic feasible solutions outperformed the origin point in terms of the number of iterations and the running time. However, there is a price to pay in terms of additional iterations and running time to obtain such initial basic feasible solutions. When taking the price into consideration, the simplex method with objective jump outperformed the traditional simplex method only on problems with 2 – 5 variables and no more than 1000 constraints in terms of both the total number of iterations and the running time. In addition, the simplex method with objective jump performed with less running time than the traditional simplex although the number of iterations was larger for most cases when the number of constraints is at least 300 up to 1000 and the number of variables is at least 40 but does not exceed the number of constraints for each problem.