A COMPUTATIONAL NOTE ON THE MARTELLO-TOTH KNAPSACK ALGORITHM

Martello and Toth are well known for their work on the 0-1 knapsack pr oblem. Computationally, their MT2 algorithm is one of the most efficie nt exact algorithms published in the OR/MS literature. For uncorrelate d and weakly correlated data sets, Martello and Toth have shown that t heir MT2 algorithm can solve up to 10000 variable problems very quickl y. However, for strongly correlated data sets, even MT2 could only sol ve up to 100 variable problems without exceeding the time limit. In th is note we take a closer look at the empirical performance of the Mart ello-Toth MT2 algorithm on strongly correlated data sets.