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) 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 Annotation Combinatorial and global optimization problems appear in a wide range of applications in operations research, engineering, biological science, and computer science 7 On descriptive potentialities of the structure: Simple examples of global optimization problems