TL;DR
This paper introduces a novel algorithm, Iterative Pseudo-Gap Enumeration (IPGE), to tackle the complex Multidimensional Multiple-choice Knapsack Problem (MMKP). IPGE leverages a new concept called "pseudo-gap" to derive effective cuts that prune the search space, leading to improved lower bounds and competitive performance compared to existing state-of-the-art methods.
What Problem Does This Paper Address?
The Multidimensional Multiple-choice Knapsack Problem (MMKP) is a challenging NP-hard combinatorial optimization problem with applications in areas like logistics and resource management. The core difficulty lies in selecting exactly one item from each of several groups, subject to multiple resource constraints, while maximizing total profit. Existing methods often struggle with large-scale instances, either by being too slow to find optimal solutions or by not achieving high-quality solutions. This paper aims to improve the efficiency and solution quality for MMKPs by developing a more effective enumeration strategy.
Methods
The proposed IPGE algorithm is an iterative approach that combines Linear Programming (LP) relaxation with a novel "pseudo-gap" concept. Here's a breakdown of the key techniques:
- Pseudo-Gap: This is a hypothesized gap between the upper and lower bounds of the problem. It's used to derive new constraints.
- Pseudo-Cuts: Based on the pseudo-gap and reduced cost constraints of non-basic variables, the authors derive a family of "pseudo-cuts." These cuts help to constrain variables across different groups, effectively strengthening the problem.
- Iterative Enumeration: The algorithm iteratively enumerates values for the pseudo-gap. This process refines the search space and guides the algorithm towards better solutions.
- Strengthened Problem Solving: In each iteration, the original MMKP is "strengthened" with the derived pseudo-cuts and then solved using an ILP solver (CPLEX).
- Cross Group Cuts (CGCs): These are a generalization of existing fixing rules, designed to restrict variables from different groups simultaneously.
- Iteration Cut: An additional cut is introduced to avoid revisiting previously explored solution spaces in subsequent iterations.
Datasets
The authors evaluated their IPGE approach on 37 benchmark instances for the MMKP. These instances are divided into two sets:
- 27 Regular Structure Instances: These instances have a consistent number of items within each group.
- 10 Irregular Structure Instances: These instances feature varying group sizes.
The paper references existing literature for the generation of these benchmarks and provides details on their characteristics (number of groups, group sizes, resource dimensions) in Tables 1 and 2.
Key Insights and Ideas
- The "Pseudo-Gap" as a Powerful Tool: The introduction of the pseudo-gap concept is central. It provides a flexible mechanism to derive informative cuts that effectively prune the search space, a common challenge in combinatorial optimization.
- Cross-Group Constraints are Crucial: The derived Cross Group Cuts (CGCs) are a significant contribution, as they leverage information across different item groups to impose tighter restrictions than traditional single-group constraints.
- Iterative Refinement for Better Bounds: The iterative nature of IPGE, where the pseudo-gap is adjusted, allows for a systematic exploration of the solution space, leading to the discovery of improved lower bounds.
- Complementarity of Approaches: The experimental results suggest that IPGE, while competitive, might also be complementary to other methods like "reduce and solve," indicating that a combination of strategies could be even more powerful.
Key Results
- Improved Lower Bounds: IPGE discovered 10 new lower bounds on the 37 benchmark instances, with 6 on regular instances and 4 on irregular instances, often surpassing previously reported high lower bounds.
- Competitive Performance: When directly compared on the same hardware and with the same ILP solver, IPGE outperformed the state-of-the-art "reduce and solve" approach (PEGF and PERC) on 18 out of 37 instances.
- Solution Quality: IPGE achieved 18 higher lower bounds than PEGF and PERC combined.
- Efficiency: For several instances, IPGE terminated well before the 1-hour time limit, indicating efficient convergence.
Limitations and Future Work
- Enumeration Strategy: The authors acknowledge that their current pseudo-gap enumeration strategy is simple. They suggest that more intelligent strategies, potentially considering the distribution of reduced costs, could further enhance performance, especially for challenging instances like INST23 where IPGE experienced a plateau.
- Iteration Cut Looseness: The "iteration cut" is noted as being "loose." Future work could explore more effective heuristic or exact cuts to further prune the search space and eliminate visited regions more efficiently.
- Pseudo-Cut Effectiveness: The relationship between the effectiveness of different pseudo-cuts and specific problem instance features remains an area for further research. Understanding which cuts work best under what circumstances could lead to more tailored and efficient algorithms.
Summary updated