Titulo Estágio
Heuristics for the clique partitioning problem
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
ECOS/DEI
Enquadramento
Given an undirected graph G=(V,E), the clique partitioning problem (CPP) is to find a partition of the set of nodes V such that each component is a clique. Considering weights w_ij on each edge (i,j) in E, the most common goal associated to this problem is to find a solution with the maximum sum of the weights of the edges in the cliques.
When G is complete and w_ij >= 0 for all (i,j) in E, then the problem is trivial. However, when G is sparse or if the set of edges includes positive and negative weights, then the problem is NP-hard [1].
The CPP is one of the clustering agglomerative techniques. It has many applications, namely in stock markets [3] and in biological networks [9,10,11,12].
There is a well-known integer programming formulation that solves the CPP [2]. However, for large instances one needs to resort to heuristic techniques to obtain approximate solutions [4,5,6,7,10,11,13].
Objetivo
The student should explore heuristic methods for the clique partitioning problem and conduct a number of computational tests in order to compare the performance of the algorithms with exact and approximate methods in the literature.
Plano de Trabalhos - Semestre 1
- Literature review: Notions of graphs and combinatorial optimization, heuristics for the clique partitioning problem.
- Notions of neighborhood for the clique partitioning problem
- Design of basic local search for the clique partitioning problem
- Writing of the intermediate report
Plano de Trabalhos - Semestre 2
- Notions of perturbations for the clique partitioning problem
- Design of iterated local search for the clique partitioning problem
- Computational experiments
- Writing of the thesis
Condições
The MSc student can use the computational resources from ECOS group for performing experiments. This project has no funding available.
Observações
Referências:
[1] Garey, M.R., Johnson, D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company, New York.
[2] Pardalos, P.M., Mavridou, T., Xue, J., 1998. The graph coloring problem: a bibliographic survey. In:Du, D.-Z., Pardalos, P.M. (Eds.). Handbook of combinatorial optimization, vol. 2. Dordrecht: Kluwer Academic Publishers. pp. 331–395.
[3] Boginski, V., Butenko, S., Pardalos, P.M., 2006. Mining market data: a network approach. Computers & Operations Research 33(11), 3171-3184.
[4] Brimberg, J., Janićijević, S., Mladenović, N., Urošević, D., 2015. Solving the clique partitioning problem as a maximally diverse grouping problem. Optimization Letters , 1-13, DOI: 10.1007/s11590-015-0869-4.
[5] Brusco, M.J., Köhn, H.F., 2009. Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem. Psychometrika 74(4), 685-703.
[6] Charon, I., Hudry, O., 2006. Noising methods for a clique partitioning problem. Discrete Applied Mathematics 154(5), 754-769.
[7] Dorndorf, U., Pesch, E., 1994. Fast clustering algorithms. ORSA Journal on Computing 6(2), 141-153.
[8] Hansen, P., Jaumard, B., 1997. Cluster analysis and mathematical programming. Mathematical programming 79(1-3), 191-215.
[9] Hüffner, F., Komusiewicz, C., Liebtrau, A., Niedermeier, R., 2014. Partitioning biological networks into highly connected clusters with maximum edge coverage. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) 11(3), 455-467.
[10] Kochenberger, G., Glover, F., Alidaee, B., Wang, H., 2005. Clustering of microarray data via clique partitioning. Journal of Combinatorial Optimization 10(1), 77-92.
[11] Nascimento, M.C., Toledo, F.M., de Carvalho, A.C., 2010. Investigation of a new GRASP-based clustering algorithm applied to biological data. Computers & Operations Research 37(8), 1381-1388.
[12] Pirim, H., Ekşioğlu, B., Perkins, A. D., Yüceer, Ç., 2012. Clustering of high throughput gene expression data. Computers & operations research 39(12), 3046-3061.
[13] Punnen, A.P., Zhang, R., 2012. Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem. Discrete Optimization 9(3), 205-208.
Orientador
Luís Paquete e Pedro Martins ( ISCAC )
paquete@dei.uc.pt 📩