Multi-Objective Neighborhood Search Algorithm Based on Decomposition for Multi-Objective Minimum Weighted Vertex Cover Problem

Shuli Hu, Xiaoli Wu, Huan Liu, Yiyuan Wang, Ruizhi Li and Minghao Yin
Additional contact information
Shuli Hu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Xiaoli Wu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Huan Liu: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Yiyuan Wang: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China
Ruizhi Li: School of Management Science and Information Engineering, Jilin University of Finance and Economics, Changchun 130117, China
Minghao Yin: School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China

Sustainability, 2019, vol. 11, issue 13, 1-21

Abstract: The multi-objective minimum weighted vertex cover problem aims to minimize the sum of different single type weights simultaneously. In this paper, we focus on the bi-objective minimum weighted vertex cover and propose a multi-objective algorithm integrating iterated neighborhood search with decomposition technique to solve this problem. Initially, we adopt the decomposition method to divide the multi-objective problem into several scalar optimization sub-problems. Meanwhile, to find more possible optimal solutions, we design a mixed score function according to the problem feature, which is applied in initializing procedure and neighborhood search. During the neighborhood search, three operators ( A d d , D e l e t e , S w a p ) explore the search space effectively. We performed numerical experiments on many instances, and the results show the effectiveness of our new algorithm (combining decomposition and neighborhood search with mixed score) on several experimental metrics. We compared our experimental results with the classical multi-objective algorithm non-dominated sorting genetic algorithm II. It was obviously shown that our algorithm can provide much better results than the comparative algorithm considering the different metrics.

Keywords: multi-objective; decomposition; vertex cover; neighborhood search (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2071-1050/11/13/3634/pdf (application/pdf)
https://www.mdpi.com/2071-1050/11/13/3634/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jsusta:v:11:y:2019:i:13:p:3634-:d:244959

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().