An AI search algorithm to obtain the shortest simplex path

Abstract

The simplex method is one way of solving a linear programming problem (LP-problem). An A* search algorithm based on a certain evaluation function has been developed to obtain the shortest path to an optimal solution within the simplex rules. An evaluation function was used to guide the algorithm to obtain the shortest path through the convex polyhedron. Every extreme point in the polyhedron is presented by a node in the search tree. The evaluation function employs a lower bound of the real path length from node n to the optimal node. The algorithm has been applied successfully to some problems from the NETLIB test suite. Empirical work is presented that compares these shortest paths with some other known column selection heuristics.