Heuristic procedure neural networks for the capacitated minimum spanning tree problem

Combinatorial optimization problems are by nature very difficult to solve, and the Capacitated Minimum Spanning Tree problem is one such problem. Much work has been done in the management sciences to develop heuristic solution procedures that suboptimally solve large instances of the Capacitated Minimum Spanning Tree problem in a reasonable amount of time. The Capacitated Minimum Spanning Tree problem is used in this paper to develop and demonstrate a hybrid neural network methodology that incorporates heuristic methods into the neural network topological design. The heuristic procedure is embedded into the neural network topological design, and an iterative improvement process is performed using the neural network. The semi-relaxed energy function of the problem is used to develop a neural network weight adjustment procedure that modifies the problem costs. In three-quarters (75%) of our experiments, the hybrid neural networks produced better results than any of the traditional procedures tested.