Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective value z*. These new methods combine the approach of D. Goldfarb and S. Mehrotra for relaxing the requirement that certain projects be computed exactly with the approach of M. J. Todd and B. P. Burrell for generating an improving sequence of lower bounds for z* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.
|Original language||English (US)|
|Number of pages||13|
|Journal||Mathematical Programming, Series B|
|State||Published - Feb 1 1988|
ASJC Scopus subject areas