Modern heuristic techniques for combinatorial problems

This chapter discusses combinatorial problems local and global optima heuristics, the tabu framework, and Evaluation of heuristic performance: analytical methods empirical testing statistical inference conclusions.

Abstract

Part 1 Introduction: combinatorial problems local and global optima heuristics. Part 2 Simulated annealing: the basic method enhancements and modifications applications conclusions. Part 3 Tabu search: the tabu framework broader aspects of intensification and diversification tabu search applications connections and conclusions. Part 4 Genetic algorithms: basic concepts a simple example extensions and modifications applications conclusions. Part 5 Artificial neural networks: neural networks combinatorial optimization problems the graph bisection problem the graph partition problem the travelling salesman problem scheduling problems deformable templates inequality constraints, the Knapsack problem summary. Part 6 Lagrangian relaxation: overview basic methodology Lagrangian heuristics and problem reduction determination of Lagrange multipliers dual ascent tree search applications conclusions. Part 7 Evaluation of heuristic performance: analytical methods empirical testing statistical inference conclusions.