Exact solutions to generalized vertex covering problems: a comparison of two models

详细信息    查看全文

• 作者：Gary Kochenberger ; Mark Lewis ; Fred Glover ; Haibo Wang
• 关键词：Vertex cover ; Performance evaluation ; Combinatorial problems
• 刊名：Optimization Letters
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：9
• 期：7
• 页码：1331-1339
• 全文大小：359 KB
• 参考文献：1.Alidaee, B., Kochenberger, G., Lewis, K., Lewis, M., Wang, H.: Computationally attractive non-linear models for combinatorial optimization. Int. J. Math. OR. 1, 9-9 (2009)MATH
  2.Bouamama, S., Blum, C., Boukerram, A.: Population-based iterated Greedy algorithm for the minimum weight vertex cover problem. A Appl. Soft Comput. 121, 632-639 (2012)
  3.Cai, S., K. Su, Chen, Q.: EWLS: a new local search for minimum vertex cover. In: Proceedings of the 24\(^{th}\) AAAI Conference on Artificial Intelligence. pp. 45-0 (2010)
  4.Cai, S., Su, K., Sattar, A.: Two new local search strategies for minimum vertex cover. In: Proceedings of the 26th AAAI Conference on Artificial Intelligence. pp. 441-47 (2012)
  5.Cygan, M., Pilipczuk, M.: Split vertex deletion meets vertex cover: new fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113, 179-82 (2013)CrossRef MATH MathSciNet
  6.Gomes, F.C., Meneses, C.N., Pardalos, P.M., Viana, G.V.R.: Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Comput. Oper. Res. 33, 3520-534 (2006)CrossRef MATH
  7.Hassin, R., Levin, A.: The minimum generalized vertex cover problem. ACM Trans. Algorithms 2, 66-8 (2006)CrossRef MathSciNet
  8.Hsia, Y., Wang, Y.: A new penalty parameter for linearly constrained 0- quadratic programming problems. Optim. Lett. 7, 765-78 (2013)CrossRef MATH MathSciNet
  9.Javoanovic, R., Tuba, M.: An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Appl. Soft Comput. 11, 5360-366 (2011)CrossRef
  10.Lewis, M.: On the use of guided design search for discovering significant decision variables in the fixed-charge capacitated multicommodity network design problem. Networks 53(1), 6-8 (2008)CrossRef
  11.Likas, A., Stafylopatis, A.: A parallel algorithm for the minimum weighted vertex cover problem. Inf. Process. Lett. 53(4), 229-34 (1995)CrossRef MATH MathSciNet
  12.Milanovic, M.: Solving the generalized vertex cover problem by genetic algorithm. Comput. Inf. 29, 1251-265 (2010)
  13.Shyu, S., Yin, P.-Y., Lin, B.M.T.: An ant colony optimization algorithm for the minimum weight vertex cover problem. Ann. OR. 131, 283-04 (2004)CrossRef MATH MathSciNet
  14.Voss, S., Fink, A.: A hybridized tabu search approach for the minimum weight vertex cover problem. JOH 18, 869-76 (2012)
  
• 作者单位：Gary Kochenberger (1)
  Mark Lewis (2)
  Fred Glover (3)
  Haibo Wang (4)
  
  1. Business Analytics Department, School of Business Administration, University of Colorado at Denver, Denver, CO, 80217, USA
  2. Craig School of Business, Missouri Western State University, St Joseph, MO, 64507, USA
  3. OptTek Inc, Boulder, CO, 80302, USA
  4. IB&TS Division, Sanchez School of Business, Texas A&M International University, Laredo, TX, 78041, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

The generalized vertex cover problem (GVCP) was recently introduced in the literature and modeled as a binary linear program. GVCP extends classic vertex cover problems to include both node and edge weights in the objective function. Due to reported difficulties in finding good solutions for even modest sized problems via the use of exact methods (CPLEX), heuristic solutions obtained from a customized genetic algorithm (GA) were reported by Milanovic (Comput Inf 29:1251-265, 2010). In this paper we consider an alternative model representation for GVCP that translates the constrained linear (binary) form to an unconstrained quadratic binary program and compare the linear and quadratic models via computations carried out by CPLEX’s branch-and-cut algorithms. For problems comparable to those previously studied in the literature, our results indicate that the quadratic model efficiently yields optimal solutions for many large GVCP problems. Moreover, our quadratic model dramatically outperforms the corresponding linear model in terms of time to reach and verify optimality and in terms of the optimality gap for problems where optimality is unattained. Keywords Vertex cover Performance evaluation Combinatorial problems