The steepest descent gravitational method for linear programming

We present a version of the gravitational method for linear programming, based on steepest descent gravitational directions. Finding the direction involves a special small "nearest point problem" that we solve using an efficient geometric approach. The method requires no expensive initialization, and operates only with a small subset of locally active constraints at each step. Redundant constraints are automatically excluded in the main computation. Computational results are provided.Peer Reviewedhttp://deepblue.lib.umich.edu/bitstream/2027.42/27699/1/0000085.pd