Browsing Mathematics by Author "Ivanović, Marija"
Strana 1-1 od 1
-
Ivanović, Marija (Beograd , 2022)[more][less]
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. URI: http://hdl.handle.net/123456789/5431 Files in this item: 1
MarijaIvanovic_ ... a_saPotpisanimIzjavama.pdf ( 1.958Mb )
Strana 1-1 od 1