# Handbook of Combinatorial Optimization

Springer Science & Business Media, Dec 1, 2013 - Mathematics - 2406 pages
Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied math ematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, air line crew scheduling, corporate planning, computer-aided design and man ufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. Furthermore, combinatorial optimization problems occur in many diverse areas such as linear and integer programming, graph theory, artificial intelligence, and number theory. All these problems, when formulated mathematically as the minimization or maximization of a certain function defined on some domain, have a commonality of discreteness. Historically, combinatorial optimization starts with linear programming. Linear programming has an entire range of important applications including production planning and distribution, personnel assignment, finance, alloca tion of economic resources, circuit simulation, and control systems. Leonid Kantorovich and Tjalling Koopmans received the Nobel Prize (1975) for their work on the optimal allocation of resources. Two important discover ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These algo rithms have had a profound effect in combinatorial optimization. Many polynomial-time solvable combinatorial optimization problems are special cases of linear programming (e.g. matching and maximum flow). In addi tion, linear programming relaxations are often the basis for many approxi mation algorithms for solving NP-hard problems (e.g. dual heuristics).

### What people are saying -Write a review

We haven't found any reviews in the usual places.

### Contents

 MixedInteger Nonlinear Optimization in Process Synthesis 1 41 MINOPT 51 Acknowledgments 71 Approximate Algorithms and Heuristics for MAXSAT 77 Approximate Algorithms and Heuristics 79 Continuous approaches 85 A different MAXSAT problem and completeness results 117 Memoryless Local Search Heuristics 128
 Optimization Approach in Process Synthesis 2 Computing Distances between Evolutionary Trees 35 35 Combinatorial Optimization and Coalition Games 77 77 An Introduction 105 Resource Allocation Problems 159 159 Combinatoral Optimization in Clustering 261 261 A Bibliographic Survey 331 331 ksC 374

 Experimental analysis and threshold effects 136 Connections between Nonlinear Programming 149 Connections between Nonlinear Programming 150 Equivalence between Integer and Real Optimization 157 Piecewise Concave Functions and Minimax 168 Interior Point Methods for Combinatorial 190 Interior Point Methods for Combinatorial Optimization 191 Solution techniques 202 Knapsack Problems 299 Subsetsum Problem 351 Multiplechoice Knapsack Problem 364 Bounded Knapsack Problem 382 Unbounded Knapsack Problem 394 Multiple Knapsack Problem 402 Conclusion and Future Trends 417 Fractional Combinatorial Optimization 429 Abstract 459 ReformulationLinearization Techniques 479 Knapsack Problems are the simplest MPhard problems in Combinatorial 482 Gröbner Bases in Integer Programming 533 Applications of Set Covering Set Packing 573 Efficient Algorithms for Geometric 1
 Dynamical System Approaches 471 Online Dominating Set Problems for Graphs 525 525 Optimization Problems in Optical Networks 543 543 Shortest Networks on Surfaces 589 589 Minimum Weight Triangulations 617 617 Optimization Applications in the Airline Industry 635 635 Semidefinite Relaxations Multivariate Normal 2 Routing and Topology Embedding in Lightwave Networks 171 171 The Quadratic Assignment Problem 241 241 Algorithmic Aspects of Domination in Graphs 339 339 Selected Algorithmic Techniques for Parallel Optimization 407 407 Multispace Search for Combinatorial Optimization 457 457 The Equitable Coloring of Graphs 543 543 Randomized Parallel Algorithms 567 Tabu Search 621 621 Author Index 747 Subject Index 773 Author Index 727 727 Subject Index 749 749 Subject Index 779 779 Subject Index of Volumes 13 845 Copyright