Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation

Alberto Del Pia, Jeff T. Linderoth, Haoran ZhuMath. Program 2023 · OpenReview

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

Abstract

We propose a method to generate cutting-planes from multiple covers of knapsack constraints. The covers may come from different knapsack inequalities if the weights in the inequalities form a totally-ordered set. Thus, we introduce and study the structure of a totally-ordered multiple knapsack set. The valid multi-cover inequalities we derive for its convex hull have a number of interesting properties. First, they generalize the well-known (1, k)-configuration inequalities. Second, they are not aggregation cuts. Third, they cannot be generated as rank-1 Chvátal-Gomory cuts from the inequality system consisting of the knapsack constraints and all their minimal cover inequalities. We also provide conditions under which the inequalities are facets for the convex hull of the totally-ordered knapsack set, as well as conditions for those inequalities to fully characterize its convex hull. We give an integer program to solve the separation and provide numerical experiments that showcase the strength of these new inequalities
BibTeX
@inproceedings{pia2023multi,
  author = {Alberto Del Pia and Jeff T. Linderoth and Haoran Zhu},
  title = {{Multi-cover inequalities for totally-ordered multiple knapsack sets: theory and computation}},
  booktitle = {Math. Program},
  year = {2023},
  url = {https://openreview.net/forum?id=pLGmOAuIdK4},
}
Figure