On Decision-Making Algorithms in Discrete Optimization Problems
The article provides a comparative analysis of the efficiency of using several predictor functions, i.e. special auxiliary functions a priori evaluating the feasibility of choosing a separating element for a certain iterative algorithm. Cases of one, two or three predictors are considered, as well a...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
The Fund for Promotion of Internet media, IT education, human development «League Internet Media»
2023-10-01
|
| Series: | Современные информационные технологии и IT-образование |
| Subjects: | |
| Online Access: | http://sitito.cs.msu.ru/index.php/SITITO/article/view/987 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850259555216261120 |
|---|---|
| author | Yulia Terentyeva |
| author_facet | Yulia Terentyeva |
| author_sort | Yulia Terentyeva |
| collection | DOAJ |
| description | The article provides a comparative analysis of the efficiency of using several predictor functions, i.e. special auxiliary functions a priori evaluating the feasibility of choosing a separating element for a certain iterative algorithm. Cases of one, two or three predictors are considered, as well as various schemes of so-called voting, that is, rules for choosing a solution. The probability of making the correct decision by the predictor function is assessed. The qualitative results of the conducted research are presented, and recommendations for the use of predictors are given. A comparative analysis of the use of schemes formed by predictors in quantities from one to three inclusive is performed in detail. The analysis is performed according to the principle of "each with each" with the presentation of the conditions of preference of one scheme over another. Among all the schemes, the leading ones were the scheme of three predictors with the majority vote “voting” scheme and the scheme consisting of one predictor, which is one of three in the leading scheme and has the highest probability of making the correct decision of the three. An assessment was made of the measure of the area characterizing the preference of one leading scheme over another. It has been demonstrated that the scheme consisting of one “smartest” predictor has a preference region that is more than 24 times larger than another leading scheme of three predictors voting by the majority vote principle and including the “smartest” predictor. The procedures for applying predictor functions are relevant in the branch and bound method. In particular, the relevance of these studies is mainly due to the need for an effective solution to discrete optimization problems that arise in the process of analyzing and designing high-dimensional communication networks. The most important task and area of application of research is to find the optimal set of edges to be completed in the graph of a communication network, which ensures a given stability in all communication directions.
This approach can be extended to situations not directly related to discrete optimization algorithms on graphs. In particular, the obtained results can be used in organizing the receipt of expert opinions in the presence of one, two or three experts with different qualifications, and possible schemes for their decision-making. |
| format | Article |
| id | doaj-art-ba9748c7cebf47c1aa2ede03dd01764a |
| institution | OA Journals |
| issn | 2411-1473 |
| language | Russian |
| publishDate | 2023-10-01 |
| publisher | The Fund for Promotion of Internet media, IT education, human development «League Internet Media» |
| record_format | Article |
| series | Современные информационные технологии и IT-образование |
| spelling | doaj-art-ba9748c7cebf47c1aa2ede03dd01764a2025-08-20T01:55:50ZrusThe Fund for Promotion of Internet media, IT education, human development «League Internet Media»Современные информационные технологии и IT-образование2411-14732023-10-0119362263210.25559/SITITO.019.202303.622-632On Decision-Making Algorithms in Discrete Optimization ProblemsYulia Terentyeva0https://orcid.org/0000-0002-2418-003XCenter for Information Technology and Systems of Executive Authorities named after A.V. Starovoitov, Moscow, RussiaThe article provides a comparative analysis of the efficiency of using several predictor functions, i.e. special auxiliary functions a priori evaluating the feasibility of choosing a separating element for a certain iterative algorithm. Cases of one, two or three predictors are considered, as well as various schemes of so-called voting, that is, rules for choosing a solution. The probability of making the correct decision by the predictor function is assessed. The qualitative results of the conducted research are presented, and recommendations for the use of predictors are given. A comparative analysis of the use of schemes formed by predictors in quantities from one to three inclusive is performed in detail. The analysis is performed according to the principle of "each with each" with the presentation of the conditions of preference of one scheme over another. Among all the schemes, the leading ones were the scheme of three predictors with the majority vote “voting” scheme and the scheme consisting of one predictor, which is one of three in the leading scheme and has the highest probability of making the correct decision of the three. An assessment was made of the measure of the area characterizing the preference of one leading scheme over another. It has been demonstrated that the scheme consisting of one “smartest” predictor has a preference region that is more than 24 times larger than another leading scheme of three predictors voting by the majority vote principle and including the “smartest” predictor. The procedures for applying predictor functions are relevant in the branch and bound method. In particular, the relevance of these studies is mainly due to the need for an effective solution to discrete optimization problems that arise in the process of analyzing and designing high-dimensional communication networks. The most important task and area of application of research is to find the optimal set of edges to be completed in the graph of a communication network, which ensures a given stability in all communication directions. This approach can be extended to situations not directly related to discrete optimization algorithms on graphs. In particular, the obtained results can be used in organizing the receipt of expert opinions in the presence of one, two or three experts with different qualifications, and possible schemes for their decision-making.http://sitito.cs.msu.ru/index.php/SITITO/article/view/987heuristic algorithmsdiscrete optimization problemsgraph theory modelsgreedy algorithms |
| spellingShingle | Yulia Terentyeva On Decision-Making Algorithms in Discrete Optimization Problems Современные информационные технологии и IT-образование heuristic algorithms discrete optimization problems graph theory models greedy algorithms |
| title | On Decision-Making Algorithms in Discrete Optimization Problems |
| title_full | On Decision-Making Algorithms in Discrete Optimization Problems |
| title_fullStr | On Decision-Making Algorithms in Discrete Optimization Problems |
| title_full_unstemmed | On Decision-Making Algorithms in Discrete Optimization Problems |
| title_short | On Decision-Making Algorithms in Discrete Optimization Problems |
| title_sort | on decision making algorithms in discrete optimization problems |
| topic | heuristic algorithms discrete optimization problems graph theory models greedy algorithms |
| url | http://sitito.cs.msu.ru/index.php/SITITO/article/view/987 |
| work_keys_str_mv | AT yuliaterentyeva ondecisionmakingalgorithmsindiscreteoptimizationproblems |