Solving linear programs with finite precision: II. Algorithms

We describe an algorithm that first decides whether the primal-dual pair of linear programsmincTxmaxbTys.t.Ax=bs.t.ATy⩽cx⩾0is feasible and in case it is, computes an optimal basis and optimal solutions. Here, A∈Rm×n,b∈Rm,c∈RnA∈Rm×n,b∈Rm,c∈Rn are given. Our algorithm works with finite precision arithmetic. Yet, this precision is variable and is adjusted during the algorithm. Both the finest precision required and the complexity of the algorithm depend on the dimensions n and m   as well as on the condition K(A,b,c)K(A,b,c) introduced in D. Cheung and F. Cucker [Solving linear programs with finite precision: I. Condition numbers and random programs, Math. Program. 99 (2004) 175–196].