Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems

This paper defines the dense subhypergraph problem (DSP), which provides a modelling framework for the nonlinear knapsack problem and other well-known problems arising in areas such as capital budgeting, flexible manufacturing system production planning, repair-kit selection, and compiler construction. The authors define several families of valid inequalities and state conditions under which these inequalities are facet-defining for DSP. They also explore the polyhedral structure of the cardinality-constrained DSP. Finally, the authors examine a special case of this problem that arises, for example, within the context of Lagrangian decomposition. For this case, they present a complete description of the convex hull of the feasible region.