Open AccessModular enumeration - a new method for solving discrete programming problems
Author(s) -
Vitaly O. Groppen
Publication year - 2022
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/2162/1/012022
Subject(s) - enumeration , modular design , boolean data type , scheme (mathematics) , a priori and a posteriori , computer science , mathematics , boolean algebra , mathematical optimization , algorithm , theoretical computer science , discrete mathematics , programming language , mathematical analysis , philosophy , epistemology
A new approach resulting in a new group of algorithms for finding globally optimal solutions to discrete programming problems with Boolean variables is proposed. It is proved that the effectiveness of this method depends only on the number of variables of the problem to be solved and of the amount of RAM of used computer. The main difference from the existing methods of implicit enumeration is in the ability for some of the modular enumeration procedures to a priori predict, solving any extreme problem with Boolean variables, the number of iterations, the gain in running time in comparison with the traditional enumeration scheme, as well as the amount of RAM used. The experimental results confirm high efficiency of the proposed approaches.