facets; nonlinear knapsack problem; flexible manufacturing system
Abstract :
[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.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Crama, Yves ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Mazzola, Joseph B.
Language :
English
Title :
Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and FMS part-selection problems
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Balas E. (1975) Facets of the knapsack polytope. Math. Progr. 8:146-164.
Berge C. Hypergraphs, North-Holland, Amsterdam; 1989.
Boonyasombat V. (1984) Degree sequences of connected hypergraphs and hypertrees. Graph Theory Singapore 1983 , K.M., Koh, H.P., Yap, Springer, Berlin; 236-247.
Boyd E.A. (1993) Polyhedral results for the precedence-constrained knapsack problem. Discr. Appl. Math. 41:185-201.
Chaillou P., Hansen P., Mahieu Y. (1989) Best network flow bounds for the quadratic knapsack problem. Combinatorial Optimization , B., Simeone, Springer, Berlin; 225-235.
Crama Y., Oerlemans A.G. (1994) A column generation approach to job grouping for flexible manufacturing systems. Euro. J. Oper. Res. 78:58-80.
Crowder H., Johnson E.L., Padberg M.W. (1983) Solving large-scale zero-one linear programming problems. Oper. Res. 31:803-834.
Dietrich B.L., Lee J., Lee Y.S. (1993) Order selection on a single machine with high set-up costs. Ann. Oper. Res. 43:379-396.
Dijkhuizen G., Faigle U. (1993) A cutting-plane approach to the edge-weighted maximal clique problem. Euro. J. Oper. Res. 69:121-130.
Gallo G., Grigoriadis M.D., Tarjan R.E. (1989) A fast parametric maximum flow algorithm and applications. SIAM J. Comp. 18:30-55.
Gallo G., Hammer P.L., Simeone B. (1980) Quadratic knapsack problems. Math. Progr. Study 12:132-149.
Gallo G., Simeone B. (1989) On the supermodular knapsack problem. Math. Progr. 45:295-309.
Geoffrion A.M. (1974) Lagrangean relaxation for integer programming. Math. Progr. Study 2:82-114.
Guignard M., Kim S. (1987) Lagrangian decomposition for integer programming: Theory and applications. R.A.I.R.O. Recherche Opérationnelle/Operations Research 21:307-323.
Hammer P.L., Johnson E.L., Peled U.N. (1975) Facets of regular 0–1 polytopes. Math. Progr. 8:179-206.
Hirabayashi R., Suzuki H., Tsuchiya N. (1984) Optimal tool module design problem for NC machine tools. J. Oper. Res. Soc. Japan 27:205-228.
Hwang S. (1986) A constraint-directed method to solve the part selection problem in flexible manufacturing systems planning stage. Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems , K.E., Stecke, R., Suri, Elsevier, Amsterdam; 297-309.
Hwang S.S., Shogan A.W. (1989) Modelling and solving an FMS part selection problem. International Journal of Production Research 27:1349-1366.
Johnson D., Niemi K. (1983) On knapsacks, partitions, and a new dynamic programming technique. Math. Oper. Res. 8:1-14.
Johnson E.L., Mehrotra A., Nemhauser G.L. (1993) Min-cut clustering. Math. Progr. 62:133-151.
Lawler E.L. Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York; 1976.
Lengauer T. Combinatorial Algorithms for Integrated Circuit Layout, Wiley, Chichester; 1990.
Mamer J.W., Shogan A.W. (1987) A constrained capital budgeting problem with applications to repair kit selection. Manag. Sci. 33:800-806.
Nemhauser G.L., Wolsey L.A. Integer and Combinatorial Optimization, Wiley, New York; 1988.
Nemhauser G.L., Trotter L.T. (1974) Properties of vertex packing and independence system polyhedra. Math. Progr. 6:48-61.
Padberg M.W. (1975) A note on zero-one programming. Operations Research 23:833-837.
Padberg M.W. (1979) Covering, packing, and knapsack problems. Ann. Discr. Math. 4:265-287.
Picard J.-C., Queyranne M. (1982) A network flow solution to some nonlinear 0–1 programming problems, with applications to graph theory. Networks 12:141-159.
Rajagopalan S. Scheduling problems in flexible manufacturing systems, Working Paper, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA; 1985.
Rajagopalan S. (1986) Formulation and heuristic solutions for parts grouping and tool loading in flexible manufacturing systems. Proc. 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems , K.E., Stecke, R., Suri, Elsevier, Amsterdam; 311-320.
Rhys J.M.W. (1970) A selection problem of shared fixed costs and network flows. Management Science 17:200-207.
Schrijver A. Theory of Linear and Integer Programming, Wiley, Chichester; 1986.
Stecke K.E. (1983) Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems. Manag. Sci. 29:273-288.
Weingartner H.M. (1966) Capital budgeting of interrelated projects: Survey and synthesis. Management Science 12:485-516.
Wolsey L. (1975) Faces for a linear inequality in 0–1 variables. Math. Progr. 8:165-178.
Zemel E. (1989) Easily computable facets of the knapsack polytope. Mathematics of Operations Research 14:760-764.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.