New classes of facets for complementarity knapsack problems

DOI10.1007/978-3-031-18530-4_1MaRDI QIDQ6166884zbMATH OpenOpenAlexFDO

Authors Alberto Del Pia, Jeff Linderoth, Haoran Zhu

Publication date 3 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.02873

zbMATH Keywords

branch-and-cutcomplementarity problemcomplementarity knapsack polytopepack inequalities

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

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, and propose efficient separation algorithms for our newly defined cutting-planes.

Recommendations

• New classes of facets for complementarity knapsack problems
• Facets of the Complementarity Knapsack Polytope
• On the complexity of separating cutting planes for the knapsack polytope
• On the facets of the mixed-integer knapsack polyhedron
• On the complexity of separation from the knapsack polytope

Cites work

• (1,k)-configurations and facets for packing problems
• A Branch-and-Cut Algorithm Without Binary Variables for Nonconvex Piecewise Linear Optimization
• A polyhedral study of the semi-continuous knapsack problem
• An algorithm for disjunctive programs
• Branch-and-cut for combinatorial optimisation problems without auxiliary binary variables
• Branch-and-cut for complementarity-constrained optimization
• Branch-and-cut for linear programs with overlapping SOS1 constraints
• Cover and pack inequalities for (mixed) integer programming
• Faces for a linear inequality in 0–1 variables
• Facets of the Complementarity Knapsack Polytope
• Facets of the Knapsack Polytope From Minimal Covers
• Facets of the knapsack polytope
• Knapsack polytopes: a survey
• Lifted Cover Inequalities for 0-1 Integer Programs: Complexity
• Multi-cover inequalities for totally-ordered multiple knapsack sets
• On the \(0/1\) knapsack polytope
• On the complexity of separation from the knapsack polytope
• Reducibility among combinatorial problems
• Sequence independent lifting in mixed integer programming
• Solving Large-Scale Zero-One Linear Programming Problems
• The complexity of cover inequality separation

Cited in

(3)

• New classes of facets for complementarity knapsack problems
• A concise characterization of strong knapsack facets
• Relaxations and cutting planes for linear programs with complementarity constraints

This page was built for publication: New classes of facets for complementarity knapsack problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166884)