Convexity and Solutions of Stochastic Multidimensional 0-1 Knapsack Problems with Probabilistic Constraints

References

• Beasley JE (1990) OR-library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11):1069–1072.Crossref, Google Scholar
• Bellman RE, Dreyfus SE (1962) Applied Dynamic Programming (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Black F, Scholes M (1973) The pricing of options and corporate liabilities. J. Political Econom. 637–654.Crossref, Google Scholar
• Bonami P, Kilinç M, Linderoth J (2012) Algorithms and software for convex mixed integer nonlinear programs. Mixed Integer Nonlinear Programming (Springer, New York), 1–39.Crossref, Google Scholar
• Bortfeldt A, Wäscher G (2013) Constraints in container loading—A state-of-the-art review. Eur. J. Oper. Res. 229(1):1–20.Crossref, Google Scholar
• Byrd RH, Nocedal J, Waltz RA (2006) KNITRO: An integrated package for nonlinear optimization. Large-Scale Nonlinear Optimization (Springer, New York), 35–59.Crossref, Google Scholar
• CPLEX, IBM ILOG (2009) User’s Manual for CPLEX (International Business Machines Corporation).Google Scholar
• Cramton P, Shoham Y, Steinberg R (2006) Combinatorial Auctions (MIT Press, Cambridge, MA).Google Scholar
• Czyzyk J, Mesnier MP, Moré JJ (1998) The NEOS server. Comput. Sci. Engrg. IEEE 5(3):68–75.Crossref, Google Scholar
• Dolan ED (2001) The NEOS server 4.0 administrative guide. Technical Memorandum ANL/MCS-TM-250, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.Google Scholar
• Esary JD, Proschan F, Walkup DW (1967) Association of random variables, with applications. Ann. Math. Statist. 38(5):1466–1474.Crossref, Google Scholar
• Fortz B, Poss M (2010) Easy distributions for combinatorial optimization problems with probabilistic constraints. Oper. Res. Lett. 38(6):545–549.Crossref, Google Scholar
• Fortz B, Labbé M, Louveaux F, Poss M (2013) Stochastic binary problems with simple penalties for capacity constraints violations. Math. Programming 138(1–3):199–221.Crossref, Google Scholar
• Fréville A (2004) The multidimensional 0-1 knapsack problem: An overview. Eur. J. Oper. Res. 155(1):1–21.Crossref, Google Scholar
• Fréville A, Hanafi S (2005) The multidimensional 0-1 knapsack problem—Bounds and computational aspects. Ann. Oper. Res. 139(1):195–227.Crossref, Google Scholar
• Gavish B, Pirkul H (1982) Allocation of databases and processors in a distributed computing system. Akoka J, ed. Management of Distributed Data Processing (North-Holland, Amsterdam), 215–231.Google Scholar
• Gill PE, Murray W, Saunders MA (2002) SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM J. Optim. 12(4):979–1006.Crossref, Google Scholar
• Gilmore PC, Gomory RE (1966) The theory and computation of knapsack functions. Oper. Res. 14(6):1045–1074.Link, Google Scholar
• Goyal V, Ravi R (2010) A PTAS for the chance-constrained knapsack problem with random item sizes. Oper. Res. Lett. 38(3):161–164.Crossref, Google Scholar
• Gropp W, Moré JJ (1997) Optimization environments and the NEOS server. Approximation Theory Optim. 167–182.Google Scholar
• Grossmann IE (2002) Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Engrg. 3(3):227–252.Crossref, Google Scholar
• Grossmann IE, Viswanathan J, Vecchietti A, Raman R, Kalvelagen E (2001) DICOPT (Engineering Research Design Center, Carnegie Mellon University, Pittsburgh, PA and GAMS Development Coporation, Washington DC), Available in http://www.gams.com.Google Scholar
• Henrion R, Strugarek C (2008) Convexity of chance constraints with independent random variables. Comput. Optim. Appl. 41(2):263–276.Crossref, Google Scholar
• Kataoka S (1963) A stochastic programming model. Econometrica: J. Econometric Soc. 31(1–2):181–196.Crossref, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer, Berlin).Crossref, Google Scholar
• Korte BH, Vygen J (2012) Combinatorial Optimization: Theory and Algorithms (Springer, Berlin).Crossref, Google Scholar
• Lorie JH, Savage LJ (1955) Three problems in rationing capital. J. Bus. 28(4):229–239.Crossref, Google Scholar
• Mádi-Nagy G, Prékopa A (2004) On multivariate discrete moment problems and their applications to bounding expectations and probabilities. Math. Oper. Res. 29(2):229–258.Link, Google Scholar
• Petersen CC (1967) Computational experience with variants of the Balas algorithm applied to the selection of R&D projects. Management Sci. 13(9):736–750.Link, Google Scholar
• Prékopa A (1974) Programming under probabilistic constraints with a random technology matrix. Mathematische Operationsforschung und Statistik 5(2):109–116.Crossref, Google Scholar
• Prékopa A (1995) Stochastic Programming (Kluwer Academic Publishers, Dordrecht, Netherlands).Crossref, Google Scholar
• Prékopa A (1999) The use of discrete moment bounds in probabilistic constrained stochastic programming models. Ann. Oper. Res. 85(0):21–38.Crossref, Google Scholar
• Prékopa A (2007) Conditional mean-conditional variance portfolio selection model. RUTCOR Research Report 34-2007, Rutgers Center for Operations Research, Piscataway, NJ).Google Scholar
• Prékopa A, Szántai T (1978) A new multivariate gamma distribution and its fitting to empirical streamflow data. Water Resources Res. 14(1):19–24.Crossref, Google Scholar
• Rosenthal RE (1988) GAMS—A User’s Guide (GAMS Development Corporation, Washington DC), Available in http://www.gams.com.Google Scholar
• Rothkopf MH, Pekeč A, Harstad RM (1998) Computationally manageable combinational auctions. Management Sci. 44(8):1131–1147.Link, Google Scholar
• Singh MR, Abraham CT, Akella R (1990) A wafer design problem in semiconductor manufacturing for reliable customer service. Components, Hybrids, and Manufacturing Technol., IEEE Trans. 13(1):103–108.Crossref, Google Scholar
• van de Panne C, Popp W (1963) Minimum-cost cattle feed under probabilistic protein constraints. Management Sci. 9(3):405–430.Link, Google Scholar
• van Noortwijk JM (2009) A survey of the application of gamma processes in maintenance. Reliability Engrg. System Safety 94(1):2–21.Crossref, Google Scholar
• Vasquez M, Hao J-K (2001) A “logic-constrained” knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite. Computation Optim. Appl. 20(2):137–157.Crossref, Google Scholar
• Weingartner HM (1966) Capital budgeting of interrelated projects: Survey and synthesis. Management Sci. 12(7):485–516.Link, Google Scholar
• Wilbaut C, Hanafi S, Salhi S (2008) A survey of effective heuristics and their application to a variety of knapsack problems. IMA J. Management Math. 19(3):227–244.Crossref, Google Scholar
• Zymler S, Kuhn D, Rustem B (2013) Distributionally robust joint chance constraints with second-order moment information. Math. Programming 137(1–3):167–198.Crossref, Google Scholar