Home

euro2021 irimas

EURO 2021 - 31st European Conference on Operational Research
11-14 July 2021, Athens, Greece

"Discrete Optimization Algorithms" Area
"Evolutionary and Swarm Optimization" Stream

Special session on the "Set Covering Problem and its applications"

Aims and scope

The set covering problem (SCP) is one of Karp's well-known NP-hard problems [6]. This classical combinatorial optimization problem is related to a wide range of real-world applications, including crew scheduling, facility location, city logistic problems, and optimal camera placement [1,2,4,5,7].

The SCP can be stated as follows: given a set of elements I to be covered, and a collection of sets J such that the union of all sets in J is I, find the smallest subset C of J such that C covers I. This formulation is referred to as the unicost set covering problem (USCP). If costs are assigned to the sets of J, then it becomes the weighted set covering problem (WSCP).

Previous studies have presented a series of techniques to solve SCP problems such as exact methods, mathematical programming, bi-level programming, heuristic, and metaheuristic methods. Among them, the continuous development of metaheuristics has derived a number of impressive algorithms that can solve huge SCP instances in a reasonable time. Very recently, their hybridizations with other techniques are shown to give even better results on both benchmark and real-world applications [3,8].

This special session is devoted to new approaches that use evolutionary or swarm optimization methods to tackle the USCP, the WSCP, or any SCP variant inspired from a real-world application.

References:
[1] Balas, E.: A class of location, distribution and scheduling problems: modeling and solution methods. In: Proceedings of the Chinese-U.S. Symposium on Systems Analysis. Wiley Series on Systems Engineering and Analysis. Wiley (1983). ISBN 978-0-471-87093-7
[2] Boschetti, M., Maniezzo, V.: A set covering based matheuristic for a real-world city logistics problem. Int. Trans. Oper. Res. 22(1), 169–195 (2015). https://doi.org/10.1111/itor.12110
[3] M. Brévilliers, J. Lepagnot, L. Idoumghar, M. Rebai, and J. Kritter. Hybrid differential evolution algorithms for the optimal camera placement problem. Journal of Systems and Information Technology, 20(4):446 – 467, 2018. https://doi.org/10.1108/JSIT-09-2017-0081
[4] Christofides, N., Korman, S.: A computational survey of methods for the set covering problem. Manag. Sci. 21(5), 591–599 (1975). https://doi.org/10.1287/mnsc.21.5.591
[5] Farahani, R.Z., Asgari, N., Heidari, N., Hosseininia, M., Goh, M.: Covering problems in facility location: a review. Comput. Ind. Eng. 62(1), 368–407 (2012). https://doi.org/10.1016/j.cie.2011.08.020
[6] R. M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972. https://doi.org/10.1007/978-1-4684-2001-2_9
[7] Kritter, J., Brévilliers, M., Lepagnot, J., Idoumghar, L.: On the optimal placement of cameras for surveillance and the underlying set cover problem. Appl. Soft Comput. 74, 133–153 (2019). https://doi.org/10.1016/j.asoc.2018.10.025
[8] Pinard M., Moalic L., Brévilliers M., Lepagnot J. and Idoumghar L., A Memetic Approach for the Unicost Set Covering Problem, Learning and Intelligent Optimization (LION 2020), Athens, Greece, LNCS, Vol.12096, pp.233-248, Springer, 2020. https://doi.org/10.1007/978-3-030-53552-0_23

Topics of interests

The methods and tools applied to solve the SCP include, but are not limited to, the following:

  • Genetic algorithms
  • Ant colony optimization
  • Artificial bee colony algorithm
  • Particle swarm optimization
  • Differential evolution
  • Memetic algorithms
  • Hybridization of evolutionary and/or swarm optimization techniques
  • Hybridization with exact and/or heuristic methods

The potential applications include, but are not limited to, the following:

  • Crew scheduling
  • Facility location
  • City logistic problems
  • Optimal camera placement
  • Nature reserve design
  • Software test suite reduction
  • Wavelength assignment problem in optical networks

Submission process

EURO 2021 important dates: https://euro2021athens.com/key-dates-deadlines/
The abstract submission deadline has been extended until March 28, 2021.

Abstract submission guidelines: https://euro2021athens.com/abstract-submission/

Abstract submission system: https://www.euro-online.org/conf/euro31/
To submit an abstract in this special session, you will have to provide the following submission code: c64b68ad.

Organizing committee

Mathieu Brévilliers, Mokhtar Essaid, Lhassane Idoumghar, Julien Lepagnot, Laurent Moalic, and Hojjat Rakhshani.

For any question or comment, please send an email to mathieu.brevilliers@uha.fr.

News and updates

  • March 15, 2021 : The section "Submission process" has been updated.
  • January 8, 2021 : The session website is online.