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
http://hdl.handle.net/2268/203414
Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
English
Crama, Yves mailto [Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
Mazzola, Joseph B. []
1995
Annals of Operations Research
Springer Science & Business Media B.V.
58
99-128
Yes (verified by ORBi)
International
0254-5330
1572-9338
[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.
Researchers
http://hdl.handle.net/2268/203414
10.1007/BF02032163

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
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.