New Classes of Facets for Complementarity Knapsack Problems
Alberto Del Pia  1, 2@  , Jeff Linderoth  1@  , Haoran Zhu  3, *@  
1 : University of Wisconsin Madison
2 : Wisconsin Institute for Discovery
3 : University of Wisconsin Madison
* : Corresponding author

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.


Online user: 1 Privacy
Loading...