Tabu Search for zero-one mixed integer programming with advanced level strategies and learning

The authors show how carefully designed Tabu Search mechanisms can work together efficiently to give high quality solutions to general zero-one mixed integer programming problems. They also show how the learning tool called Target Analysis can be applied in this setting to identify better control structures and decision rules. The present approach is designed to solve thoroughly general 0/1 MIP problems and thus contains no problem domain specific knowledge. Nevertheless, applied to a portfolio of multiconstraint knapsack test problems from the literature, the method obtains solutions whose quality rivals, and in some cases surpasses, that of the best solutions obtained by special purpose methods that have been created to exploit the special structure of these problems.