Background
----------

This dataset is associated with the following papers:

T. Dokka, A.N. Letchford & M.H. Mansoor (2021) On the complexity of surrogate and group relaxation for integer linear programs. Oper. Res. Lett., 49(4), 530-534.

T. Dokka, A.N. Letchford & M.H. Mansoor (2022) Revisiting surrogate relaxation for the multidimensional knapsack problem. Working paper, Department of  Management Science, Lancaster University UK.

The dataset is concerned with the computation of upper bounds for benchmark instances of the Multidimensional Knapsack Problem (MKP). For background on the MKP, see, for example:

A. Fréville (2004) The multidimensional 0-1 knapsack problem: An overview. Eur. J. Oper. Res., 155, 1-21.

H. Kellerer, U. Pferschy & D. Pisinger (2004) Knapsack Problems. Heidelberg: Springer.

Instances
---------

There exist several sets of benchmark instances. We considered five sets, all of which are available at the OR Library (ORlib):

1. Seven instances from Petersen (1967).

2. Two instances from Senyu & Toyada (1967).

3. Nine instances from Weingartner & Ness (1967).

4. Ninety instances from Shi (1979).

5. Two-hundred and seventy instances from Chu & Beasley (1998).

At the time of writing, all of these instances had been solved exactly, apart from the largest 60 Chu-Beasley instances. See, for example:

R. Mansini & M.G. Speranza (2012) CORAL: an exact algorithm for the
multidimensional knapsack problem. INFORMS J. Comput., 24, 399-415.

Spreadsheet Format
------------------

Our spreadsheet has one tab for each of the first four sets. For the last set, we have two tabs (one for the solved instances and one for the unsolved ones). For the instances in the first four sets, the interpretation of the spreadsheet is as follows:

Column A: Instance name.
Column B: Number of items (n).
Column C: Number of constraints (m).
Column D: Optimal solution value (OPT).
Column E: Upper bound from the linear programming (LP) relaxation (UB).
Column F:  Gap between the LP upper bound and the optimum, expressed as a percentage of the optimum (%gap).
Column G: Time taken to solve the LP on our machine, in seconds (time).
Column H: Upper bound obtained by solving the surrogate dual (SD) exactly (UB).
Column I: Gap between the SD upper bound and the optimum, expressed as a percentage of the optimum (%gap).
Column J: Number of major iterations in our algorithm for solving the SD (# iter).
Column K: Number of cutting planes generated in our algorithm for solving the SD (# cuts).
Column L: Time taken to solve the SD on our machine, in seconds (time).

For the Chu-Beasley instances, we have an additional column that displays the so-called "tightness parameter" delta.  Also, for the unsolved Chu-Beasley instances, we display the best known lower bound instead of the optimal solution value.