Heuristics
Haksun Li · Apress eBooks · 2022
In computer science and mathematical optimization, a heuristic is a procedure designed to find a good enough solution to an optimization problem when the classical methods (LP, QP, SOCP, SDP, SQP) that we discussed in the past few chapters fail, are too slow, are infeasible, or are not applicable. This is especially true when the problem is too big (e.g., beyond the limited computation capacity), have incomplete or imperfect information (e.g., lack of structure for pruning), have a complex objective function (e.g., nondifferentiable), or have difficult constraints (rule-based constraints, exceptions). A heuristic often speeds up the computation by eliminating a large subset of the solution candidates using ad hoc rules. Equivalently, it searches only a subset of the solution space that is otherwise too large to be completely enumerated or otherwise explored. Those ad hoc rules often make assumptions about the problem being solved and hence also the solution space. They may or may not eliminate the true solutions. Although these ad hoc rules are often not proven or given their properties, in practice heuristics often return good usable solutions to many otherwise unsolvable problems, such as the whole class of NP-Complete problems like the traveling salesman problem.