2022, issue 4, p. 56-81
Received 13.12.2022; Revised 18.12.2022; Accepted 20.12.2022
Published 29.12.2022; First Online 28.02.2023
https://doi.org/10.34229/2707-451X.22.4.5
Previous | FULL TEXT (in Ukrainian) | Next
Using the NEOS Server for Solving Two Classes of Optimization Problems
Halyna Bila 1,
Oleksandr Korchynskyy 2, Petro Stetsyuk 1 * 
, Olha Khomiak 1 , Serhiy Shekhovtsov 3
1 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
2 Uzhhorod National University, Ukraine
3 Kharkiv National University of Radio Electronics, Ukraine
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
NEOS server provides free access to the library of necessary software for solving optimization problems. The effective numerical methods developed can be used for a specific application or for solving a wide range of mathematical programming problems.
The article is devoted to researching the possibilities of solving optimization problems using NEOS server on the example of two mathematical programming problems: a linear Boolean programming problem for the well-known m-traveler problem and nonlinear programming problem for a special multiextremal problem on the Stiefel’s manifold.
The material of the work is presented in 4 sections. Chapter 1 describes general information about using NEOS server for solving optimization problems and focuses on AMPL mathematical programming language as its component. Comparison of the frequency of use of AMPL, GAMS and other input data formats available on the server was conducted.
The second section describes the principle of solving optimization problems using NEOS and provides a list of AMPL-supporting solvers available on the server. Statistics of use frequency of the solvers CPLEX, Gurobi and BARON in comparison with other solvers available on the server, as well as general statistics of the number of solved problems on the server in 2021 are given.
Chapter 3 describes linear Boolean programming problems for the m-travelers problem, which is equivalent to the well-known traveling salesman problem. Performance indicators for solving these problems using CPLEX and Gurobi solvers are given.
In Chapter 4 a study of nonlinear programming problem for a special multiextremal problem on the Stiefel’s manifold is conducted. General formulation of the problem and the formulation of its partial cases depending on the constraints imposed on vector components are given. The efficiency of solving test cases using BARON solver was investigated depending on the number of vectors and their dimensions.
Keywords: optimization, NEOS server, AMPL, NEOS solvers, travelling salesman problem, Stiefel’s manifold.
Cite as: Bila H., Korchynskyy O., Stetsyuk P., Khomiak O., Shekhovtsov S. Using the NEOS Server for Solving Two Classes of Optimization Problems. Cybernetics and Computer Technologies. 2022. 4. P. 56–81. (in Ukrainian) https://doi.org/10.34229/2707-451X.22.4.5
References
1. NEOS Solver. https://neos-server.org/ (accessed: 15.12.2022)
2. Dolan E. The NEOS Server 4.0 Administrative Guide, 2001. 41 p. https://doi.org/10.2172/822567
3. Moré J.J., Czyzyk J.J., Mesnier M.P. The Network-Enabled Optimization System (NEOS) Server. 1998. 13 p.
4. Gropp W., Moré J.J. Optimization Environments and the NEOS Server. 1997. 18 p.
5. Fourer R., Gay D., Kernighan B. AMPL, A Modeling Language for Mathematical Programming. Belmont: Duxburry Press, 2003. 517 p.
6. CPLEX Optimizer. High-performance mathematical programming solver for linear programming, mixed-integer programming and quadratic programming. https://www.ibm.com/analytics/cplex-optimizer (accessed: 15.12.2022)
7. Gurobi Optimization, Inc., Gurobi Optimizer Reference Manual, 2014. http://www.gurobi.com/ (accessed: 15.12.2022)
8. Tawarmalani M., Sahinidis N.V. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming. 2005. 103 (2). P. 225–249. https://doi.org/10.1007/s10107-005-0581-8
9. Sahinidis, N.V. BARON 21.1.13: Global Optimization of Mixed-Integer Nonlinear Programs. User's manual. 2021.
10. Kilinc M., Sahinidis N.V. Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems in BARON. Optimization Methods and Software. 2018. 33. P. 540–562. https://doi.org/10.1080/10556788.2017.1350178
11. Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulation of travelling salesman problem. J. ACM. 1960. 3. P. 326–329. https://doi.org/10.1145/321043.321046
12. Gameckiy A.F., Solomon D.I. Operations research. V. II. Chisinau, Evrika, 2008. 592 p. (In Russian)
13. Alekseeva E.V. Construction of mathematical models of integer linear programming. Examples and problems: Ucheb. Posobie / Novosib.gos. universitet. Novosibirsk, 2012. 131 p. (In Russian)
14. Stetsyuk P.I., Nuriyev U.G., Nuriyeva F.U. New integer linear programming model for the traveling salesman problem. Proceedings of the 7th International Scientific Conference “Mathematical modeling, optimization and information technologies”, 15-19 November 2021. P. 319–325. (In Russian)
15. Stetsyuk P., Solomon D., Grygorak M. Problems on shortest k-node cycles and paths. Cybernetics and Computer Technologies. 2021. 3. P. 15–33. (In Ukrainian) https://doi.org/10.34229/2707-451X.21.3.2
16. TSPLIB: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (accessed: 15.12.2022)
17. Balogh J., Csendes T., Rapcsák T. Some Global Optimization Problems on Stiefel Manifold. Journal of Global Optimization. 2004. 30. P. 91–101. https://doi.org/10.1007/s10898-004-0574-9
18. Shor N.Z., Stetsyuk P.I., Berezovskyi O.A. Dual bounds for special optimization quadratic type problem on Stiefel manifolds. Theory of optimal solutions. 2004. P. 3–10. (In Russian) http://dspace.nbuv.gov.ua/handle/123456789/84870
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next