|
Abstract:
|
In this work some actual combinatorial optimization problems are investigated. Several
di erent methods are suggested for solving the following NP hard problems:
maximally balanced connected partition problem in graph, general maximally balanced
problem with q partitions (q ≥ 2), maximum set splitting problem and p-ary
transitive reduction problem in digraphs. Together with investigation of combinatorial
optimization methods for solving these problems, the applying of these problems
in education is also considered in the dissertation.
For solving each of these problems, metaheuristics are developed: variable neighborhood
search is developed for each problem and genetic algorithm is used for solving
p-ary transitive reduction problem in digraphs. For maximally balanced connected
partition problem a mixed linear programming model is established, which
enables to solve the problem exactly for the instances of lower dimensions.
Achieved numerical results indicate the high level of reliability and usability of
the proposed methods.
Problems solved in this research are of a great interest both in theoretical and
practical points of view. They are used in production, computer networks, engineering,
image processing, biology, social sciences and also in various elds of applied
mathematics and computer science.
In this work the applying of some problems in educational issues is also considered.
It is shown that approaches of nding maximally balanced connected partition
in graph and nding maximum splitting of the set can be successfully used in course
organization, which is veri ed on the concrete examples. Based on the objective
indicators and professor's assessment, the techniques for the identifying the connections
between the lessons, as well as the weights of the lessons are developed.
Thus, whole course can be represented as a connected weighted graph, enabling the
resolving of the lesson partition problem by mathematical approaches.
By assigning the lessons into the appropriate categories (topics area) inside a
iv
course, a collection of subsets (corresponding to the topics) of the set of lessons is
created. If we set the requirement that lessons should be split into two disjoint subsets
(e.g. into the winter and summer semesters), in a way that corresponding topics
are processed in both subsets, then the mathematical model of the requirement and
its solution corresponds to the set splitting problem.
By the developed models of course organization, from which the NP hard problems
arise, in addition to the scienti c contributions in the elds of mathematical
programming and operational research, contributions in educational aspects are
added, especially in the methodology of teaching mathematics and computer science. |