Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems

The design of effective exact enumerative algorithms for finding the optimal solution of a given NP-hard combinatorial optimization problem, whose mathematical model is given by an integer linear program, is considered. The commonly used approaches, i.e., dynamic programming, branch-and-bound, branch-and-cut and branch-and-price, are shortly described. Since the ‘most effective’ algorithm to be used for finding the optimal solution of a given problem strongly depends on the specific instance to be solved, then the ‘best’ results are often obtained by using hybrid algorithms, i.e., by combining different approaches, according to what can be called an optimization engineering technique. To illustrate the above-mentioned approach, the well-known 0–1 knapsack problem, asymmetric travelling salesman problem and 2-constraint bin packing problem are considered.