An AI search algorithm to obtain the shortest simplex path
Loading...
Authors
Scott, TG
Hattingh, J.M.
Steyn, T
Issue Date
1996
Type
Article
Language
en
Keywords
Linear programming , Artificial intelligence , Simplex method , Search algorithms , A*-algorithm
Alternative Title
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.
Description
Citation
Scott TG, Hattingh JM & Steyn T (1996) An AI search algorithm to obtain the shortest simplex path. South African Computer Journal, Number 18, 1996
Publisher
South African Computer Society (SAICSIT)
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
2313-7835