Combinatorial and Global OptimizationCombinatorial 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
Preface | 1 |
References | 9 |
Exact Rates of Prokhorov Convergence under Three Moment Condi | 33 |
Algorithms for the Consistency Analysis in Scenario Projects | 55 |
Assignment of Reusable and NonReusable Frequencies | 75 |
Image Space Analysis for Vector Optimization and Variational Inequal | 97 |
Solving Quadratic Knapsack Problems by Reformulation and Tabu | 111 |
4 | 128 |
6 | 222 |
References | 231 |
A New Finite Cone Covering Algorithm for Concave Minimization | 237 |
A Diagonal Global Optimization Method | 251 |
References | 258 |
Frequency Assignment for Very Large Sparse Networks | 265 |
A Derivative Free Minimization Method for Noisy Functions | 283 |
Tight QAP Bounds via Linear Programming | 297 |
Semidefinite Programming Approaches for MAX2SAT and MAX3 | 161 |
A A Groenwold and J A Snyman | 173 |
On a Data Structure in a Global Description of Sequences | 177 |
Heuristic Solutions of Vehicle Routing Problems in Supply Chain Man | 205 |
An Application of the Simulated Annealing | 305 |
ImpactEcho Experiments317 | 317 |
Normal Branch and Bound Algorithms for General Nonconvex Quadratic | 333 |
Other editions - View all
Combinatorial and Global Optimization Panos M Pardalos,Athanasios Migdalas,Rainer E Burkard Limited preview - 2002 |
Common terms and phrases
AFA1 AFA2 approach arc cost function assignment problem branch and bound bundle Combinatorial and Global computational concave consider consistency constraints convergence convex cone crack defined denote efficient exists extreme points facility FCNFP fixed charge formulation frequency assignment function value geometric given Global Optimization graph graph coloring Hamiltonian cycle Hamiltonian path heuristic HSGT inequalities instances integer patterns integer relations inter-clique edges iteration Lemma local minima locally convex space lower bound Math Mathematics matrix method Migdalas minimization minimum network flow network flow problem nodes NP-complete objective function obtained Operations Research optimal solution optimization problems P.M. Pardalos partition piecewise linear PLNFP polynomial procedure programming Proof quadratic radio labelling random SDP relaxation sequence sequential Simulated Annealing solve Step structural numbers tabu search technique Theorem tour traveling salesman problem unsat variables Vector Optimization vehicle routing problem vertex vertices