Table of Contents

Introduction ix
Gerd FINKE

Chapter 1. Linear Programming 1
Gerd FINKE and Nadia BRAUNER

1.1. Fundamental concepts 1

1.2. Software 9

1.3. Indivisible units 14

1.4. Modeling with integer variables 22

1.5. Conclusion 27

1.6. Bibliography 28

Chapter 2. Graphs and Networks 29
Wojciech BIENIA

2.1. The concept of a graph 29

2.2. Sub-structures and exploration 31

2.3. Edge-and vertex-connectivity 34

2.4. Directed graphs 36

2.5. Valued graphs and networks 37

2.5.1. The shortest spanning tree problem in a connected graph 37

2.5.2. The shortest path 41

2.6. Assignment and coloring 46

2.6.1. Matchings 46

2.6.2. Vertex colorings 48

2.7. Flow in networks 53

2.8. Conclusion 68

2.9. Bibliography 68

Chapter 3. Classical Combinatorial Problems and Solution Techniques 71
Clarisse DHAENENS, Marie-Laure ESPINOUSE and Bernard PENZ

3.1. Introduction 71

3.2. Classical optimization problems 72

3.2.1. Introduction 72

3.2.2. Combinatorial optimization problems in graph theory 72

3.2.3. Assignment Problems 73

3.2.4. Transportation problems 74

3.2.5. Location problems 75

3.2.6. Scheduling problems 76

3.3. Complexity 77

3.4. Solution of hard problems 80

3.4.1. Introduction 80

3.4.2. Relaxations 81

3.4.3. Heuristic methods of construction 81

3.4.4. Improvement methods 83

3.4.5. Exact methods 90

3.5. Conclusion 101

3.6. Bibliography 102

Chapter 4. Project Scheduling 105
Lionel DUPONT

4.1. Presentation 105

4.1.1. Conducting a project 105

4.1.2. Definitions 106

4.1.3. Scheduling methods 108

4.2. Scheduling and graphs without cycles 108

4.3. Fundamental problem 113

4.3.1. Calculation of the earliest dates 113

4.3.2. Calculation of the latest dates 114

4.3.3. Margins 116

4.4. Visualizations 117

4.4.1. Representation on the graph PERT/CPM 117

4.4.2. Gantt chart 118

4.5. Probabilistic PERT 119

4.5.1. Analytic solution 120

4.5.2. Solution by simulation 122

4.6. Sequencing with disjunctive constraints 123

4.7. Sequencing with cumultative constraints: serial methods 126

4.8. Time-cost trade-off problem 131

4.9. Conclusion 135

4.10. Bibliography 135

Chapter 5. Operations Management in Transportation Networks 137
Jacques DESROSIERS

5.1. Introduction 137

5.1.1. A bit of history 137

5.1.2. University–industry: a winning partnership 138

5.2. Fundamental notions 139

5.2.1. A common structure 139

5.2.2. The shortest path problem with time windows 140

5.2.3. Some mathematics 141

5.2.4. A generic algorithm 142

5.3. A mechanism of decomposition 145

5.3.1. Local restrictions and global constraints 145

5.3.2. The column generation method 148

5.3.3. Solutions satisfying the integrality constraints 150

5.4. Diversity of the local restrictions 151

5.4.1. A few words on the extension functions 151

5.4.2. Modeling examples 154

5.5. Applications in large transportation networks 156

5.5.1. Urban transportation 156

5.5.2. Air transportation 157

5.5.3. Rail transportation 158

5.6. What does the future look like? 159

5.7. Bibliography 160

Chapter 6. Pickup and Delivery Problems with Services on Nodes or Arcs of a Network 165
Alain HERTZ and Michel MITTAZ

6.1. Introduction 165

6.2. Node routing problems 166

6.2.1. The traveling salesman problem 166

6.2.2. Vehicle tours with capacity constraints 170

6.3. Arc routing problems 174

6.3.1. The Chinese postman problem 174

6.3.2. The rural postman problem 177

6.3.3. Arc routing problems with capacity constraints 183

6.4. Conclusion 185

6.5. Bibliography 186

Chapter 7. Telecommunication Networks 189
Alexandre CAMINADA, Jin-Kao HAO, Jean-Luc LUTTON and Vincent MARTIN

7.1. Introduction 189

7.2. Optimal synthesis of backbone networks 190

7.3. Topology and dimensioning of the nominal network 193

7.3.1. Descent algorithm 194

7.3.2. Simulated annealing 197

7.4. Dimensioning of spare capacities 200

7.4.1. Non-simultaneous multiflow model and linear programming 200

7.4.2. Solution of non-simultaneous multiflows by decomposition 203

7.4.3. Extension of the decomposition model for modular capacities 206

7.5. Conception of cellular networks 208

7.6. Antenna positioning and configuration 210

7.6.1. Multicriteria model 212

7.6.2. A heuristic for positioning antennas 215

7.7. Frequency assignment 220

7.7.1. Modeling by set T-coloring 223

7.7.2. Solution by evolutionary algorithms 224

7.8. Conclusion 228

7.9. Bibliography 229

Chapter 8. Mission Planning for Observation Satellites 235
Virginie GABREL, Cécile MURAT and Vangelis PASCHOS

8.1. Introduction 235

8.2. Description of the problem of planning satellite shots 237

8.2.1. Context: image acquisitions – constraints of the satellite used 237

8.2.2. Problems studied 239

8.3. Models and formulations of induced combinatorial problems 241

8.4. Algorithms for MS and MSO 246

8.4.1. Solving MS 246

8.4.2. Solving MSO in the discrete case 251

8.4.3. Solving MSO in the continuous case 251

8.5. Experiments and numerical results 257

8.5.1. Performances of approximate algorithms proposed to solve MS 257

8.5.2. Performances of approximate algorithms proposed to solve MSO 259

8.6. Conclusion 261

8.7. Bibliography 261

List of Authors 263

Index 265

About the Author

Gerd Finke is currently Professor of operation research at the Joseph Fourier university in Grenoble, France.