Open AccessA New Family of Algorithms Searching Optimal Solutions to Discrete Optimization Problems
Author(s) -
Vitaly O. Groppen
Publication year - 2021
Publication title -
international journal of computers
Language(s) - English
Resource type - Journals
ISSN - 1998-4308
DOI - 10.46300/9108.2021.15.23
Subject(s) - enumeration , basis (linear algebra) , algorithm , a priori and a posteriori , modular design , mathematics , mathematical optimization , computer science , discrete optimization , optimization problem , discrete mathematics , philosophy , geometry , epistemology , operating system
A new family of algorithms searching globally optimal solutions to discrete programming problems is proposed. It is proved that the effectiveness of this method depends only on the number of variables of the problem being solved. The main difference from the methods of implicit enumeration is in the ability to a priori predict, solving by the one of proposed methods any extreme problem with Boolean variables, the number of iterations, the running time, and the amount of RAM used. The results of experimental verification of the effectiveness of various versions of modular enumeration procedures and, on their basis, recommendations for the use of these algorithms are given.