(A) new lower bound updating scheme in karmarkar's algorithm = Karmarkar 알고리즘에서의 새로운 하한개선 기법에 관한 연구

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 211
  • Download : 0
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.
Advisors
Kim, Se-Hunresearcher김세헌researcher
Description
한국과학기술원 : 경영과학과,
Publisher
한국과학기술원
Issue Date
1991
Identifier
68023/325007 / 000891488
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 경영과학과, 1991.2, [ [ii], 44 p. ; ]

URI
http://hdl.handle.net/10203/44914
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=68023&flag=dissertation
Appears in Collection
MG-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0