A 3-flip neighborhood local search for the set covering problem |
| |
| Institution: | 1. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan;2. Sumitomo Electric Information Systems Co., Ltd., 2-1-3, Nishimiyahara, Yodogawa-ku, Osaka 532-0004, Japan;3. Department of Informatics, School of Science and Technology, Kwansei Gakuin University, 2-1 Gakuen, Sanda 669-1337, Japan;1. Department of Civil and Environmental Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801, United States;2. Department of Systems and Industrial Engineering, The University of Arizona, Tucson, AZ 85721, USA;3. Research Center for Modern Logistics, Graduate School at Shenzhen, Tsinghua University, Shenzhen 518055, China;1. Department of Management, Dehaghan Branch, Islamic Azad University, Dehaghan, Iran;2. Department of Industrial Engineering, Yazd University, Yazd, Iran;1. College of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian 116025, PR China;2. Institute of Systems Engineering, State Key Laboratory of Synthetic Automation for Process Industries, Northeastern University, Shenyang 110004, PR China;3. Information Technology Center, China Mobile Group Liaoning Co., Ltd, No. 6 Xinlong Street, Hunnanxin District, Shenyang 110179, PR China;1. CIRRELT, Département d’informatique et de recherche opérationnelle, Université de Montréal, Canada;2. CIRRELT, Département de management et technologie, École des Sciences de la Gestion, UQAM, Canada;3. CIRRELT, Département de mathématiques et de génie industriel, École Polytechnique, Montréal, Canada;4. ICD-LOSI, Université de Technologie de Troyes, France;1. School of Management, Tianjin Polytechnic University, Tianjin, China;2. School of Electrical Engineering & Automation, Tianjin Polytechnic University, Tianjin, China |
| |
| Abstract: | The set covering problem (SCP) calls for a minimum cost family of subsets from n given subsets, which together covers the entire ground set. In this paper, we propose a local search algorithm for SCP, which has the following three characteristics. (1) The use of 3-flip neighborhood, which is the set of solutions obtainable from the current solution by exchanging at most three subsets. As the size of 3-flip neighborhood is O(n3), the neighborhood search becomes expensive if implemented naively. To overcome this, we propose an efficient implementation that reduces the number of candidates in the neighborhood without sacrificing the solution quality. (2) We allow the search to visit the infeasible region, and incorporate the strategic oscillation technique realized by adaptive control of penalty weights. (3) The size reduction of the problem by using the information from the Lagrangian relaxation is incorporated, which is indispensable for solving very large instances. According to computational comparisons on benchmark instances with other existing heuristic algorithms for SCP, our algorithm performs quite effectively for various types of problems, especially for very large-scale instances. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
