Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value (Q1103522): Difference between revisions

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.