|
|||||
|
|
Determination of optimal vertices from feasible solutions in unimodular linear programming |
|
| Authors: | Shinji Mizuno Romesh Saigal James B Orlin |
| Institution: | (1) Department of Prediction and Control, The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, 106 Tokyo, Japan;(2) Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor, MI, USA;(3) Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA, USA |
| Abstract: | In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.This author's research is partially supported by NSF grant DDM-8921835 and Airforce Grant AFSOR-88-0088. |
| Keywords: | Linear programming duality theorem unimodular totally unimodular interior point methods |
| 本文献已被 SpringerLink 等数据库收录！ | |