1 September 2023 in Cybernetics and Systems Analysis
1 November 2022 in Cybernetics and Systems Analysis
18 October 2022 in Cybernetics and Systems Analysis
29 December 2022 in Cybernetics and Computer Technologies
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.
29 November 2022 in Cybernetics and Computer Technologies
R-algorithms, or subgradient methods with dilation of space in the direction of the difference of two sequential subgradients, were proposed by N.Z.Shor in 1970 in his doctoral thesis. Respective software implementations proved to be competitive with the most effective methods for smooth ill-conditioned problems, both in terms of reliability and calculation time and accuracy of results. The article is devoted to the description of two software implementations of Shor's r-algorithm modification with a constant coefficient of space dilation and adaptive step control. The first program is implemented using the GNU Octave, and the second program is implemented using Python. Material of the paper is presented in three sections. In the first section, we describe a modification of the r-algorithm with a constant coefficient of space dilation in the direction of the difference of two sequential subgradients and an adaptive method for step size adjustment in the direction of the antisubgradient in the transformed space of variables. The software implementation of this modification is presented in the form of octave-function ralgb5a, which allows to find either approximation of the minimum point of a convex function, or approximation of the maximum point of the concave function. The code of the ralgb5a function is given with a brief description of its input and output parameters. The second section describes test experiments to investigate efficiency of the octave-function ralgb5a to maximizing the piecewise linear concave function, which is obtained using the method of non-smooth penalty functions for the linear programming problem. Another example represents minimization of the piecewise linear convex function, which corresponds to the method of least modules. Results of these computational experiments for test problems with 200, 500, 1000, 1500 and 2000 variables are presented to demonstrate the effective operation of the octave-function ralgb5a. The third section describes the python function ralgb5a and provides its code with a description of the input and output parameters. It is show, how the ralgb5a function can be accelerated by setting two parameters. The results of computational experiments to solve the test problem using the method of least modules for 5,000 variables and 10,000 observations are presented.