RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Computer Research and Modeling: Year: Volume: Issue: Page: Find

 Computer Research and Modeling, 2019, Volume 11, Issue 6, Pages 1101–1110 (Mi crm766)

THE 3RD BRICS MATHEMATICS CONFERENCE

Linear and nonlinear optimization models of multiple covering of a bounded plane domain with circles

Sh. I. Galiev, A. V. Khor'kov

Tupolev Kazan National Research Technical University–KAI, 10 ul. Karla Marksa, Kazan, 420111, Russia

Abstract: Problems of multiple covering ($k$-covering) of a bounded set $G$ with equal circles of a given radius are well known. They are thoroughly studied under the assumption that $G$ is a finite set. There are several papers concerned with studying this problem in the case where $G$ is a connected set. In this paper, we study the problem of minimizing the number of circles that form a $k$-covering, $k\geq 1$, provided that $G$ is a bounded convex plane domain.
For the above-mentioned problem, we state a $0$$1 linear model, a general integer linear model, and a nonlinear model, imposing a constraint on the minimum distance between the centers of covering circles. The latter constraint is due to the fact that in practice one can place at most one device at each point. We establish necessary and sufficient solvability conditions for the linear models and describe one (easily realizable) variant of these conditions in the case where the covered set G is a rectangle. We propose some methods for finding an approximate number of circles of a given radius that provide the desired k-covering of the set G, both with and without constraints on distances between the circles' centers. Wetreat the calculated values as approximate upper bounds for the number of circles. We also propose a technique that allows one to get approximate lower bounds for the number of circles that is necessary for providing a k-covering of the set G. In the general linear model, as distinct from the 0$$1$ linear model, we require no additional constraint. The difference between the upper and lower bounds for the number of circles characterizesv the quality (acceptability) of the constructed $k$-covering.
We state a nonlinear mathematical model for the $k$-covering problem with the above-mentioned constraints imposed on distances between the centers of covering circles. For this model, we propose an algorithm which (in certain cases) allows one to find more exact solutions to covering problems than those calculated from linear models.
For implementing the proposed approach, we have developed computer programs and performed numerical experiments. Results of numerical experiments demonstrate the effectiveness of the method.

Keywords: linear models of the multiple covering problem, $k$-covering of a bounded set, nonlinear models of the $k$-covering problem with circles of a given radius, solvability conditions for linear models of the $k$-covering problem.

DOI: https://doi.org/10.20537/2076-7633-2019-11-6-1101-1110

Full text: PDF file (110 kB)
Full text: http://crm.ics.org.ru/.../2869
References: PDF file   HTML file

UDC: 519.6:519.147
Accepted:14.11.2019
Language:

Citation: Sh. I. Galiev, A. V. Khor'kov, “Linear and nonlinear optimization models of multiple covering of a bounded plane domain with circles”, Computer Research and Modeling, 11:6 (2019), 1101–1110

Citation in format AMSBIB
\Bibitem{GalKho19} \by Sh.~I.~Galiev, A.~V.~Khor'kov \paper Linear and nonlinear optimization models of multiple covering of a bounded plane domain with circles \jour Computer Research and Modeling \yr 2019 \vol 11 \issue 6 \pages 1101--1110 \mathnet{http://mi.mathnet.ru/crm766} \crossref{https://doi.org/10.20537/2076-7633-2019-11-6-1101-1110}