Constrained optimization is a challenging branch of operations research that aims to create a model which has a wide range of applications in the supply chain, telecommunications and medical fields. As the problem structure is split into two main components, the objective is to accomplish the feasible set framed by the system constraints. The aim of this book is expose optimization problems that can be expressed as graphs, by detailing, for each studied problem, the set of nodes and the set of edges. This graph modeling is an incentive for designing a platform that integrates all optimization components in order to output the best solution regarding the parameters' tuning. The authors propose in their analysis, for optimization problems, to provide their graphical modeling and mathematical formulation and expose some of their variants. As a solution approaches, an optimizer can be the most promising direction for limited-size instances. For large problem instances, approximate algorithms are the most appropriate way for generating high quality solutions. The authors thus propose, for each studied problem, a greedy algorithm as a problem-specific heuristic and a genetic algorithm as a metaheuristic.
List of Tables xi
List of Figures xiii
List of Algorithms xvii
Introduction xix
Chapter 1 Basic Concepts in Optimization 1 (12)
and Graph Theory
1.1 Introduction 1 (1)
1.2 Notation 2 (1)
1.3 Problem structure and variants 2 (2)
1.4 Features of an optimization problem 4 (1)
1.5 A didactic example 5 (1)
1.6 Basic concepts in graph theory 6 (6)
1.6.1 Degree of a graph 7 (1)
1.6.2 Matrix representation of a graph 7 (1)
1.6.3 Connected graphs 8 (1)
1.6.4 Itineraries in a graph 8 (1)
1.6.5 Tree graphs 9 (2)
1.6.6 The bipartite graphs 11 (1)
1.7 Conclusion 12 (1)
Chapter 2 Knapsack Problems 13 (18)
2.1 Introduction 13 (1)
2.2 Graph modeling of the knapsack problem 14 (1)
2.3 Notation 14 (1)
2.4 0-1 knapsack problem 15 (1)
2.5 An example 16 (1)
2.6 Multiple knapsack problem 17 (2)
2.6.1 Mathematical model 17 (1)
2.6.2 An example 18 (1)
2.7 Multidimensional knapsack problem 19 (2)
2.7.1 Mathematical model 19 (1)
2.7.2 An example 20 (1)
2.8 Quadratic knapsack problem 21 (2)
2.8.1 Mathematical model 22 (1)
2.8.2 An example 22 (1)
2.9 Quadratic multidimensional knapsack 23 (2)
problem
2.9.1 Mathematical model 24 (1)
2.9.2 An example 24 (1)
2.10 Solution approaches for knapsack 25 (3)
problems
2.10.1 The greedy algorithm 25 (1)
2.10.2 A genetic algorithm for the KP 26 (2)
2.11 Conclusion 28 (3)
Chapter 3 Packing Problems 31 (20)
3.1 Introduction 31 (1)
3.2 Graph modeling of the bin packing 32 (1)
problem
3.3 Notation 33 (1)
3.4 Basic bin packing problem 33 (3)
3.4.1 Mathematical modeling of the BPP 34 (1)
3.4.2 An example 35 (1)
3.5 Variable cost and size BPP 36 (1)
3.5.1 Mathematical model 36 (1)
3.5.2 An example 37 (1)
3.6 Vector BPP 37 (3)
3.6.1 Mathematical model 38 (1)
3.6.2 An example 39 (1)
3.7 BPP with conflicts 40 (2)
3.7.1 Mathematical model 40 (1)
3.7.2 An example 41 (1)
3.8 Solution approaches for the BPP 42 (6)
3.8.1 The next-fit strategy 42 (1)
3.8.2 The first-fit strategy 43 (1)
3.8.3 The best-fit strategy 44 (1)
3.8.4 The minimum bin slack 44 (2)
3.8.5 The minimum bin slack' 46 (1)
3.8.6 The least loaded heuristic 46 (1)
3.8.7 A genetic algorithm for the bin 47 (1)
packing problem
3.9 Conclusion 48 (3)
Chapter 4 Assignment Problem 51 (18)
4.1 Introduction 51 (1)
4.2 Graph modeling of the assignment 52 (1)
problem
4.3 Notation 52 (1)
4.4 Mathematical formulation of the basic 53 (2)
AP
4.4.1 An example 54 (1)
4.5 Generalized assignment problem 55 (2)
4.5.1 An example 56 (1)
4.6 The generalized multiassignment 57 (2)
problem
4.6.1 An example 58 (1)
4.7 Weighted assignment problem 59 (1)
4.8 Generalized quadratic assignment 60 (1)
problem
4.9 The bottleneck GAP 61 (1)
4.10 The multilevel GAP 61 (1)
4.11 The elastic GAP 62 (1)
4.12 The multiresource GAP 63 (1)
4.13 Solution approaches for solving the 64 (3)
AP
4.13.1 A greedy algorithm for the AP 64 (1)
4.13.2 A genetic algorithm for the AP 65 (2)
4.14 Conclusion 67 (2)
Chapter 5 The Resource Constrained Project 69 (14)
Scheduling Problem
5.1 Introduction 69 (1)
5.2 Graph modeling of the RCPSP 70 (1)
5.3 Notation 71 (1)
5.4 Single-mode RCPSP 72 (3)
5.4.1 Mathematical modeling of the 73 (1)
SM-RCPSP
5.4.2 An example of an SM-RCPSP 74 (1)
5.5 Multimode RCPSP 75 (1)
5.6 RCPSP with time windows 75 (1)
5.7 Solution approaches for solving the 76 (6)
RCPSP
5.7.1 A greedy algorithm for the RCPSP 76 (1)
5.7.2 A genetic algorithm for the RCPSP 77 (5)
5.8 Conclusion 82 (1)
Chapter 6 Spanning Tree Problems 83 (30)
6.1 Introduction 83 (1)
6.2 Minimum spanning tree problem 84 (4)
6.2.1 Notation 84 (1)
6.2.2 Mathematical formulation 84 (1)
6.2.3 Algorithms for the MST problem 85 (3)
6.3 Generalized minimum spanning tree 88 (12)
problem
6.3.1 Notation 90 (1)
6.3.2 Mathematical formulation 90 (3)
6.3.3 Greedy approaches for the GMST 93 (3)
problem
6.3.4 Genetic algorithm for the GMST 96 (4)
problem
6.4 k-cardinality tree problem KCT 100 (6)
6.4.1 Problem definition 100 (1)
6.4.2 An example 100 (2)
6.4.3 Notation 102 (1)
6.4.4 Mathematical formulation 103 (1)
6.4.5 Greedy approaches for the 103 (1)
k-cardinality tree problem
6.4.6 Minimum path approach 104 (1)
6.4.7 A genetic approach for the 105 (1)
k-cardinality problem
6.5 The capacitated minimum spanning tree 106 (6)
problem
6.5.1 Problem definition 106 (1)
6.5.2 Notation 107 (1)
6.5.3 An example 107 (1)
6.5.4 Solution approaches for the CMST 108 (4)
problem
6.6 Conclusion 112 (1)
Chapter 7 Steiner Problems 113 (12)
7.1 Introduction 113 (1)
7.2 The Steiner tree problem 114 (4)
7.2.1 Problem definition 114 (1)
7.2.2 Problem formulation 115 (1)
7.2.3 Constructive heuristics for the 115 (3)
Steiner tree problem
7.3 The price collecting Steiner tree 118 (5)
problem
7.3.1 Problem definition 118 (1)
7.3.2 Example 118 (1)
7.3.3 Mathematical formulation 118 (2)
7.3.4 A greedy approach to solve the 120 (1)
PCSTP
7.3.5 A genetic algorithm for the PCSTP 121 (2)
7.4 Conclusion 123 (2)
Chapter 8 A DSS Design for Optimization 125 (20)
Problems
8.1 Introduction 125 (1)
8.2 Definition of a DSS 126 (1)
8.3 Taxonomy of a DSS 127 (1)
8.4 Architecture and design of a DSS 128 (3)
8.4.1 Architecture of a DSS 129 (1)
8.4.2 DSS design 130 (1)
8.5 A DSS for the knapsack problem 131 (2)
8.6 A DSS for the DCVRP 133 (10)
8.6.1 Statement and modeling of the CVRP 136 (1)
8.6.2 Notation 137 (1)
8.6.3 Mathematical formulation of the 138 (1)
DCVRP
8.6.4 DCVRP-DSS interfaces 139 (2)
8.6.5 A real application: the case of 141 (2)
Tunisia
8.7 Conclusion 143 (2)
Conclusion 145 (2)
Glossary 147 (2)
Bibliography 149 (6)
Index 155
新书报道