Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

Donald Goldfarb; Sanjay Mehrotra

doi:10.1007/BF01580729

Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

Donald Goldfarb^*, Sanjay Mehrotra

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective value z^*. 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 for z^* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.

Original language	English (US)
Pages (from-to)	183-195
Number of pages	13
Journal	Mathematical Programming, Series B
Volume	40
Issue number	1-3
DOIs	https://doi.org/10.1007/BF01580729
State	Published - Jan 1 1988

Keywords

Karmarkar's method
inexact projections
linear programming

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1007/BF01580729

Cite this

@article{4116c341bb3144c8b6c984e291ecf317,

title = "Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value",

abstract = "Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective value z*. 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 for z* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.",

keywords = "Karmarkar's method, inexact projections, linear programming",

author = "Donald Goldfarb and Sanjay Mehrotra",

year = "1988",

month = jan,

day = "1",

doi = "10.1007/BF01580729",

language = "English (US)",

volume = "40",

pages = "183--195",

journal = "Mathematical Programming, Series B",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1-3",

}

TY - JOUR

T1 - Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

AU - Goldfarb, Donald

AU - Mehrotra, Sanjay

PY - 1988/1/1

Y1 - 1988/1/1

N2 - Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective value z*. 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 for z* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.

AB - Variants of Karmarkar's algorithm are given for solving linear programs with unknown optimal objective value z*. 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 for z* using dual feasible solutions. These methods retain the polynomial-time complexity of Karmarkar's algorithm.

KW - Karmarkar's method

KW - inexact projections

KW - linear programming

UR - http://www.scopus.com/inward/record.url?scp=34250092355&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34250092355&partnerID=8YFLogxK

U2 - 10.1007/BF01580729

DO - 10.1007/BF01580729

M3 - Article

AN - SCOPUS:34250092355

SN - 0025-5610

VL - 40

SP - 183

EP - 195

JO - Mathematical Programming, Series B

JF - Mathematical Programming, Series B

IS - 1-3

ER -

Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this