Efficiently Generating Bounded Solutions for Very Large Multiple Knapsack Assignment Problems
DOI:
https://doi.org/10.47852/bonviewJCCE3202921Keywords:
multiple knapsack assignment problem, Gurobi integer programming software, simple sequential increasing tolerance methodology, initial feasible solutionAbstract
The Multiple Knapsack Assignment Problem (MKAP) is an interesting generalization of the Multiple Knapsack Problem which has logistical applications in transportation and shipping. In addition to trying to insert items into knapsacks in order to maximize the profit of the items in the knapsacks, the MKAP partitions the items into classes and only items from the same class can be inserted into a knapsack. In the literature, the Gurobi integer programming software has solved MKAPs with up to 1240 variables and 120 constraints in at most 20 minutes on a standard PC. In this article, using a standard PC and iteratively loosening the acceptable tolerance gap for 180 MKAPs with up to 20,100 variables and 1,120 constraints, we show that Gurobi can, on average, generate solutions that are guaranteed to be at most 0.17% from the optimums in 43 seconds. However, for very large MKAPs (over a million variables), Gurobi’s performance can be significantly improved when an initial feasible solution is provided. Specifically, using from the literature, a heuristic and 42 MKAP instances with over 6 million variables and nearly 90,000 constraints, Gurobi generated solutions guaranteed to be, on average, within 0.21% of the optimums in 10 minutes. This is a 99% reduction in the final solution bound (gap between the best Gurobi solution and the best upper bound) compared to the approach without initial solution inputs. Hence, a major objective of this article is to demonstrate for what size MKAP instances providing Gurobi with an initial heuristic solution significantly improves performance in terms of both execution time and solution quality.
Received: 3 April 2023 | Revised: 8 June 2023 | Accepted: 12 June 2023
Conflicts of Interest
The authors declare that they have no conflicts of interest to this work.
Data Availability Statement
Data sharing is not applicable to this article as no new data were created or analyzed in this study.
Metrics
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Authors
This work is licensed under a Creative Commons Attribution 4.0 International License.