Combinatorial and Global Optimization

"Combinatorial and global optimization problems appear in a wide range of applications in operations research, engineering, biological science, and computer science. In combinatorial optimization and graph theory, many approaches have been developed that link the discrete universe to the continuous universe through geometric, analytic, and algebraic techniques. Such techniques include global optimization formulations, semidefinite programming, and spectral theory. Recent major successes based on these approaches include interior point algorithms for linear and discrete problems, the celebrated Goemans Williamson relaxation of the maximum cut problem, and the Du Hwang solution of the Gilbert Pollak conjecture. Since integer constraints are equivalent to nonconvex constraints, the fundamental difference between classes of optimization problems is not between discrete and continuous problems but between convex and nonconvex optimization problems. This volume is a selection of refereed papers based on talks presented at a conference on "Combinatorial and Global Optimization" held at Crete, Greece." Readership: Researchers in numerical & computational mathematics, optimization, combinatorics & graph theory, networking and materials engineering. Booknews Papers from a recent conference held in Greece report on work in different aspects of combinatorial and global optimization and in complementary aspects of mathematical programming. Specific topics include a hybrid scatter genetic tabu approach for continuous global optimization, exact rates of Prokhorov convergence under three moment conditions, algorithms for the consistency analysis in scenario projects, assignment of reusable and non-reusable frequencies, and image space analysis for vector optimization and variational inequalities. This work lacks a subject index. Annotation c. Book News, Inc., Portland, OR (booknews.com) 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 A forest exterior point algorithm for assignment problems / H. Achatz [und weitere] -- A hybrid scatter genetic tabu approach for continuous global optimization / I.M. Al-Harkan and T.B. Trafalis -- Exact rates of Prokhorov convergence under three moment conditions / G.A. Anastassiou and T. Rychlik -- Location/allocation of queuing facilities in continuous space using minsum and minimax criteria / J. Brimberg, R.F. Love and A. Mehrez -- Algorithms for the consistency analysis in scenario projects / R. Feldmann [und weitere] -- Assignment of reusable and Non-reusable frequencies / D.A. Fotakis and P.G. Spirakis -- Image space analysis for vector optimization and variational inequalities. Scalarization / F. Giannessi and L. Pellegrini -- Solving quadratic knapsack problems by reformulation and tabu search. Single constraint case / F. Glover [und weitere] -- Global optimization using dynamic search trajectories / A.A. Groenwold and J.A. Snyman -- On Pareto efficiency. A general constructive existence principle / G. Isac -- Piecewise linear network flow problems / D. Kim and P.M. Pardalos -- Semidefinite programming approaches for MAX-2-SAT and MAX-3-SAT: computational perspectives / E. de Klerk and J.P. Warners -- On a data atructure in a global description of sequences / V. Korotkich -- Heuristic solutions of vehicle routing problems in supply chain management / Y. Marinakis and A. Migdalas -- A new finite cone covering algorithm for concave minimization / C. Meyer and B. Jumard -- A diagonal global optimization method / A. Molinaro, C. Pizzuti and Y.D. Sergeyev -- Frequency assignment for very large, sparse networks / R. Murphey -- A derivative free minimization method for noisy functions / V.P. Plagianakos and M.N. Vrahatis -- Tight QAP bounds via linear programming / K.G. Ramakrishnan [und weitere] -- GPS network design: an application of the simulated annealing heuristic technique / H.A. Saleh and P.J. Dare -- Global optimization for crack identification: impact-echo experiments / G.E. Stavroulakis -- Normal branch and bound algorithms for general nonconvex quadratic programming / H. Tuy 1 Main result2 Outline of proof; References; Location/Allocation of Queuing Facilities in Continuous Space using Minisum and Minimax Criteria; 1 Introduction; 2 The model; 3 A solution method; 4 Computational results; 5 Conclusions; References; Algorithms for the Consistency Analysis in Scenario Projects; 1 Introduction; 2 Definitions; 3 Complexity; 4 Algorithms; 5 Conclusions; References; Assignment of Reusable and Non-Reusable Frequencies; 1 Introduction; 2 Definitions and techniques; 3 The complexity of radio coloring and radio labelling; 4 An exact algorithm for constant number of colors 3 Additional valid inequalities4 Solving the SDP relaxation of MAX-2-SAT; 5 A branch and cut framework; 6 Numerical experiments; 7 Future work; References; On a Data Structure in a Global Description of Sequences; 1 Introduction; 2 Structural numbers and their geometric interpretation; 3 Structural numbers as coordinates of a space and a system of linear equations; 4 Integer patterns: Means for the visualization of the system; 5 What picture appears when the system is visualized: An illustrative example; 6 Definition of the structure and its isomorphic representations: Web of relations 5 Algorithms for on-line radio labelling6 Open problems; References; Image Space Analysis for Vector Optimization and Variational Inequalities. Scalarization; 1 Introduction; 2 A separation scheme; 3 On the scalarization of vector optimization; 4 Vector variational inequalities; References; Solving Quadratic Knapsack Problems by Reformulation and Tabu Search. Single Constraint Case; 1 Introduction; 2 Reformulation; 3 Computational experiments; 4 Summary and conclusions; Appendix: Overview of our tabu search algorithm; References; Global Optimization using Dynamic Search Trajectories Preface; Contents; A Forest Exterior Point Algorithm for Assignment Problems; 1 Introduction; 2 Preliminaries; 3 Description of the algorithm; 4 Correctness and complexity of the algorithm; 5 Concluding remarks; References; A Hybrid Scatter Genetic Tabu Approach for Continuous Global Optimization; 1 Introduction; 2 Genetic scatter search and tabu serach approach; 3 HSGT algorithm description; 4 Weight computations; 5 Computational results; 6 Conclusions and recommendations; Appendix A: Test functions; References; Exact Rates of Prokhorov Convergence under Three Moment Conditions 1 Introduction2 The Snyman-Fatti trajectory method; 3 The modified bouncing ball trajectory method; 4 Global stopping criterion; 5 Numerical results; 6 Conclusions; References; On Pareto Efficiency. A General Constructive Existence Principle; 1 Introduction; 2 Preliminaries; 3 The main result; 4 Realizations of Theorem 1; References; Piecewise Linear Network Flow Problems; 1 Introduction; 2 Applications; 3 Concluding remarks; References; Semidefinite Programming Approaches for MAX-2-SAT and MAX-3-SAT: computational perspectives; 1 Introduction; 2 The SDP relaxation of MAX-2-SAT 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.