Probabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems

We extend our previous work applying first-level Tabu Search mechanisms to 0/1 MIP problems, introducing probabilistic measures for move selection. These are especially applicable when the move evaluation function is contaminated by noise or contains elements not directly related to the objective function value. We also look at the possibility of replacing tabu memory completely by associated probabilistic guidance. Our approach is designed with the ability to solve general 0/1 MCP problems, and thus contains no problem domain specific knowledge. The outcome improves significantly on the solutions obtained by the first-level Tabu Search mechanisms previously employed. The probabilistic measures are extremely simple to implement, and can be readily incorporated in standard Tabu Search designs.