The importance of fine-tuning Gurobi parameters when solving quadratic knapsack problems: A guide for OR practitioners

Dominic Rando, Yun Lu, Myung Soon Song, Francis J. Vasko

Article ID: 8052
Vol 1, Issue 1, 2024


Abstract


In the operations research (OR) literature several highly efficient solution methods for the Quadratic Knapsack Problem (QKP) have been documented. However, these solution approaches are not readily available for industrial applications. In this short paper, we demonstrate that OR practitioners must be careful in their use of general-purpose integer programming software such as Gurobi when solving QKPs. We verify the very positive impact of fine-tuning parameters when solving QKPs with Gurobi.


Keywords


quadratic knapsack problem; general-purpose integer programming software; Gurobi; parameter fine tuning; operations research practitioners

Full Text:

PDF


References


1. Witzgall, C.: Mathematical methods of site selection for electronic message system (ems). Technical Report, NBS Internal Report, 1975.

2. Johnson, E., Mehrotra, A., Nemhauser, G.: Min-cut clustering. 1993. Math. Program. 1993, 62, 133–151.

3. Rhys, J.: A selection problem of shared fixed costs and network flows. 1970, Manag. Sci. 17, 200–207.

4. Quan, N., Harrison, K. M., A tight upper bound for quadratic knapsack problems in grid-based wind farm layout optimization. Eng. Optim. 2024, 50,3, 367-381.

5. Caprara, A., Pisinger, D., Toth, P. Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 1998, 11: 125–137.

6. Gallo, G., Hammer, P.L., Simeone, B. Quadratic knapsack problems, Math. Program. Stud. 1980, 12: 132–149.

7. Pisinger, D. The quadratic knapsack problem — a survey. Discrete Appl. Math. 2007, 155: 623–648.

8. Cacchiani, V., Lori, M., Locvatelli, A., Martello, S. Knapsack problems-an overview of recent advances. Part II: multiple, multidimensional, and quadratic knapsack problems. Computers & Operations Research. 2022, 143. 105693.

9. Billionnet, A., Soutif, E. An exact method based on Lagrangian decomposition for the 0–1 quadratic knapsack problem. European J. Oper. Res. 2004, 157: 565–575.

10. Pisinger, D., Rasmussen, A.B., Sandvik. R. Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J. Comput. 2007, 19: 280–290.

11. Cunha, J.O., Simonetti, L., Lucena, A. Lagrangian heuristics for the Quadratic Knapsack Problem. Comput Optim Appl. 2016, 63: 97-120. https://doi.org/10.1007/s10589-015-9763-3.

12. Fomeni, F.D., Kaparis, K., Letchford, A.N. A cut-and-branch algorithm for the Quadratic Knapsack Problem. Discrete Optimization. 2022, 44: 1-18. https://doi.org/10.1016/j.dispot.2020.100579.

13. Fomeni. F.D. A lifted-space dynamic programming algorithm for the Quadratic Knapsack Problem. Discrete Applied Mathematics. 2023, 335: 52-68. https://doi.org/10.1016/j.dam.2023./02.003.

14. Fampa, M., Lubke, D., Wang, F., Wolkowicz, H., 2020. Parametric convex quadratic relaxation of the quadratic knapsack problem. Eur. J. Oper. Res. 281, 36–49.

15. Wu, Z., Jiang, B., Karimi, H.R., 2020. A logarithmic descent direction algorithm for the quadratic knapsack problem. Appl. Math. Comput. 369, 124854. Xie, X.F., Liu, J., 2007.

16. Song, M. S., Lin, P. H., Lu, Y., Shively-ertas, E., Vasko, F. J. 2024 A practical approach for dealing with hard knapsack problems using general-purpose integer programming software, Intl. Trans. In Op. Res. 1-22. https://doi.org/10.1111/itor.13449

17. Lu, Y., McNally, B., Shively-Ertas, E., Vasko, F. J. 2021."A Simple and Efficient Technique to Generate Bounded Solutions for the Multidimensional Knapsack Problem: a Guide for OR Practitioners", International Journal of Circuits, Systems and Signal Processing. https://doi.org/10.46300/9106.2021.15.178

18. https://support.gurobi.com/hc/en-us/articles/8265539575953-What-is-the-MIPGap.

19. Vasko, F.J., Lu, Y., Song, M.S. Solving hard combinatorial optimization problems with general purpose integer programming software: a guide for OR practitioners. Inside OR. 2023, 627: 13.

20. https://www.gurobi.com/documentation/current/refman/parameter_tuning_tool.html

21. https://www.gurobi.com/documentation/current/refman/parameters.html




DOI: https://doi.org/10.24294/pnmai8052

Refbacks

  • There are currently no refbacks.


License URL: https://creativecommons.org/licenses/by/4.0/

This site is licensed under a Creative Commons Attribution 4.0 International License.