Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value |
| |
Authors: | Donald Goldfarb Sanjay Mehrotra |
| |
Affiliation: | (1) Department of Industrial Engineering and Operations Research, Columbia University, 10027 New York, NY, USA;(2) Department of Industrial Engineering and Management Studies, Northwestern University, 60208 Evanston, IL, USA |
| |
Abstract: | Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective valuez*. These new methods combine the approach of Goldfarb and Mehrotra for relaxing the requirement that certain projections be computed exactly with the approach of Todd and Burrell for generating an improving sequence of lower bounds forz* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.This research was supported in part by NSF Grants DMS-85-12277 and CDR-84-21402, and ONR Contract N0014-87-K0214. |
| |
Keywords: | Karmarkar's method linear programming inexact projections |
本文献已被 SpringerLink 等数据库收录! |