Abstract:

In the last few decades, the theory of communications networks has seen great development. There are many traffic problems known to practice, which have prompted theoreticians from mathematics, computer scientists, and other researchers to undertake a deeper study of this area.

Scientists have, of course, found effective algorithms for many problems to find a solution in "reasonable time", yet there are a huge number of problems that no such algorithms exist yet.

In this article, we deal with the problems that have arisen from the practice where it is necessary to build control or service systems in the transport network, the means of which must be concentrated in several nodes of the network for reasons of better utilization. The cost of building such a system is proportional to the number of deployed centers. This creates a broad class of tasks in which, under certain technological conditions, it is necessary to minimize the number of locations that are located while securing the operation of all processes in the network. An alternative to these tasks is to maximize the serviceability of these processes at a given number of centers. In general, these tasks are called combinatorial.

Two approaches can be used to address the solution, with the exact method of integer programming or heuristics. In the first case, the question arises as to whether a larger dimension can be resolved at a "reasonable time" and in the latter case we risk that the solution found quickly will be much worse than optimal.
This article is dedicated to covering problems.

We present the problem-solving tasks, the top-level graphs and the set-up tasks. These tasks are described both as optimization problems, as well as their equivalents, decision-making problems. Then we will also describe the mathematical model of these tasks as a role of integer programming. We also present a solution methodology. Here are the exact methods and heuristics. Finally, we present research and experimentation.

Keywords:

Mathematics, method, algorithm, exact solution, heuristic solution, combinatorial problem.