Modélisation et Résolution Exacte et Approchée des Problèmes d’Optimisation Combinatoire (MREA-POC)

Titre de l’équipe : Modélisation et Résolution Exacte et Approchée des Problèmes d’Optimisation Combinatoire (MREA-POC)

Chef de l’équipe : DAHMANI Isma

Grade : Maître de conférences

Liste  des membres de l’équipe

Nom  & Prénom Grade DernierGrade Spécialité   Structure de rattachement
DAHMANI Isma    MCA HU  USTHB
BENKANOUN Yazid   MCB   DUSTHB
FERROUM Meriem  DoctorantDUSTHB  
BOUKHARI Samah  DoctorantMS USTHB
MOKRANI Amira NaghamDoctorant MS   USTHB
LACHEMI HADJOUT NadiaDoctorantMSUSTHB

Objectifs de l’équipe

L’équipe s’intéresse à l’étude d’une classe qui porte un intérêt important sur le plan théorique ainsi que sur le plan pratique à titre d’exemple les problèmes d’optimisation combinatoire, en particulier les problèmes qui sont  formulés comme des programmes linéaires en nombres entiers.  La famille de problèmes de sac-à-dos ou “knapsack”  (KP)  est représentée  par  un programme linéaire en nombres entiers ne comprenant qu’une seule contrainte fonctionnelle. Ce problèmes possède plusieurs applications pertinentes liées à la prise de décision et aux systèmes intelligents comme : le partitionnement de base de données, la fabrication flexible, la prise de décision financière, le prototypage de clé publique etc.  

La  contribution  de l’équipe se focalise  sur quelques variantes de problèmes de type sac à dos, où nous envisageons de développer des méthodes exactes, approchées et hybrides pour leurs résolutions. 

Un des vecteurs porteurs de nos recherches portera sur les problèmes ”multiobjevtive shrtest path” avec des ” Assignements optimales” en utilisant des agrégations de types flous” L’intégrale de Choquet ”. Les capacités non additives  peuvent intervenir dans la détermination des solutions de tous les problèmes cités ci-dessus.

Mots clés

Optimisation Combinatoire, Programmation en nombres entiers, méthodes exactes, méthodes approchées, knapsack, multi-objectif, Capacités non additives ,Plus courts chemins  multi objectif, Optimisation multi objectif, Logique flou.

Publications internationales

  1. S. Boukhari , I. Dahmani and M Hifi. Effect of the local branching strategy on the descent method : The case of the generalized multiple knapsack with setup. : Computers and Industrial Engineering, vol 165, pp. 107934, 2022. 
  2. Isma Dahmani, Meriem Ferroum  et Mhand Hifi : Effect of Backtracking Strategy in Population-Based Approach : The Case of the Set-Union Knapsack Problem : Cybernetics and Systems, vol. 53, no 1, p. 168-185, 2022.
  3. S. Boukhari , I. Dahmani and M Hifi. Computational power of a hybrid algorithm for solving the multiple knapsack problem with setup : In Intelligent Computing, Springer, Cham, pp. 154-168, 2022.
  4. I. Dahmani, M. Ferroum, and M. Hifi. An iterative rounding strategy-based algorithm for the set-union knapsack problem : Soft Computing  vol. 25, no 21,  (2021), p. 13617-13639.
  5. S. Boukhari , I. Dahmani and M Hifi. Effect of valid cardinality constraints in local branching : the case of the knapsack problem with setup : Information Technology in Industry (ITII), vol. 8, no.3, 2020 .
  6. Yazid, B., Sadek, B., & Djamal, C. (2020). Evolutionary metaheuristics to solve multiobjective assignment problem in telecommunication network: Multiobjective assignment problem. International Journal of Applied Metaheuristic Computing (IJAMC), 11(2), 56-76.
  7. I. Dahmani and Mhand Hifi, T Saadi and L Yousef. A Swarm Optimization-Based Search Algorithm for the Quadratic Knapsack Problem with Conict Graphs : Expert Systems with Applications, vol. 148, p. 113224, 2020.
  8. I. Dahmani and Mhand Hifi. A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs : Annals of Operations Research, p. 1–23, 2019.
  9. I. Dahmani, Mhand Hifi and Lei WuAn exact decomposition algorithm for the generalized knapsack sharing problem. European Journal of Operational Research, vol. 252(3), pp. 761-774, 2016.
  10. I. Dahmani and R Ouafi. Improved algorithm for orthogonal rectangular packing problem. International Journal of Information Sciences and Computer Engineering, vol. 1(2), pp. 21-25, 2010.
  11. S. Boukhari , I. Dahmani and M Hifi. : Local branching strategy-based method for the knapsack problem with setup : Proceedings of the 4th International Conference on Artificial Intelligence, Soft Computing And Applications, CS and IT-CSCP, Springer, Cham, pp. 65-75, 2020.

Conférences et  Séminaire

  1. I. Dahmani, M. Ferroum , M. Hifi,, An Iterative Algorithm for Solving the Multiple Knapsack Assignment Problem , 23ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF2022), à Lyon de, 23-25 février 2022.
  2. S. Boukhari, I. Dahmani, M. Hifi, A Hybrid Algorithm for Solving the Multiple Knapsack Problem with Setup. , 23ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF2022), à Lyon de, 23-25 février 2022.
  3. I. Dahmani, M. Ferroum , M. Hifi, An iterative approach for set-union knapsack problem , 22ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF2021), Laboratoire IRIMAS de l’Université de Haute-Alsace, de, 26-30 avril 2021.
  4. S. Boukhari , I. Dahmani, M. Hifi, A Local Branching for the Knapsack Problem with Setup , 22ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF2021), Laboratoire IRIMAS de l’Université de Haute-Alsace, de, 26-30 avril 2021.
  5. S. Boukhari, I. Dahmani, M. Hifi, Computational Power of a Hybrid Algorithm for Solving the Multiple Knapsack Problem with Setup , Computing Conference 2021, 15 et 16 juillet 2021.
  6. Isma Dahmani, Meriem Ferroum, Mhand Hifi, The Local Branching as a Learning Strategy in the Evolutionary Algorithm : The Case of the Set-Union Knapsack Problem, 2021 8th Intl. Conference on Soft Computing & Machine Intelligence (ISCMI2021 ) in Cairo, Egypt during November 26-27, 2021 .
  7. Méziane Aider, Amina N. Benahmed, Isma Dahmani, Mhand Hifi, A Hybrid Evolutionary Algorithm for the Sequencing m-Vector Bin Packing problem , 2021 8th Intl. Conference on Soft Computing & Machine Intelligence (ISCMI2021 ) in Cairo, Egypt during November 26-27, 2021.
  8. S. Boukhari, I. Dahmani, M. Hifi, Méthode hybride pour la résolution du problème de sac à dos Multiple avec setup. Journées Doctorales de Recherche Opérationnelle et Management JDROM?2021, 16 décembre 2021, USTHB.
  9. M. Hifi, I. Dahmani, M. Ferroum and S. Sadeghsa, Using a perturbation strategy for a variant of the knapsack problem , 21ème congrès annuel de la société Française de Recherche Opérationnelle et d’Aide à la Décision (ROADEF2020), Université de Montpellier, 19-21 janvier 2020.
  10. Dahmani, I., Ferroum, M., Hifi, M., & Sadeghsa, S. (2020, June). A Hybrid Swarm Optimization-Based Algorithm for the Set-Union Knapsack Problem. In 2020 7th International Conference on Control, Decision and Information Technologies (CoDIT) (Vol. 1, pp. 1162-1167). IEEE.
  11. S. Boukhari, I. Dahmani, M. Hifi, Computational Power of a Hybrid Algorithm for Solving the Multiple Knapsack Problem with Setup, AISCA 2020  4th International Conference on Artificial Intelligence, Soft Computing And Applications, 28 et 29 Novembre 2020.
  12. S. Boukhari, I. Dahmani, M. Hifi, Tackling a particular knapsack problem with local branching. Journées Doctorales de Recherche Opérationnelle et Management JDROM’2020, 23-24 décembre 2020, USTHB.
  13. M. Ferroum, I. Dahmani, M. Hifi, Reactive Strategy-Based Method for the Multiple Knapsack Assignment. Journées Doctorales de Recherche Opérationnelle et Management JDROM’2020, 23-24 décembre 2020, USTHB.
  14. M. Ferroum, I. Dahmani, M. Hifi, Fix and Solve Strategies-Based Algorithm for the Set Union Knapsack. Journées Doctorales de Recherche Opérationnelle et Management JDROM’2019, 18-19 décembre 2019, USTHB.
  15. Y.Benkanoun , D.Chaabane      Présentation au séminaire hebdomadaire du département de Recherche Opérationnelle mai 2018.  Thème : la contribution directe de la logique floue dans un problème de prise de décision.
  16.  Y.BENKANOUN    Présentation au séminaire hebdomadaire du département de Recherche Opérationnelle, Février 2017. Thème : Optimisation multi objectif par l’intégrale de Choquet sur un ensemble des plus courts chemins.
  17.  Y.BENKANOUN    Décembre 2017 Participation aux journées doctorales de recherche opérationnelle et management (JDROM’ 2017). Thème : pertinence d’une agrégation multidimensionnelle .l’intégrale de Choquet un bon candidat.
  18. I. Dahmani. Problème de la distribution équitable avec des objets communs. Séminaire hebdomadaire de Recherche Opérationnelle : 28 avril 2015, USTHB.
  19. Y.Benkanoun et D.Chaabane     Participation aux journées nationales sur la Recherche opérationnelle au sein de l’entreprise (JNRO’2015) BORDJ BOUARRERIDJ. Thème : Optimisation by Choquet’s Integral on the Set of Pareto Optimal Short Paths.
  20. I. Dahmani. Problème de la distribution équitable. Séminaire hebdomadaire de Recherche Opérationnelle : 04 mars 2014, USTHB.
  21. Y.BENKANOUN    Participation aux journées doctorales du laboratoire JDL 2014 de l’Université des Sciences et de la Technologie Houari Boumediene, Bab Ezzouar. Thème : Optimisation par l’intégrale de Choquet sur un ensemble des plus courts
  22.  Y.BENKANOUN      Participation aux journées doctorales du laboratoire JDL 2014 de l’Université des Sciences et de la Technologie Houari Boumediene, Bab Ezzouar. Thème : Méthodes exacte pour l’optimisation multi objectif dans les graphes,  recherche de solution de compromis. (Utilisation de l’intégrale de Choquet sur un ensemble de solutions efficaces).
  23.  Y.Benkanoun et D.Chaabane     Communication Orale pour les journées doctorales JDL ‘2014. Thème : Méthode exactes pour l’optimisation multi objectif dans les graphes.
  24.  Y.Benkanoun et D.Chaabane      Y.BENKANOUN    Participation aux journées doctorales du laboratoire JDL 2013 de l’Université des Sciences et de la Technologie Houari Boumediene, Bab Ezzouar. Thème : Optimisation par l’intégrale de Choquet sur un ensemble des plus courts chemins Pareto Optimal.
  25. I. Dahmani, M. Hifi and R. Ouafi. A Scatter Search-Based Algorithm for the Knapsack Sharing Problem. In Proceedings of 5th Saudi Science Conference Umm Al Qura University Makkah ; Saudi Arabia, 2012.
  26. I. Dahmani, M. Hifi and R. Ouafi. Scatter Search-Based Algorithm for the Knapsack Sharing Problem. In Proceedings of ISOR’2011, Alger, Algérie, 2011.
  27. I. Dahmani et R. Ouafi. Un algorithme amélioré pour la résolution du problème d’assemblage orthogonal rectangulaire. Communication à la 5ème Conférence internationale en Recherche Opérationnelle (CIRO’10) Marrakech, 2010.
  28. I. Dahmani et R. Ouafi. Problème d’Assemblage Orthogonal Rectangulaire : Approche Algorithmique. Au 7ème Colloque sur l’Optimisation et les Système d’Information (COSI’ 2010) – Ouargla, 2010.
  29. Y.BENKANOUN     Participation aux journées ”Technologie de communication dans la pratique à la pédagogie. (Ecole Nationale de Poste et Télécommunication). (UFC) (Juillet 2006 )