Combinatorial and Global Optimization.
Title:
Combinatorial and Global Optimization.
Author:
Pardalos, Panos M.
ISBN:
9789812778215
Personal Author:
Physical Description:
1 online resource (373 pages)
Series:
Series on Applied Mathematics ; v.14
Series on Applied Mathematics
Contents:
Contents -- Preface -- 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 Main result -- 2 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 -- 5 Algorithms for on-line radio labelling -- 6 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 -- 1 Introduction -- 2 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 -- 3 Additional valid inequalities -- 4 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 -- 7 On descriptive potentialities of the structure: Simple examples of global optimization problems -- References -- Heuristic Solutions of Vehicle Routing Problems in Supply Chain Management -- 1 Introduction -- 2 Supply chain management -- 3 The vehicle routing problem -- 4 Classic heuristics for the traveling salesman and the vehicle routing problems -- 5 Metaheuristics for the traveling salesman and the vehicle routing problems -- 6 Computational results -- References.
A New Finite Cone Covering Algorithm for Concave Minimization -- 1 Introduction -- 2 Basic operations -- 3 Algorithm -- 4.Conclusions -- References -- A Diagonal Global Optimization Method -- 1 Introduction -- 2 Diagonal information global optimization algorithm and its new convergence conditions -- 3 A new diagonal information algorithm -- 4 Numerical results -- 5 Conclusions -- References -- Frequency Assignment for Very Large Sparse Networks -- 1 Introduction -- 2 Minimum order and minimum span assignments -- 3 Alternate graph approach -- 4 Local search -- 5 Experimental results -- 6 Conclusions -- References -- A Derivative Free Minimization Method for Noisy Functions -- 1 Introduction -- 2 Optimization of noisy functions -- 3 A derivative-free minimization method for imprecise problems and its convergence -- 4 Numerical applications -- 5 Concluding remarks -- References -- Tight QAP Bounds via Linear Programming -- 1 LP-based lower bounds for the QAP -- 2 Experimental results -- 3 Concluding remarks -- References -- GPS Network Design: An Application of the Simulated Annealing Heuristic Technique -- 1 Introduction -- 2 Simulated annealing technique -- 3 Formulation of the GPS surveying problem -- 4 The GPS-simulated annealing algorithm -- 5 Computational results -- 6 Further work and conclusion -- References -- Global Optimization for Crack Identification:Impact-Echo Experiments -- 1 Introduction -- 2 Global optimization for inverse problems -- 3 Mechanical modelling -- 4 Inverse problem -- 5 Conclusion -- References -- Normal Branch and Bound Algorithms for General Nonconvex Quadratic Programming -- 1 Introduction -- 2 A generic BB algorithm -- 3 Examples -- 4 Quadratic system equivalent to a linear system -- 5 General decoupling scheme -- 6 Linear relaxations -- 7 Semidefinite relaxation -- References.
Abstract:
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. Contents: A Forest Exterior Point Algorithm for Assignment Problems (H Achatz et al.); Location/Allocation of Queuing Facilities in Continuous Space Using Minsum and Minimax Criteria (J Brimberg et al.); Algorithms for the Consistency Analysis in Scenario Projects (R Feldmann et al.); Solving Quadratic Knapsack Problems by Reformulation and Tabu Search. Single Constraint Case (F Glover et al.); Global Optimization Using Dynamic Search Trajectories (A A Groenwold & J A Snyman); On Pareto Efficiency. A General Constructive Existence Principle (G Isac); Piecewise Linear Network Flow Problems (D Kim & P M Pardalos); Semidefinite Programming Approaches for MAX-2-SAT and MAX-3-SAT: Computational Perspectives (E de Klerk & J P Warners); Heuristic Solutions of
Vehicle Routing Problems in Supply Chain Management (Y Marinakis & A Migdalas); A New Finite Cone Covering Algorithm for Concave Minimization (C Meyer & B Jaumard); Frequency Assignment for Very Large, Sparse Networks (R Murphey); GPS Network Design: An Application of the Simulated Annealing Heuristic Technique (H A Saleh & P J Dare); Normal Branch and Bound Algorithms for General Nonconvex Quadratic Programming (H Tuy); and other papers. Readership: Researchers in numerical & computational mathematics, optimization, combinatorics & graph theory, networking and materials engineering.
Local Note:
Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2017. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.
Genre:
Electronic Access:
Click to View