A FAST METHOD FOR OPTIMIZING THE K-CLUSTERING BI-CLIQUE COMPLETION PROBLEM IN TELECOMMUNICATION

  • SAGVAN ALI SALEH College of Engineering, University of Duhok, Kurdistan Region-Iraq
  • MHAND HIFI Universit´e de Picardie Jules Verne,
Keywords: Bi-clique, heuristic, neighborhood, optimization

Abstract

 In this work, we present a fast approximate method for solving the k-Clustering Minimum Bi-clique Completion Problem (KBCP), a problem belonging to the telecommunication and transportation do- mains. In KBCP, we are given a set of demands of services from customers and its goal is to determine a subset of k multicast sessions that is able to partition the set of the starting demands. Each of the considered service has to belong to a multicast session while each costumer can appear in more sessions. The KBCP is tackled by using a fast approximate method which is based on the principle of neighborhood search techniques. The method can search several solutions belonging to diversified sub-spaces aiming to find the best solution. The performance of the presented method is evaluated on benchmark instances taken from the literature, whereby the provided results are compared to those reached by the Cplex solver and recent methods described in the literature. The results show that, the proposed method is fast and competitive and it is able to reach new bounds.

Downloads

Download data is not yet available.

References

1. Al-Iedani, N., Hifi, M., Saadi, T.: Neighborhood search-based heuristic for the k- clustering minimum biclique completion problem. In Control, Decision and Informa- tion Technologies (CoDIT), International Conference on IEEE, pp. 639–643, (2016).
2. Dasgupta, S., Christos H. P., Umesh V.: Algorithms. McGraw-Hill, Inc., (2016).
3. Faure, N., Chr´etienne, P., Gourdin, E., Sourd, F.: Biclique Completion Problems for Multicast Network Design. Discrete Optimization, 4, pp. 360–377 (2007).
4. Gualandi, S.: k-Clustering Minimum Biclique Completion via a Hybrid CP and SDP Approach. In: van Hoeve, W-J., Hooker, J.N. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. LNCS, vol. 5547, pp. 87–101. Springer Berlin Heidelberg (2009)
5. Gualandi, S., Maffioli, F., Magni, C.: A Branch-and-Price Approach to k-Clustering Minimum Biclique Completion Problem. International Transactions in Operational Research, 20, pp. 101–117 (2013)
6. Hifi, M., Moussa, I., Saadi, T., Saleh, S.: An Adaptive Neighborhood Search for k-Clustering Minimum Bi-clique Completion Problems. In Modelling, Computation and Optimization in Information Systems and Management Sciences, Springer Inter- national Publishing, pp. 15–25, (2015).
7. Hifi, M., Michrafy, M.: A Reactive Local Search-Based Algorithm for the Disjunc- tively Knapsack Problem. Journal of the Operational Research Society, 57, pp. 718– 726 (2006)
8. Johnson, D.S.: Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Sciences, 9, pp. 256-278 (1974)
9. Shaw, P.: Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. In: M. Maher, M., Puget, J.F. (eds.) Principles and Practice of Constraint Programming – CP98. LNCS, vol. 1520, pp. 417–431. Springer Berlin Heidelberg (1998)
Published
2017-07-27
How to Cite
SALEH, S. A., & HIFI, M. (2017). A FAST METHOD FOR OPTIMIZING THE K-CLUSTERING BI-CLIQUE COMPLETION PROBLEM IN TELECOMMUNICATION. Journal of Duhok University, 20(1), 175-183. https://doi.org/10.26682/sjuod.2017.20.1.16