Abbreviations .................................................. xi
Symbols and Notation ........................................... xi
List of Tables ............................................... xiii
List of Figures ................................................ xv
List of Algorithms ........................................... xvii
1 Introduction ................................................. 1
1.1 Problems and Methods .................................... 1
1.1.1 Combinatorial Optimization ....................... 1
1.1.2 Facility Location-Network Design ................. 2
1.2 Outline and Contributions ............................... 3
1.3 Acknowledgments ......................................... 4
2 Preliminaries and Terminology ................................ 7
2.1 Sets and Graphs ......................................... 7
2.2 Complexity Theory ....................................... 8
2.2.1 Algorithms ....................................... 8
2.2.2 Problems ......................................... 8
2.3 Linear and Integer Programming .......................... 9
2.4 Shortest Path Problems and Solutions ................... 10
2.5 Branch-and-Cut ......................................... 11
2.5.1 Branch-and-Bound ................................ 13
2.5.2 The Cutting Plane Method ........................ 13
2.5.3 Branch-and-Cut .................................. 14
3 Facility Location and Network Design ........................ 15
3.1 Facility Location ...................................... 15
3.1.1 Median and Fixed Charge Problems ................ 16
3.1.2 Covering and Center Problems .................... 17
3.2 Network Design ......................................... 19
3.2.1 Inverse and Reverse Facility Location ........... 20
3.3 Facility Location-Network Design ....................... 21
3.3.1 Disaggregate IP Formulation ..................... 24
3.3.2 Aggregate IP Formulation ........................ 27
3.3.3 Comparing IP Formulations ....................... 28
4 Upper Bound Approaches: Heuristics .......................... 33
4.1 Greedy Heuristics ...................................... 35
4.2 A Custom Heuristic ..................................... 37
4.3 Neighborhoods and Neighbor Operators ................... 42
4.3.1 Hamming Neighborhoods ........................... 42
4.3.2 Step Neighborhoods .............................. 44
4.4 Local Search ........................................... 45
4.5 Simulated Annealing .................................... 47
4.6 Variable Neighborhood Search Heuristics ................ 50
4.6.1 Basic Variable Neighborhood Search .............. 51
4.6.2 Reduced Variable Neighborhood Search ............ 53
4.6.3 Variable Neighborhood Descent ................... 54
4.7 Comparison and Discussion .............................. 56
5 Lower Bound Approaches ...................................... 65
5.1 Improving the LP Relaxation of D ....................... 66
5.1.1 Knapsack Cuts ................................... 66
5.1.1.1 Target Cut Method ...................... 67
5.1.1.2 Ones Plus Method ....................... 68
5.1.2 Results ......................................... 71
5.2 Improving the LP Relaxation of A ....................... 73
5.2.1 Subset Cuts ..................................... 74
5.2.2 Similar Inequalities in the Literature .......... 76
5.2.3 Results ......................................... 76
5.3 Comparison and Discussion .............................. 77
6 Exact Approaches ............................................ 83
6.1 A Branch-and-Cut Solver ................................ 83
6.2 Results ................................................ 84
7 A Case Study: Nouna ......................................... 87
7.1 The Setting: Nouna Health District ..................... 87
7.2 Modeling as FLND ....................................... 90
7.3 Results ................................................ 92
8 Software: FLND Visualizer ................................... 99
8.1 Creating Problem Instances ............................. 99
8.2 Solving and Viewing Solutions ......................... 101
9 Discussion and Conclusions ................................. 105
A Test Instances .............................................. 107
References .................................................... 119
| 
