(A) new lower bound updating scheme in karmarkar's algorithm

Abstract

Karmarkar``s algorithm is known to have some practical deficiency in spite of its polynomial complexity. It requires prior knowledge of the exact optimal value and it does not generate the optimal dual solutions. ye and Kojima developed a standard form variant of Karmarkar``s algorithm that generates a dual solution through successive lower bound updating scheme of the unknown optimal objective value. In this thesis, to improve the algorithm of Ye and Kojima further, Karmarkar``s algorithm is joined with the ellipsoid method using dualcontaining ellipsoid. A dual-containing ellipsoid contains all of the optimal dual solutions, and this ellipsoid shrinks at a fixed ratio. Our method, then finds dual feasible solutions contained in this ellipsoid and uses them to generate a new lower bound of the optimal objective value. This boudn is utilized in the Ye and Kojima``s scheme to improve its computational efficiency. Our method has been tested on 12 example problems. We observed that the number of iterations has been reduced significantly in all test problems. However, the total CPU times did not reduced due to the additional computational times required in the process of obtaining a dual feasible solution.