ABSTRACT
Many combinatorial optimization problems are remarkably simple to state and intuitively easy to understand, requiring little mathematical sophistication. This chapter examines some heuristic and metaheuristic methods that are currently popular, effective, and practical. Greedy heuristics are probably the simplest type of heuristics in which a partial solution is constructed step by step towards a complete solution based on basic known information of a problem instance. Simulated annealing is a technique that can be quite easy to implement. Specific details of an implementation often depend on the type of problem being solved. Genetic algorithms (GA) are a type of search algorithm for finding optimal solutions to computationally difficult problems, and are based on analogies to biological reproductive processes. Constraint programming assumes that the problem can be described as a set of variables and a set of constraints that restrict the feasible solutions for a problem. Heuristic techniques guided entirely by opportunities for improvement often converge rapidly to a local optimal solution.
