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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 30.05.2019
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}


Linking options:
  • http://mi.mathnet.ru/eng/crm766
  • http://mi.mathnet.ru/eng/crm/v11/i6/p1101

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Computer Research and Modeling
    Number of views:
    This page:61
    Full text:5
    References:5

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021