FAST ALGORITHM FOR SOLVING A ONE-DIMENSIONAL UNCLOSED DESIRABLE NEIGHBORS PROBLEM
DOI:
https://doi.org/10.15588/1607-3274-2022-1-4Keywords:
problem of desirable neighbors, unclosed problem, combinatorial problem, chain of vertices of the graph, optimal distribution.Abstract
Contex. The paper formulates a general combinatorial problem for the desired neighbors. Possible areas of practical application of the results of its development are listed. Within the framework of this problem, an analysis of the scientific literature on the optimization of combinatorial problems of practical importance that are close in subject is carried out, on the basis of which the novelty of the formulated problem accepted for scientific and algorithmic development is established.
Objective. For a particular case of the problem, the article formulates a one-dimensional unclosed integer combinatorial problem of practical importance about the desired neighbors on the example of the problem of distributing buyers on land plots, taking into account their recommendations on the desired neighborhood.
Method. A method for solving the mentioned problem has been developed and an appropriate effective algorithm has been created, which for thousands of experimental sets of hundreds of distribution subjects allows to get the optimal result on an ordinary personal computer in less than a second of counting time. The idea of developing the optimization process is expressed, which doubles the practical effect of optimization by cutting off unwanted neighbors without worsening the maximum value of the desirability criterion.
Results. The results of the work include the formulation of a one-dimensional unclosed combinatorial problem about the desired neighbors and an effective algorithm for its solution, which makes it possible to find one, several, and, if necessary, all the options for optimal distributions. The main results of the work can also include the concept and formulation of a general optimization combinatorial problem of desirable neighbors, which may have theoretical and practical prospects.
Conclusions. The method underlying the algorithm for solving the problem allows, if necessary, to easily find all the best placement options, the number of which, as a rule, is very large. It is established that their number can be reduced with benefit up to one by reducing the number of undesirable neighborhoods, which contributes to improving the quality of filtered optimal distributions in accordance with this criterion. The considered problem can receive prospects for evolution and development in various subject areas of the economy, production, architecture, urban studies and other spheres.
References
Khodamoradi K., Krishnamurti R. Prize Collecting Travelling Salesman Problem, Fast Heuristic Separations, In Proceedings of 5th the International Conference on Operations Research and Enterprise Systems, 2016, Vol. 1, pp. 380–387. DOI: 10.5220/0005758103800387
Babin G., Deneault S., Laporte G. Improvements to the Oropt heuristic for the symmetric travelling salesman problem, The Journal of the Operational Research Society, 2005, Vol. 58, No. 3, pp. 402–407. DOI: 10.1057/palgrave.jors.2602160
Land A. H., Doig A. G. An Automatic Method for Solving Discrete Programming Problems, Econometrica, 2010, Vol. 28, No. 3, pp. 497–520. DOI: 10.1007/978-3-54068279-0_5
Robert W. I. An efficient algorithm for the “stable roommates” problem, Journal of Algorithms, 1985, Vol. 6, pp. 577–595. DOI: 10.1016/0196-6774(85)90033-1
Kenneth P. B., Peter G. D. Non-sexist solution of the ménage problem, The American Mathematical Monthly, 1986, Vol. 93, No. 7, pp. 514–519. DOI: 10.2307/2323022
Holst L. On the ‘problème des ménages’ from a probabilistic viewpoint, Statistics and Probability Letters, 1991, Vol. 11, pp. 225–231. DOI: 10.1016/0167-7152(91)90147-J
Gessel I., Rota G.-C. Classic Papers in Combinatorics. Boston, Birkhäuser, 2009, 501 p. DOI: 10.1007/978-08176-4842-8_8
Li Y.Z., Ingason H., Lonnermark A. Fire development in different scales of train carriages, Fire Safety Sci 11, 2014, pp. 302–315. DOI: 10.3801/IAFSS.FSS.11-302
Xiting G., Sean X. Z. Optimal Production Planning with Emissions Trading, Operations Research, 2013, Vol. 61, No. 4, pp. 908–924. DOI:10.2307/23481804
Xu Y., Wenye W. Localized Scheduling for Practical and Optimal Capacity Utilization in Large Wireless Networks, IEEE Global Telecommunications Conference, 2009, pp. 1–6. DOI: 10.1109/GLOCOM.2009.5425722
Dever E., Sertysesilisik B., Rostron, J. The refurbishment of small-scale retail premises in relation to the Disability Discrimination Act 1995, Journal of Retail & Leisure Property, 2009, Vol. 8, pp. 79–90. DOI: 10.1057/rlp.2009.1
Rogers D., Keane A., Alizadeh T., Nelson J. Understanding Urbanism. Singapore, Palgrave Macmillan, 2020, pp. 179– 194. DOI: 10.1007/978-981-15-4386-9_1
Arroyo F. Sown in Earth: Essays of Memory and Belonging. Chicago, University of Arizona Press, 2020, 280 p. DOI: 10.2307/j.ctvw04c0s.
Gryncewicz W., Kutera R. Web Oriented Architectural Styles for Integrating Service e-Marketplace Systems, In Proceedings of the Seventh International Symposium on Business Modeling and Software Design, 2017, pp. 72–80. DOI: 10.5220/0006527600720080
Lavrov I., Maksimova L., Corsi G. Problems in Set Theory, Mathematical Logic and the Theory of Algorithms. Boston, Springer, 2003, 517 p. DOI: 10.1007/978-1-4615-01855_3
Goldreich O. P. NP and NP-Completeness: The Basics of Computational Complexity. Cambridge, Cambridge University Press, 2010, 216 p. DOI: 10.1017/CBO9780511761355
Ellard D. Poly-iamond enumeration, The Mathematical Gazette, 1982, Vol. 66, No. 438, pp. 310–314. DOI: 10.2307/3615527
Wätjen D. Parallel communicating limited and uniformly limited 0L systems, Theoretical Computer Science, 2001, Vol. 255, pp. 163–191. DOI: 10.1016/S03043975(99)00162-0
Polyakov A. B. On equilibrium distributions on a set of permutations of the integers, Russian Mathematical Surveys, 1999, Vol. 54, No. 2, pp. 450–452. DOI: 10.1070/RM1999v054n02ABEH000145
Shemitz J. NET 2.0 for Delphi Programmers. Berkeley, Apress, 2006, 280 p. DOI: 10.1007/978-1-4302-0174-8_10
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 В. А. Коднянко
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
