Bulletin of Irkutsk State University. Series Mathematics
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



Bulletin of Irkutsk State University. Series Mathematics:
Year:
Volume:
Issue:
Page:
Find






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


Bulletin of Irkutsk State University. Series Mathematics, 2014, Volume 9, Pages 10–25 (Mi iigum196)  

This article is cited in 1 scientific paper (total in 1 paper)

Solving Weber Problem on Plane with Minimax Criterion and Forbidden Gaps

G. G. Zabudsky, N. S. Veremchuk

Sobolev Institute of Mathematics of the Siberian Branch of the RAS, 13, Pevtsova St., Omsk, 644043
Full-text PDF (286 kB) Citations (1)
References:
Abstract: Location problems of various facilities are a wide class of operations research. The variety of statements of location problems is depends on the area in which are to be placed facilities and various restrictions and types of criteria. Important subclass of location problems of the interconnected facilities is the Weber problem. Two criteria of optimality are considered: minimization of total cost of communications between facilities or minimization of the maximum communication cost. Minimax Weber problem with a rectangular metrics is researched by J. G. Morris, R. L. Francis and T. Ichimori. In this paper, the problem of optimum location of facilities on the plane with the fixed facilities located on it and the rectangular forbidden gaps, with the borders parallel to axes of coordinates is considered. The located facilities are connected among themselves and with fixed facilities. The criterion is minimization of the maximum cost of communications between all facilities. Location in forbidden gaps is not allowed. The rectangular metrics is used. Properties of the problem, model of integer linear programming with Boolean variables are described. It is proved that it is sufficient to consider a subset of admissible solutions to find the optimum. Three variants of branch and bounds algorithm with different lower bounds on the goal function are developed. Computational experiment on comparison of efficiency of one of these algorithms and the IBM ILOG CPLEX is presented. Usage of the obtained property is perspective both in combinatorial methods as well as in integer programming methods for solving the problem.
Keywords: location problem, integer programming, minimax Weber problem, forbidden gaps, algorithm branch and bounds.
Document Type: Article
UDC: 519.854, 004.8, 004.023
Language: Russian
Citation: G. G. Zabudsky, N. S. Veremchuk, “Solving Weber Problem on Plane with Minimax Criterion and Forbidden Gaps”, Bulletin of Irkutsk State University. Series Mathematics, 9 (2014), 10–25
Citation in format AMSBIB
\Bibitem{ZabVer14}
\by G.~G.~Zabudsky, N.~S.~Veremchuk
\paper Solving Weber Problem on Plane with Minimax Criterion and Forbidden Gaps
\jour Bulletin of Irkutsk State University. Series Mathematics
\yr 2014
\vol 9
\pages 10--25
\mathnet{http://mi.mathnet.ru/iigum196}
Linking options:
  • https://www.mathnet.ru/eng/iigum196
  • https://www.mathnet.ru/eng/iigum/v9/p10
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024