|
Abstract:
|
This dissertation focuses on the Roman domination problem and its two
modifications. Improvements and relaxations of two integer linear programming for-
mulations for the Roman domination problem from the literature are introduced,
proved to be equivalent to the existing ones despite of the variables relaxation and
usage of fewer number of constraints and compared by standard optimization solvers,
CPLEX and Gurobi. Improved formulations can be equally used as original ones,
but, as it can be seen from numerical results, for some instances, they can be more
useful. Given the fact that old and new formulations can not be used for some
large size instances, and that algorithms for solving Roman domination problem
are mostly defined for some particular graph classes, the aim of this research was
to find a new algorithm that can be used for solving Roman domination problem
on all graph classes and all graph sizes. Although the Roman domination problem
belongs to the class NP, presented algorithm is able to find solution value equal to
optimal solution value on very large number of instances in less then a second. For
the first modification of the Roman domination problem, named Restrained Roman
domination problem, a new mixed integer linear programming formulation is intro-
duced and, to the best of the author’s knowledge, this formulation is the first in
the literature. For the second modification of the Roman domination problem, the
Weak Roman domination problem, an improved integer linear programming formu-
lation is presented. Improved formulation is also proved to be correct, equivalent
to the existing formulation from the literature and compared using standard op-
timization solvers, CPLEX and Gurobi. Numerical results showed the advantage
of the improved formulation on almost all tested instances. Additionally, an im-
proved linear-time algorithm for solving the Weak Roman domination problem on
block graphs is introduced and, similarly to the Roman domination problem, a new
algorithm, based on the variable neighborhood search method is presented. With
the new variable neighborhood search based algorithm we aimed to find solution of
the Weak Roman domination problem equal to the optimal on very large number of
tested instances. For instances for which some solution value is found but not proved
to be an optimal, presented algorithm provided the new lower-bounds. Even more,
for some instances, where optimization solvers were not able to prove optimality or
to find any solution, new solutions are found. |