An efficient matheuristic for the minimum-weight dominating set problem. Albuquerque, M. & Vidal, T. *Applied Soft Computing*, 72:527–538, 2018. Paper doi abstract bibtex 1 download A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph belongs either to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a number of applications related to wireless networks design, coding theory, and data mining, among many others. When vertices weights are given, minimizing the total weight of the dominating set gives rise to a problem variant known as the minimum weight dominating set problem. To solve this problem, we introduce a hybrid matheuristic combining a tabu search with an integer programming solver, used to solve subproblems in which only a minority of decision variables, selected relatively to the search history, are left free while the others are fixed. Moreover, we introduce an adaptive penalty to promote the exploration of intermediate infeasible solutions in the search, enhance the algorithm with perturbations and node elimination procedures, and exploit richer neighborhood classes. Extensive experimental analyses on a variety of instance classes demonstrate the good performance of the algorithm, and the contribution of each component in the success of the search is analyzed.

@article{Albuquerque2018,
abstract = {A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph belongs either to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a number of applications related to wireless networks design, coding theory, and data mining, among many others. When vertices weights are given, minimizing the total weight of the dominating set gives rise to a problem variant known as the minimum weight dominating set problem. To solve this problem, we introduce a hybrid matheuristic combining a tabu search with an integer programming solver, used to solve subproblems in which only a minority of decision variables, selected relatively to the search history, are left free while the others are fixed. Moreover, we introduce an adaptive penalty to promote the exploration of intermediate infeasible solutions in the search, enhance the algorithm with perturbations and node elimination procedures, and exploit richer neighborhood classes. Extensive experimental analyses on a variety of instance classes demonstrate the good performance of the algorithm, and the contribution of each component in the success of the search is analyzed.},
author = {Albuquerque, M. and Vidal, T.},
doi = {https://doi.org/10.1016/j.asoc.2018.06.052},
file = {:C$\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Albuquerque, Vidal/Albuquerque, Vidal - 2018 - An efficient matheuristic for the minimum-weight dominating set problem.pdf:pdf},
journal = {Applied Soft Computing},
keywords = {hybrid metaheuristics,integer,large neighborhood search,matheuristics,minimum weight dominating set,programming},
pages = {527--538},
title = {{An efficient matheuristic for the minimum-weight dominating set problem}},
url = {https://arxiv.org/pdf/1808.09809.pdf},
volume = {72},
year = {2018}
}

Downloads: 1

{"_id":"ANKYFCcmCdmrmAPLE","bibbaseid":"albuquerque-vidal-anefficientmatheuristicfortheminimumweightdominatingsetproblem-2018","downloads":1,"creationDate":"2018-10-11T15:20:09.417Z","title":"An efficient matheuristic for the minimum-weight dominating set problem","author_short":["Albuquerque, M.","Vidal, T."],"year":2018,"bibtype":"article","biburl":"https://w1.cirrelt.ca/~vidalt/resources/My%20Collection.bib","bibdata":{"bibtype":"article","type":"article","abstract":"A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph belongs either to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a number of applications related to wireless networks design, coding theory, and data mining, among many others. When vertices weights are given, minimizing the total weight of the dominating set gives rise to a problem variant known as the minimum weight dominating set problem. To solve this problem, we introduce a hybrid matheuristic combining a tabu search with an integer programming solver, used to solve subproblems in which only a minority of decision variables, selected relatively to the search history, are left free while the others are fixed. Moreover, we introduce an adaptive penalty to promote the exploration of intermediate infeasible solutions in the search, enhance the algorithm with perturbations and node elimination procedures, and exploit richer neighborhood classes. Extensive experimental analyses on a variety of instance classes demonstrate the good performance of the algorithm, and the contribution of each component in the success of the search is analyzed.","author":[{"propositions":[],"lastnames":["Albuquerque"],"firstnames":["M."],"suffixes":[]},{"propositions":[],"lastnames":["Vidal"],"firstnames":["T."],"suffixes":[]}],"doi":"https://doi.org/10.1016/j.asoc.2018.06.052","file":":C$\\$:/Users/Thibaut/Documents/Mendeley-Articles/Albuquerque, Vidal/Albuquerque, Vidal - 2018 - An efficient matheuristic for the minimum-weight dominating set problem.pdf:pdf","journal":"Applied Soft Computing","keywords":"hybrid metaheuristics,integer,large neighborhood search,matheuristics,minimum weight dominating set,programming","pages":"527–538","title":"An efficient matheuristic for the minimum-weight dominating set problem","url":"https://arxiv.org/pdf/1808.09809.pdf","volume":"72","year":"2018","bibtex":"@article{Albuquerque2018,\nabstract = {A minimum dominating set in a graph is a minimum set of vertices such that every vertex of the graph belongs either to it, or is adjacent to one vertex of this set. This mathematical object is of high relevance in a number of applications related to wireless networks design, coding theory, and data mining, among many others. When vertices weights are given, minimizing the total weight of the dominating set gives rise to a problem variant known as the minimum weight dominating set problem. To solve this problem, we introduce a hybrid matheuristic combining a tabu search with an integer programming solver, used to solve subproblems in which only a minority of decision variables, selected relatively to the search history, are left free while the others are fixed. Moreover, we introduce an adaptive penalty to promote the exploration of intermediate infeasible solutions in the search, enhance the algorithm with perturbations and node elimination procedures, and exploit richer neighborhood classes. Extensive experimental analyses on a variety of instance classes demonstrate the good performance of the algorithm, and the contribution of each component in the success of the search is analyzed.},\nauthor = {Albuquerque, M. and Vidal, T.},\ndoi = {https://doi.org/10.1016/j.asoc.2018.06.052},\nfile = {:C$\\backslash$:/Users/Thibaut/Documents/Mendeley-Articles/Albuquerque, Vidal/Albuquerque, Vidal - 2018 - An efficient matheuristic for the minimum-weight dominating set problem.pdf:pdf},\njournal = {Applied Soft Computing},\nkeywords = {hybrid metaheuristics,integer,large neighborhood search,matheuristics,minimum weight dominating set,programming},\npages = {527--538},\ntitle = {{An efficient matheuristic for the minimum-weight dominating set problem}},\nurl = {https://arxiv.org/pdf/1808.09809.pdf},\nvolume = {72},\nyear = {2018}\n}\n","author_short":["Albuquerque, M.","Vidal, T."],"key":"Albuquerque2018","id":"Albuquerque2018","bibbaseid":"albuquerque-vidal-anefficientmatheuristicfortheminimumweightdominatingsetproblem-2018","role":"author","urls":{"Paper":"https://arxiv.org/pdf/1808.09809.pdf"},"keyword":["hybrid metaheuristics","integer","large neighborhood search","matheuristics","minimum weight dominating set","programming"],"metadata":{"authorlinks":{"vidal, t":"https://bibbase.org/show?bib=https%3A%2F%2Fw1.cirrelt.ca%2F%7Evidalt%2Fresources%2FMy%2520Collection.bib"}},"downloads":1},"search_terms":["efficient","matheuristic","minimum","weight","dominating","set","problem","albuquerque","vidal"],"keywords":["hybrid metaheuristics","integer","large neighborhood search","matheuristics","minimum weight dominating set","programming"],"authorIDs":["awoTsndRPACdYbwLY"],"dataSources":["yinfondEAJRbDM9sJ","sempRA6PhmAdGk3yG"]}