O(n(3)) noniterative heuristic algorithm for linear programs with error-free implementation

We present an O(n(3)) noniterative heuristic algorithm and describe an impl ementation of p-adic arithmetic to solve the linear programming problems er ror-free. An optimality test as well as numerical examples depict the scope of such an algorithm. In the few cases where it did not lead to the optima l solution, it did provide a nonnegative solution of the system Ax = b, whi ch could be used as the basic feasible solution for any one of the widely u sed simplex methods, say, the revised simplex algorithm without the need to include artificial variables in .4x = b for consistency check. Thus the al gorithm could be at least a pre-processor for any simplex algorithm and avo ids the enhancement of dimensions of the constraint matrix A and consequent additional space, computational complexities, and errors. (C) 2000 Elsevie r Science Inc. All rights reserved.