A computational note on the Martello-Toth knapsack algorithm

Martello and Toth are well known for their work on the 0-1 kanpsack problem. Computationally, their MT2 algorithm is one of the most efficient exact algorithms published in the OR/MS literature. For uncorrelated and weakly correlated data sets, Martello and Toth have shown that their MT2 algorithm can solve up to 10000 variable problems very quickly. However, for strongly correlated data sets, even MT2 could only solve up to 100 variable problems without exceeding the time limit. This note takes a closer look at the empirical performance of the Martello-Toth MT2 algorithm on strongly correlated data sets.