The primal simplex algorithm is still one of the most used algorithms by the operations research community. It moves from basis to adjacent one until optimality. The number of bases can bef very huge, even exponential, due to degeneracy or when we have to go through all of the extreme points very close to each other. The improved primal simplex algorithm (IPS) is efficient against degeneracy but when there is no degeneracy, it behaves exactly as a primal simplex and consequently, it may suffer from the same limitations. We present a new formulation of the complementary problem, i.e., the auxiliary subproblem used by the improved primal simplex to find descent directions, that guarantees a significant improvement of the objective value at each iteration until we reach an \(\epsilon-\)approximation of the optimal value. We prove that the number of needed directions is polynomial.