Automatic Generation of Algorithms for the Binary Knapsack Problem

Because it is classified as NP-hard, the binary knapsack problem is a good example of a combinatorial optimization problem that still presents increased difficulty when attempting to determine the optimal solution for any instance. Although exact and heuristic methods have been developed in an attempt to solve the problem, such methods have been unable to solve even small instances of the problem. In this paper, new algorithms for this problem are automatically generated by means of genetic programming from sets of training instances of different sizes and are then evaluated against other larger sized sets of instances, thereby detecting the robustness of the algorithms for larger instances. Overall, the produced algorithms are able to identify up to 52% of the optimal solutions for the biggest instances used. © 2013 IEEE.