METHODS OF SOLUTIONS OF COMBINATORIAL PROBLEMS

University of Žilina, Faculty of Humanities (SLOVAKIA)

Appears in: ICERI2020 Proceedings

Publication year: 2020

Pages: 8-16

ISBN: 978-84-09-24232-0

ISSN: 2340-1095

doi: 10.21125/iceri.2020.0009

Publication year: 2020

Pages: 8-16

ISBN: 978-84-09-24232-0

ISSN: 2340-1095

doi: 10.21125/iceri.2020.0009

Conference name: 13th annual International Conference of Education, Research and Innovation

Dates: 9-10 November, 2020

Location: Online Conference

Dates: 9-10 November, 2020

Location: Online Conference

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.

Citation copied to the clipboard successfully.

Sorry, but the download of this paper is restricted to authorized users only.