Reference : Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FM...
Scientific journals : Article
Business & economic sciences : Quantitative methods in economics & management
Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
Crama, Yves mailto [Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
Mazzola, Joseph B. []
Annals of Operations Research
Springer Science & Business Media B.V.
Yes (verified by ORBi)
[en] facets ; nonlinear knapsack problem ; flexible manufacturing system
[en] 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. We define several families of valid inequalities and state conditions under which these inequalities are facet-defining for DSP. We also explore the polyhedral structure of the cardinality-constrained DSP. Finally, we examine a special case of this problem that arises, for example, within the context of Lagrangian decomposition. For this case, we present a complete description of the convex hull of the feasible region.

File(s) associated to this reference

Fulltext file(s):

Restricted access
NonlinearKnapsack_Crama_Mazzola.pdfPublisher postprint1.48 MBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.