TL;DR
This paper introduces a new class of cutting-planes called "multi-cover inequalities" (MCIs) for a specific type of integer programming problem: the totally-ordered multiple knapsack set. These MCIs offer a significant improvement in tightening the linear programming relaxation compared to existing methods, leading to more efficient solutions for complex optimization problems.
What Problem Does This Paper Address?
The paper tackles the challenge of solving integer programming problems, specifically those involving multiple knapsack constraints. While individual knapsack problems have well-studied polyhedral structures and effective cutting-planes, the intersection of multiple knapsack constraints (a "multiple knapsack set") is much less understood. This lack of understanding makes it difficult to efficiently solve such problems, especially when the constraints have a specific "totally-ordered" structure. The authors aim to develop new cutting-planes that can effectively tighten the linear programming relaxation of these complex problems, thereby improving the performance of standard optimization solvers.
Methods
The core contribution of this paper is the introduction of Multi-cover Inequalities (MCIs). These inequalities are derived by considering multiple "covers" (sets of items that would exceed a knapsack's capacity) from potentially different knapsack constraints within the problem. The key innovation lies in how these covers are combined and analyzed, particularly when the item weights across the knapsack constraints form a totally-ordered sequence.
The authors introduce:
- Totally-Ordered Multiple Knapsack Set (TOMKS): A specific structure of multiple knapsack problems where the weight vectors of the items are component-wise ordered.
- Multi-cover Definition: A family of covers that satisfy a specific comparability condition.
- Algorithm 1 (MCI Generation): A procedure to construct MCIs from a multi-cover.
- Simple-MCI (S-MCI): A specific type of MCI with a closed-form expression.
- Extended MCI (E-MCI): A strengthened version of MCIs.
- Separation Algorithm: A mixed-integer programming (MIP) formulation to find violated MCIs for a given fractional solution.
The paper also provides theoretical conditions under which MCIs are facet-defining for the convex hull of the TOMKS and when they fully characterize it.
Datasets
Not discussed in the paper. The authors generate synthetic instances of the multiple knapsack problem for their numerical experiments.
Key Insights and Ideas
- MCIs Generalize Existing Cuts: The paper shows that MCIs can generalize well-known (1, k)-configuration inequalities and can even be facets of certain knapsack polytopes.
- MCIs are Not Aggregation Cuts: A significant finding is that MCIs are not simply combinations of existing knapsack constraints or their immediate cover inequalities. This suggests they capture unique structural information.
- MCIs are Not Always Rank-1 CG Cuts: The authors demonstrate that MCIs cannot always be generated as rank-1 Chvátal-Gomory cuts from the system of knapsack constraints and their minimal cover inequalities, highlighting their distinct nature.
- TOMKS Structure is Key: The "totally-ordered" property of the knapsack constraints is crucial for the development and effectiveness of MCIs.
- Computational Power: Numerical experiments show that MCIs, especially their lifted versions (L-MCIs), significantly reduce the optimality gap and solve a much larger number of instances to optimality compared to traditional cutting-planes.
Key Results
- Theoretical Characterization: The paper provides conditions for MCIs to be facet-defining and to fully characterize the convex hull of TOMKS.
- Separation MIP: An exact MIP formulation for separating MCIs is presented, enabling their use in branch-and-cut algorithms.
- Numerical Performance:
- Optimality Gap Reduction: L-MCIs closed significantly more optimality gap than LCI counterparts, often reducing gaps from over 3% to near zero.
- Instances Solved to Optimality: L-MCIs solved a substantially higher percentage of instances to optimality (60-80%) compared to other methods. For example, for (30,3) instances, L-MCI solved 6 instances to optimality, while LCI solved only 2.
Limitations and Future Work
- NP-Hardness of Multi-cover Identification: The paper acknowledges that identifying whether a given family of covers is a multi-cover is likely NP-hard, which poses a challenge for general separation.
- Computational Cost of Separation: The exact separation of MCIs relies on solving a complex MIP, which can be computationally expensive for very large problems.
- Focus on TOMKS: The current work is specific to totally-ordered multiple knapsack sets. Extending these ideas to more general multiple knapsack problems would be a valuable future direction.
- Heuristic Separation: The authors encourage research into efficient heuristic separation methods for MCIs to handle larger instances.
- Broader Applications: Exploring the applicability of MCIs to other combinatorial optimization problems beyond knapsack sets is a promising avenue.
Summary updated