Convergence results and numerical experiments on a linear programming hybrid algorithm |
| |
| Institution: | 1. LPTPM, Hassiba Ben Bouali University of Chlef, Esalem City, 02000 Chlef, Algeria;2. Sonatrach/Direction Centrale Recherche & Développement, Avenue du 1er Novembre, 35000 Boumerdès, Algéria;3. Research Center in Industrial Technologies (CRTI), P. O. Box 64, Cheraga, Algiers 16014, Algeria;1. Process Systems Engineering (AVT.SVT), RWTH Aachen University, Aachen, Germany;2. Institute of Operations Research, Karlsruhe Institute of Technology (KIT), Karlsruhe, Germany;1. The University of Texas at Arlington, USA;2. Columbia University, USA;3. University of California, Berkeley, USA |
| |
| Abstract: | A modification of Karmarkar's algorithm for linear programming successively generates column-scaled equivalents of the original linear program, and in the scaled coordinates obtains improvements according to steepest descent directions. As an interior-feasible-preserving algorithm, termination requires a purification algorithm to obtain a dual basic optimal solution. Together the two algorithms comprise a ‘hybrid’ procedure for solving linear programs.In this paper we present some convergence results on the Phase II and Phase I portions of the scaling algorithm. We also present results of numerical experiments on examples of Klee—Minty type which show sensitivity to the starting interior-feasible point and steepest descent step size. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
