Mathematical Modeling
Vol. 4 (2020), Issue 1, pg(s) 3-6

THEORETICAL FOUNDATIONS AND SPECIFICITY OF MATHEMATICAL MODELLING

Neural network approaches for a facility location problem

  • 1 Faculty of Mathematics and Informatics – Sofia University “St. Kliment Ohridski”, Bulgaria

Abstract

This paper examines the possibility to use neural networks for approximately solving the MiniSum problem, a classic facility location problem. For this we first create a set of realistic MiniSum instances, based on the Bulgarian road network. Two standard neural network approaches – Hopfield networks and Boltzmann machines, are then applied to the instances. Since the quality of solutions is not satisfactory, the reasons for the poor performance are discussed. An improved neural network approach is then proposed. This approach has excellent performance on the MiniSum instances. It always finds solutions just several percent worse than the optimum, and is often able to find the exact optimum.

Keywords

References

  1. "Cbc (Coin-or branch and cut) mixed integer linear programming solver", https://github.com/coin-or/Cbc
  2. Hoos H. H., Stützle T., "Stochastic Local Search: Foundations and Applications", The Morgan Kaufmann Series in Artificial Intelligence, 2005.
  3. Hopfield J. J., Tank D. W., "Neural Computation of Decisions in Optimization Problems", Biological Cybernetics, 52 (1985) 141- 152.
  4. Karp R. M., "Reducibility among Combinatorial Problems", Complexity of Computer Computations. The IBM Research Symposia Series, Springer, Boston, 1972.
  5. Korst J.H.M., Aarts E.H.L., "Combinatorial optimization on a Boltzmann machine", J. of Parallel and Distributed Computing, Vol. 6, pp. 331–357, 1989.
  6. OpenStreetMap contributors (2015). Planet dump [Data file from 27/12/2019]. Retrieved from https://planet.openstreetmap.org.
  7. Rojas R., "Neural Networks – A Systematic Introduction", Springer-Verlag, 1996.
  8. Wilson G. V., Pawley G. S., "On the stability of the Travelling Salesman Problem algorithm of Hopfield and Tank", Biological Cybernetics, 58 (1988), 63-70.

Article full text

Download PDF