Novi pristupi u rešavanju optimizacionog problema rimske dominaciuje na grafovima

eBibliothek Repositorium

 
 

Novi pristupi u rešavanju optimizacionog problema rimske dominaciuje na grafovima

Zur Kurzanzeige

dc.contributor.advisor Savić, Aleksandar
dc.contributor.author Ivanović, Marija
dc.date.accessioned 2022-07-05T13:21:49Z
dc.date.available 2022-07-05T13:21:49Z
dc.date.issued 2022
dc.identifier.uri http://hdl.handle.net/123456789/5431
dc.description.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. en_US
dc.description.provenance Submitted by Slavisha Milisavljevic (slavisha) on 2022-07-05T13:21:49Z No. of bitstreams: 1 MarijaIvanovic_Disertacija_saPotpisanimIzjavama.pdf: 1958289 bytes, checksum: 3032452550a470042459cc049a78eb0d (MD5) en
dc.description.provenance Made available in DSpace on 2022-07-05T13:21:49Z (GMT). No. of bitstreams: 1 MarijaIvanovic_Disertacija_saPotpisanimIzjavama.pdf: 1958289 bytes, checksum: 3032452550a470042459cc049a78eb0d (MD5) Previous issue date: 2022 en
dc.language.iso sr en_US
dc.publisher Beograd en_US
dc.title Novi pristupi u rešavanju optimizacionog problema rimske dominaciuje na grafovima en_US
mf.author.birth-place Požarevac en_US
mf.author.birth-country Srbija en_US
mf.author.residence-state Srbija en_US
mf.author.citizenship Srpsko en_US
mf.author.nationality Srpkinja en_US
mf.subject.area Optimization en_US
mf.subject.keywords integer linear programming, mixed integer linear programming, com- binatorial optimization, metaheuristics, variable neighborhood search en_US
mf.subject.subarea Discrete optimization en_US
mf.contributor.committee Dražić, Milan
mf.contributor.committee Davidović, Tatjana
mf.contributor.committee Urošević, Dragan
mf.university.faculty Mathematical faculty en_US
mf.document.references 93 en_US
mf.document.pages 171 en_US
mf.document.location Beograd en_US
mf.document.genealogy-project No en_US
mf.university Belgrade University en_US

Dateien zu dieser Ressource

Dateien Größe Format Anzeige
MarijaIvanovic_ ... a_saPotpisanimIzjavama.pdf 1.958Mb PDF Öffnen

Das Dokument erscheint in:

Zur Kurzanzeige