University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Khaoula imene Guitane |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
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
