A relaxed primal-dual path-following algorithm for linear programming |
| |
Authors: | Tsung-Min Hwang Chih-Hung Lin Wen-Wei Lin Shu-Cherng Fang |
| |
Institution: | (1) Institute of Applied Mathematics, National Tsing Hua University, 30043 Hsinchu, Taiwan R.O.C.;(2) Operations Research and Industrial Engineering, North Carolina State University, 27615-7913 Raleigh, NC, USA |
| |
Abstract: | In this paper, we provide an easily satisfied relaxation condition for the primaldual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts.Partially supported by the North Carolina Supercomputing Center, the 1993 Cray Research Award, and a National Science Council Research Grant of the Republic of China. |
| |
Keywords: | Linear programming primal-dual method interior path-following algorithm relaxation method |
本文献已被 SpringerLink 等数据库收录! |
|