Combinatorial and Global Optimization

9810248024......Page 1
Contents......Page 10
Preface......Page 8
A Forest Exterior Point Algorithm for Assignment Problems......Page 18
2 Preliminaries......Page 19
3 Description of the algorithm......Page 20
4 Correctness and complexity of the algorithm......Page 22
References......Page 26
A Hybrid Scatter Genetic Tabu Approach for Continuous Global Optimization......Page 28
1 Introduction......Page 29
2 Genetic scatter search and tabu serach approach......Page 30
3 HSGT algorithm description......Page 33
4 Weight computations......Page 35
5 Computational results......Page 37
6 Conclusions and recommendations......Page 38
Appendix A: Test functions......Page 39
References......Page 46
Exact Rates of Prokhorov Convergence under Three Moment Conditions......Page 50
1 Main result......Page 51
2 Outline of proof......Page 55
References......Page 59
Location/Allocation of Queuing Facilities in Continuous Space using Minisum and Minimax Criteria......Page 60
1 Introduction......Page 61
2 The model......Page 62
3 A solution method......Page 65
4 Computational results......Page 67
References......Page 69
Algorithms for the Consistency Analysis in Scenario Projects......Page 72
1 Introduction......Page 73
2 Definitions......Page 75
3 Complexity......Page 76
4 Algorithms......Page 80
References......Page 89
Assignment of Reusable and Non-Reusable Frequencies......Page 92
1 Introduction......Page 93
2 Definitions and techniques......Page 94
3 The complexity of radio coloring and radio labelling......Page 98
4 An exact algorithm for constant number of colors......Page 101
5 Algorithms for on-line radio labelling......Page 107
6 Open problems......Page 110
References......Page 111
Image Space Analysis for Vector Optimization and Variational Inequalities. Scalarization......Page 114
1 Introduction......Page 115
2 A separation scheme......Page 116
3 On the scalarization of vector optimization......Page 118
4 Vector variational inequalities......Page 122
References......Page 125
Solving Quadratic Knapsack Problems by Reformulation and Tabu Search. Single Constraint Case......Page 128
1 Introduction......Page 129
2 Reformulation......Page 130
3 Computational experiments......Page 132
4 Summary and conclusions......Page 136
References......Page 137
Global Optimization using Dynamic Search Trajectories......Page 140
1 Introduction......Page 141
2 The Snyman-Fatti trajectory method......Page 142
3 The modified bouncing ball trajectory method......Page 144
4 Global stopping criterion......Page 145
5 Numerical results......Page 146
References......Page 148
1 Introduction......Page 150
2 Preliminaries......Page 152
3 The main result......Page 153
4 Realizations of Theorem 1......Page 154
References......Page 159
Piecewise Linear Network Flow Problems......Page 162
1 Introduction......Page 163
2 Applications......Page 173
3 Concluding remarks......Page 174
References......Page 175
Semidefinite Programming Approaches for MAX-2-SAT and MAX-3-SAT: computational perspectives......Page 178
2 The SDP relaxation of MAX-2-SAT......Page 179
3 Additional valid inequalities......Page 182
4 Solving the SDP relaxation of MAX-2-SAT......Page 183
5 A branch and cut framework......Page 185
6 Numerical experiments......Page 188
7 Future work......Page 189
References......Page 192
1 Introduction......Page 194
2 Structural numbers and their geometric interpretation......Page 196
3 Structural numbers as coordinates of a space and a system of linear equations......Page 198
4 Integer patterns: Means for the visualization of the system......Page 202
5 What picture appears when the system is visualized: An illustrative example......Page 203
6 Definition of the structure and its isomorphic representations: Web of relations......Page 208
7 On descriptive potentialities of the structure: Simple examples of global optimization problems......Page 212
References......Page 220
Heuristic Solutions of Vehicle Routing Problems in Supply Chain Management......Page 222
2 Supply chain management......Page 223
3 The vehicle routing problem......Page 224
4 Classic heuristics for the traveling salesman and the vehicle routing problems......Page 227
5 Metaheuristics for the traveling salesman and the vehicle routing problems......Page 236
6 Computational results......Page 245
References......Page 248
A New Finite Cone Covering Algorithm for Concave Minimization......Page 254
1 Introduction......Page 255
2 Basic operations......Page 256
3 Algorithm......Page 263
References......Page 264
A Diagonal Global Optimization Method......Page 268
1 Introduction......Page 269
2 Diagonal information global optimization algorithm and its new convergence conditions......Page 270
3 A new diagonal information algorithm......Page 273
4 Numerical results......Page 275
5 Conclusions......Page 277
References......Page 279
Frequency Assignment for Very Large Sparse Networks......Page 282
1 Introduction......Page 283
2 Minimum order and minimum span assignments......Page 284
3 Alternate graph approach......Page 289
4 Local search......Page 292
5 Experimental results......Page 293
References......Page 297
1 Introduction......Page 300
2 Optimization of noisy functions......Page 301
3 A derivative-free minimization method for imprecise problems and its convergence......Page 303
4 Numerical applications......Page 306
5 Concluding remarks......Page 310
References......Page 311
Tight QAP Bounds via Linear Programming......Page 314
1 LP-based lower bounds for the QAP......Page 315
2 Experimental results......Page 316
3 Concluding remarks......Page 318
References......Page 319
GPS Network Design: An Application of the Simulated Annealing Heuristic Technique......Page 322
1 Introduction......Page 323
3 Formulation of the GPS surveying problem......Page 324
5 Computational results......Page 326
6 Further work and conclusion......Page 327
References......Page 328
1 Introduction......Page 334
2 Global optimization for inverse problems......Page 336
3 Mechanical modelling......Page 337
4 Inverse problem......Page 343
5 Conclusion......Page 345
References......Page 346
1 Introduction......Page 350
2 A generic BB algorithm......Page 352
3 Examples......Page 355
4 Quadratic system equivalent to a linear system......Page 357
5 General decoupling scheme......Page 361
6 Linear relaxations......Page 362
7 Semidefinite relaxation......Page 366
References......Page 370