Abstract
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–1265, 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alidaee, B., Kochenberger, G., Lewis, K., Lewis, M., Wang, H.: Computationally attractive non-linear models for combinatorial optimization. Int. J. Math. OR. 1, 9–19 (2009)
Bouamama, S., Blum, C., Boukerram, A.: Population-based iterated Greedy algorithm for the minimum weight vertex cover problem. A Appl. Soft Comput. 121, 632–1639 (2012)
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–50 (2010)
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–447 (2012)
Cygan, M., Pilipczuk, M.: Split vertex deletion meets vertex cover: new fixed-parameter and exact exponential-time algorithms. Inf. Process. Lett. 113, 179–182 (2013)
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–3534 (2006)
Hassin, R., Levin, A.: The minimum generalized vertex cover problem. ACM Trans. Algorithms 2, 66–78 (2006)
Hsia, Y., Wang, Y.: A new penalty parameter for linearly constrained 0–1 quadratic programming problems. Optim. Lett. 7, 765–778 (2013)
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–5366 (2011)
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–18 (2008)
Likas, A., Stafylopatis, A.: A parallel algorithm for the minimum weighted vertex cover problem. Inf. Process. Lett. 53(4), 229–234 (1995)
Milanovic, M.: Solving the generalized vertex cover problem by genetic algorithm. Comput. Inf. 29, 1251–1265 (2010)
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–304 (2004)
Voss, S., Fink, A.: A hybridized tabu search approach for the minimum weight vertex cover problem. JOH 18, 869–876 (2012)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kochenberger, G., Lewis, M., Glover, F. et al. Exact solutions to generalized vertex covering problems: a comparison of two models. Optim Lett 9, 1331–1339 (2015). https://doi.org/10.1007/s11590-015-0851-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-015-0851-1