Combinatorial and Global Optimization

R.E. Burkard, Panos M. Pardalos, Athanasios Migdalas, Rainer E. Burkard9810248024, 9789810248024, 9789812778215

A selection of refereed papers based on talks presented at a conference on ‘Combinatorial and Global Optimization’ held at Crete, Greece. For researchers in numerical and computational mathematics, optimization, combinatorics and graph theory, networking and materials engineering.

---

Table of contents :
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