Open AccessModels and methods for One-Dimensional Space Allocation Problem with forbidden zones
Author(s) -
G. G. Zabudsky,
N. S. Veremchuk
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1441/1/012177
Subject(s) - extension (predicate logic) , integer programming , mathematical optimization , pipeline (software) , line (geometry) , space (punctuation) , computer science , real line , combinatorial optimization , optimization problem , mathematics , combinatorics , geometry , programming language , operating system
We consider an extension of the well–known optimization placement problem. The problem is One–Dimensional Space Allocation Problem (ODSAP). The classical formulation of the problem is to place rectangular connected objects on a line with the minimum total cost of connections between them. The extension of the problem is that there are fixed objects (forbidden zones) on the line. The objects are impossible to place in forbidden zones. The placed objects are connected among themselves and with the zones. The configuration of connections between objects is defined by a network. A similar situation arises, for example, when designing the location of technological equipment of petrochemical enterprise. It is necessary to place units of equipment so that the total cost of the pipeline ties was minimal. In this article a review of the models and methods to solve of the classical ODSAP is given. The properties of the problem with the forbidden zones are noted. Models of combinatorial optimization and integer programming for the problem are constructed. Algorithms for finding an approximate solution and branch and bounds are described. Results of computational experiments are reported.