Complexity Indices for the Multidimensional Knapsack Problem

In this article, the concept of conditioning in integer programming is extended to the concept of a complexity index. A complexity index is a measure through which the execution time of an exact algorithm can be predicted. We consider the multidimensional knapsack problem with instances taken from the OR-library and MIPLIB. The complexity indices we developed correspond to the eigenvalues of a Dikin matrix placed in the center of a polyhedron defined by the constraints of the problem relaxed from its binary variable formulation. The lower and higher eigenvalues, as well as their ratio, which we have defined as the slenderness, are used as complexity indices. The experiments performed show a good linear correlation between these indices and a low execution time of the Branch and Bound algorithm using the standard version of CPLEX® 12.2. The correlation coefficient obtained ranges between 39 and 60% for the various data regressions, which proves a medium to strong correlation. © 2018, Springer-Verlag GmbH Germany, part of Springer Nature.