Metode interior primal-dual dengan langkah full-newton: Studi kasus masalah klee-minty dengan kendala redundant taknegatif

Abstract

Klee-Minty problem is a linear optimization problem that requires exponential iteration when it is solved by simplex method. The weakness of this simplex method has stimulated research to find another method, that can solve linear optimization problem with polynomial time. Effective breakthrough to solve linear optimization problem has occurred with the appearance of interior-point method. In solving the Klee-Minty problem using interior-point method, the process leading to an optimal solution follows a central path. In this paper we examine one of the worst case of solving Klee-Minty problem, with the addition of redundant non-negative constraints. From the results of some case studies, it is known that these constraints lead the central path to visit the vertices in the feasible region closely enough. So solving the Klee-Minty problem using the interior-point method becomes longer.