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

Considered is the linear programming problem minimize \(z(x)=c^ Tx\) subject to \(Ax=0,\) \(e^ T=n,\) \(x\geq 0,\) where A is an \(m\times n\) matrix of rank m, \(x\in R^ n\), \(c\in R^ n\), and \(e\in R^ n\) is the vector with all its elements equal to one. It is assumed that e is a feasible point, i.e. \(Ae=0\), and that a lower bound \(z^ 0\) on the optimal value is known. The authors give variants of Karmarkar's algorithm for this problem with unknown optimal objective value \(z^*\). These methods combine an earlier approach of the authors 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. It is also discussed how to compute an initial lower bound for the optimal objective value and how to transform a ``standard form linear program into the form given in this paper.

Recommendations

Cites work

Cited in

(13)

Describes a project that uses

Uses Software

This page was built for publication: Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103522)