New Classes of Facets for Complementarity Knapsack Problems

Alberto Del Pia, Jeff T. Linderoth, Haoran ZhuISCO 2022 · OpenReview

TL;DR

This paper introduces novel mathematical inequalities (cutting-planes) to better model and solve a complex optimization problem called the Complementarity Knapsack Problem (CKP). The authors also prove that a key computational challenge in solving CKP, known as separation, is indeed NP-complete, and they provide efficient algorithms to tackle it.

What Problem Does This Paper Address?

The Complementarity Knapsack Problem (CKP) is a variation of the classic knapsack problem. In a standard knapsack problem, you want to maximize the value of items you put in a knapsack without exceeding its weight capacity. CKP adds a twist: for certain groups of items, you can only pick at most one item from each group to be "active" (i.e., have a positive value). This "complementarity constraint" makes the problem significantly harder to solve.

Existing methods for solving CKP often involve complex mathematical formulations and algorithms. A crucial part of these algorithms is finding "cutting-planes" – inequalities that help to tighten the mathematical model and guide the solver towards the optimal solution. While previous work by de Farias et al. introduced some of these cutting-planes, this paper aims to:

  1. Discover new families of cutting-planes: The authors propose three new types of inequalities that are derived from a combinatorial concept called a "pack." These new inequalities are fundamentally different from previous ones and are shown to be "facet-defining," meaning they are crucial for defining the boundaries of the feasible solution space.
  2. Address separation complexity: For many optimization problems, determining if a given solution violates a cutting-plane (the "separation problem") is computationally very difficult (NP-complete). De Farias et al. conjectured that this was true for their CKP inequalities. This paper proves that conjecture and also shows it's NP-complete for their newly proposed inequalities.
  3. Develop efficient algorithms: To make these new cutting-planes practical, the paper provides algorithms to find them efficiently, especially when the problem size is manageable.

Methods

The core of this paper lies in polyhedral combinatorics and integer programming.

  • New Cutting-Planes: The authors introduce a new combinatorial concept called a "pack," which is related to but distinct from the "cover" concept used in prior work. They then use packs to derive three new families of inequalities. The key is that these inequalities are derived from the structure of the problem itself, not just general-purpose techniques. They also provide conditions under which these inequalities are "facet-defining," meaning they are essential for defining the boundary of the feasible region of the problem.
  • Separation Complexity: To prove that the separation problem is NP-complete, the authors use reductions from known NP-complete problems (specifically, the partition problem). This involves constructing an instance of CKP from an instance of the partition problem such that a solution to the CKP separation problem implies a solution to the partition problem.
  • Exact Separation Algorithms: The paper proposes algorithms to find separating inequalities. These algorithms are designed to be efficient, particularly when the number of "complementarity groups" (represented by $|M|$) is small. They leverage the properties of packs and maximal switching packs to systematically search for violated inequalities.

Datasets

Not discussed in the paper. The paper focuses on theoretical contributions and algorithmic development for a general problem formulation, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The "Pack" Concept is Powerful: Introducing the "pack" as a combinatorial object, complementary to "covers," opens up new avenues for generating strong valid inequalities for CKP. This highlights how novel combinatorial structures can lead to better mathematical formulations.
  • New Inequalities are Fundamentally Different: The paper emphasizes that the proposed "complementarity pack inequalities" cannot be easily derived through standard "lifting" procedures applied to existing inequalities. This suggests they capture a unique aspect of the CKP structure.
  • Separation is Indeed Hard: The paper confirms the conjecture that separating certain CKP inequalities is NP-complete. This is an important theoretical result that informs the complexity of solving CKP and the design of algorithms.
  • Efficient Algorithms Exist (Under Conditions): Despite the NP-completeness of separation, the paper demonstrates that efficient algorithms can be developed, especially when certain problem parameters (like the number of complementarity groups) are small. This is crucial for practical applications.

Key Results

  • Three New Families of Facet-Defining Inequalities: The paper introduces and proves the validity and facet-defining properties of three new families of cutting-planes for the Complementarity Knapsack Polytope.
  • NP-Completeness of Separation Proven: The paper proves that the separation problem for two families of inequalities from prior work (de Farias et al. [8]) and for the newly proposed inequalities is NP-complete.
  • Polynomial-Time Separation Algorithms: For the first family of complementarity pack inequalities, an exact separation algorithm is presented that runs in polynomial time if the number of complementarity groups $|M|$ is logarithmic in the input size of the CKP. Similar algorithms are outlined for the other two families.

Limitations and Future Work

  • Separation Complexity for Other Families: While algorithms are provided for the first family of inequalities, the separation complexity for the second and third families of complementarity pack inequalities is conjectured to be NP-complete, but not formally proven in this paper.
  • Heuristic Separation Algorithms: The paper suggests that developing more efficient heuristic separation algorithms would be a valuable direction for future work, especially for larger problem instances where exact algorithms might be too slow.
  • Numerical Studies: The authors mention the need for extensive numerical studies to evaluate the practical performance of the proposed inequalities and separation algorithms.
  • General Graph Structures: The paper poses an interesting open question about understanding valid inequalities for a more general set related to complementarity constraints on arbitrary graphs, which could lead to broader theoretical insights.

Summary updated

Abstract

The complementarity knapsack problem (CKP) is a knapsack problem with real-valued variables and complementarity conditions between pairs of its variables. We extend the polyhedral studies of De Farias et al. for CKP, by proposing three new families of cutting-planes that are all obtained from a combinatorial concept known as a pack. Sufficient conditions for these inequalities to be facet-defining, based on the concept of a maximal switching pack, are also provided. Moreover, we answer positively a conjecture by De Farias et al. about the separation complexity of the inequalities introduced in their work.
BibTeX
@inproceedings{pia2022new,
  author = {Alberto Del Pia and Jeff T. Linderoth and Haoran Zhu},
  title = {{New Classes of Facets for Complementarity Knapsack Problems}},
  booktitle = {ISCO},
  year = {2022},
  url = {https://openreview.net/forum?id=O_pCUK14OO},
}
Figure