University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Ikram Bouras |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Application de l’optimisation bi-niveau aux réseaux sociaux Type de document : texte imprimé Auteurs : Youcef Bouabdallah, Auteur ; Ikram Bouras, Directeur de thèse Editeur : Setif:UFA Année de publication : 2021 Importance : 1 vol (35 f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation bi-niveaux
programmation linéaire en nombre entier
Réseaux sociauxIndex. décimale : 510 - Mathématique Résumé : On s’intéresse dans ce mémoire à l’étude d’une application de l’optimisation bi-niveaux
qui est un cas particulier de la programmation mathématique représenté par un problème
hiérarchique de deux niveaux de décision : première niveau appelé ʺ leaderʺ et second
appelé ʺFollower ʺ.
Nous étudions le problème de la maximisation d’influence dans les réseaux sociaux signés, il a été
formulé comme un problème linéaire bi-niveaux (PBL). Nous reformulons le problème en modèles
PLNE à un seul niveau en utilisant deux différentes conditions d’optimalité (condition d’optimalité de
KKT, le plus court chemin). Des tests numériques sont effectués sur des instances aléatoires pour
comparer les différentes formulations proposées.Côte titre : MAM/0480 En ligne : https://drive.google.com/file/d/1wx9Aow1Tn9nUHgPyk1JxfBWRmx6QZ6Pu/view?usp=shari [...] Format de la ressource électronique : Application de l’optimisation bi-niveau aux réseaux sociaux [texte imprimé] / Youcef Bouabdallah, Auteur ; Ikram Bouras, Directeur de thèse . - [S.l.] : Setif:UFA, 2021 . - 1 vol (35 f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Programmation bi-niveaux
programmation linéaire en nombre entier
Réseaux sociauxIndex. décimale : 510 - Mathématique Résumé : On s’intéresse dans ce mémoire à l’étude d’une application de l’optimisation bi-niveaux
qui est un cas particulier de la programmation mathématique représenté par un problème
hiérarchique de deux niveaux de décision : première niveau appelé ʺ leaderʺ et second
appelé ʺFollower ʺ.
Nous étudions le problème de la maximisation d’influence dans les réseaux sociaux signés, il a été
formulé comme un problème linéaire bi-niveaux (PBL). Nous reformulons le problème en modèles
PLNE à un seul niveau en utilisant deux différentes conditions d’optimalité (condition d’optimalité de
KKT, le plus court chemin). Des tests numériques sont effectués sur des instances aléatoires pour
comparer les différentes formulations proposées.Côte titre : MAM/0480 En ligne : https://drive.google.com/file/d/1wx9Aow1Tn9nUHgPyk1JxfBWRmx6QZ6Pu/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0480 MAM/0480 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Fonctions approximantes en programmation linéaire Type de document : texte imprimé Auteurs : Ikram Bouras Catégories : Thèses & Mémoires:Mathématique Mots-clés : Optimisation et contrôle Côte titre : MAM/0127 En ligne : https://drive.google.com/file/d/19aF9HlJNigyqOkEWvMUNPDh-KzXHobxn/view?usp=shari [...] Format de la ressource électronique : Fonctions approximantes en programmation linéaire [texte imprimé] / Ikram Bouras . - [s.d.].
Catégories : Thèses & Mémoires:Mathématique Mots-clés : Optimisation et contrôle Côte titre : MAM/0127 En ligne : https://drive.google.com/file/d/19aF9HlJNigyqOkEWvMUNPDh-KzXHobxn/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAM/0127 MAM/0127 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Solution techniques for the Bi-level Knapsack Problem Type de document : texte imprimé Auteurs : Lilia houda Bessou, Auteur ; Khaoula imene Guitane ; Ikram Bouras, Directeur de thèse Editeur : Setif:UFA Année de publication : 2024 Importance : 1 vol (68 f .) Format : 29 cm Langues : Anglais (eng) Catégories : Thèses & Mémoires:Informatique Mots-clés : Knapsack problem
Bi-level programming
Dynamic programming
Integer programmingIndex. décimale : 004 - Informatique Résumé :
The bilevel knapsack problem (BKP) is a complex combinatorial optimization
problem characterized by a hierarchical two-level decisionmaking
structure, where decisions made at the upper level (leader)
directly influence the lower level (follower). Traditional knapsack
problem-solving methods are inadequate for addressing the intricacies
of the BKP due to this interaction. This thesis study an exact
algorithm, DPBKP, designed to solve the BKP effectively based on a
reformulation of the problem into an integer programming problem.
This thesis provides numerical experiments on randomly generated
instances.Note de contenu : Sommaire
Introduction 1
1 Preliminary Notions 3
1.1 Integer Linear Programming (ILP) . . . . . . . . . . . . . . . . . 3
1.1.1 Definition of the ILP problem . . . . . . . . . . . . . . . . 4
1.1.2 The advantages of Integer Linear Programming (ILP) . . . 5
1.1.3 Exact algorithms to solve ILP . . . . . . . . . . . . . . . . 5
1.2 Two-level (bi-level) optimization . . . . . . . . . . . . . . . . . . . 8
1.2.1 Bi-Level Linear Programming (BLP) . . . . . . . . . . . . 9
1.2.2 Non-uniqueness of the optimal solution of the “Follower” . 12
1.2.3 Algorithms to solve BLP . . . . . . . . . . . . . . . . . . . 13
2 The general Knapsack problem 16
2.1 Historical Overview of the Knapsack Problem . . . . . . . . . . . 16
2.2 The general Knapsack problem . . . . . . . . . . . . . . . . . . . 18
2.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Types of the Knapsack Problem . . . . . . . . . . . . . . . . . . . 22
2.4.1 Bounded Knapsack Problem . . . . . . . . . . . . . . . . . 24
2.4.2 Unbounded Knapsack Problem . . . . . . . . . . . . . . . 25
2.4.3 Multiple-choice Knapsack Problem . . . . . . . . . . . . . 26
2.5 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.1 Brute Force Approach . . . . . . . . . . . . . . . . . . . . 27
2.5.2 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . 27
2.5.3 Approximation Algorithms . . . . . . . . . . . . . . . . . . 28
2.5.4 Exact methods . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Bi-Level Knapsack Problem 31
3.1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 mathematical formulation . . . . . . . . . . . . . . . . . . . . . . 32
3.3 One-level reformulation of the bilevel knapsack problem . . . . . . 35
3.4 Application Example . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Numerical results 47
4.1 Software tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.1 Julia programming language . . . . . . . . . . . . . . . . 48
4.1.2 JuMP modeling language . . . . . . . . . . . . . . . . . . 49
4.1.3 HiGHS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.4 Packages and Stalls . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1 Data generator . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.2 Problem solving . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.3 Results discussion . . . . . . . . . . . . . . . . . . . . . . 57Côte titre : MAI/0859 Solution techniques for the Bi-level Knapsack Problem [texte imprimé] / Lilia houda Bessou, Auteur ; Khaoula imene Guitane ; Ikram Bouras, Directeur de thèse . - [S.l.] : Setif:UFA, 2024 . - 1 vol (68 f .) ; 29 cm.
Langues : Anglais (eng)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Knapsack problem
Bi-level programming
Dynamic programming
Integer programmingIndex. décimale : 004 - Informatique Résumé :
The bilevel knapsack problem (BKP) is a complex combinatorial optimization
problem characterized by a hierarchical two-level decisionmaking
structure, where decisions made at the upper level (leader)
directly influence the lower level (follower). Traditional knapsack
problem-solving methods are inadequate for addressing the intricacies
of the BKP due to this interaction. This thesis study an exact
algorithm, DPBKP, designed to solve the BKP effectively based on a
reformulation of the problem into an integer programming problem.
This thesis provides numerical experiments on randomly generated
instances.Note de contenu : Sommaire
Introduction 1
1 Preliminary Notions 3
1.1 Integer Linear Programming (ILP) . . . . . . . . . . . . . . . . . 3
1.1.1 Definition of the ILP problem . . . . . . . . . . . . . . . . 4
1.1.2 The advantages of Integer Linear Programming (ILP) . . . 5
1.1.3 Exact algorithms to solve ILP . . . . . . . . . . . . . . . . 5
1.2 Two-level (bi-level) optimization . . . . . . . . . . . . . . . . . . . 8
1.2.1 Bi-Level Linear Programming (BLP) . . . . . . . . . . . . 9
1.2.2 Non-uniqueness of the optimal solution of the “Follower” . 12
1.2.3 Algorithms to solve BLP . . . . . . . . . . . . . . . . . . . 13
2 The general Knapsack problem 16
2.1 Historical Overview of the Knapsack Problem . . . . . . . . . . . 16
2.2 The general Knapsack problem . . . . . . . . . . . . . . . . . . . 18
2.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Types of the Knapsack Problem . . . . . . . . . . . . . . . . . . . 22
2.4.1 Bounded Knapsack Problem . . . . . . . . . . . . . . . . . 24
2.4.2 Unbounded Knapsack Problem . . . . . . . . . . . . . . . 25
2.4.3 Multiple-choice Knapsack Problem . . . . . . . . . . . . . 26
2.5 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5.1 Brute Force Approach . . . . . . . . . . . . . . . . . . . . 27
2.5.2 Greedy Algorithms . . . . . . . . . . . . . . . . . . . . . . 27
2.5.3 Approximation Algorithms . . . . . . . . . . . . . . . . . . 28
2.5.4 Exact methods . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Bi-Level Knapsack Problem 31
3.1 introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 mathematical formulation . . . . . . . . . . . . . . . . . . . . . . 32
3.3 One-level reformulation of the bilevel knapsack problem . . . . . . 35
3.4 Application Example . . . . . . . . . . . . . . . . . . . . . . . . . 43
4 Numerical results 47
4.1 Software tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.1.1 Julia programming language . . . . . . . . . . . . . . . . 48
4.1.2 JuMP modeling language . . . . . . . . . . . . . . . . . . 49
4.1.3 HiGHS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.4 Packages and Stalls . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.1 Data generator . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.2 Problem solving . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2.3 Results discussion . . . . . . . . . . . . . . . . . . . . . . 57Côte titre : MAI/0859 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0859 MAI/0859 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
