×

An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition. (English) Zbl 1173.90489

Summary: We examine a situation in which a decision-maker executes a sequence of resource allocation decisions over time, but the availability of the indivisible resources at future epochs is uncertain due to actions of competitors. We cast this problem as a specialized type of stochastic knapsack problem in which the uncertainty of item (resource) availability is induced by competitors concurrently filling their own respective knapsacks. Utilizing a multi-period bounded multiple-choice knapsack framework, we introduce a general discrete stochastic optimization model that allows a nonlinear objective function, cardinality constraints, and a knapsack capacity constraint. Utilizing a set of greedy selection rules and agent-based modeling to simulate the competitors’ actions, we solve the problem with a stochastic ruler approach that incorporates beam search to determine item selection of the types specified by the solution representation. We illustrate the computational effectiveness of our approach on instances motivated by a sports league draft as well as generic problem instances based on the knapsack literature.

MSC:

90C15 Stochastic programming
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alrefaei, M. H.; Andradottir, S., A modification of the stochastic ruler method for discrete stochastic optimization, European Journal of Operational Research, 133, 160-182 (2001) · Zbl 1006.90058
[2] Alrefaei, M. H.; Andradottir, S., Discrete stochastic optimization using variants of the stochastic ruler method, Naval Research Logistics, 52, 4, 344-360 (2005) · Zbl 1090.90148
[3] Axelrod, R., The complexity of cooperation: agent-based models of competition and collaboration (1997), Princeton University Press: Princeton University Press Princeton, NJ
[4] Brams, S. J.; Straffin, P. D., Prisoners’ dilemma and professional sports drafts, The American Mathematical Monthly, 86, 2, 80-88 (1979) · Zbl 0399.90120
[5] Brams SJ. Mathematics and democracy: designing better voting and fair-division procedures. Mathematical and Computer Modelling; 2008.; Brams SJ. Mathematics and democracy: designing better voting and fair-division procedures. Mathematical and Computer Modelling; 2008. · Zbl 1151.91001
[6] Brams, S. J.; Kaplan, T. R., Dividing the indivisible: procedures for allocating cabinet ministries to political parties in a parliamentary system, Journal of Theoretical Politics, 16, 2, 143 (2004)
[7] Carraway, R. L.; Schmidt, R. L.; Weatherford, L. R., An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns, Naval Research Logistics, 40, 2, 161-173 (1993) · Zbl 0793.90042
[8] Chen X, Makio J, Weinhardt C. Agent-based simulation on competition of e-auction marketplaces. In: International conference on computational intelligence for modelling, control and automation; 2005. International conference on intelligent agents, web technologies and internet commerce, vol. 2; 2005.; Chen X, Makio J, Weinhardt C. Agent-based simulation on competition of e-auction marketplaces. In: International conference on computational intelligence for modelling, control and automation; 2005. International conference on intelligent agents, web technologies and internet commerce, vol. 2; 2005.
[9] Chiu, S. Y.; Lu, L.; Cox, L. A., Optimal access control for broadband services: stochastic knapsack with advance information, European Journal of Operational Research, 89, 1, 127-134 (1996) · Zbl 0908.90124
[10] Dobson, G., Worst-case analysis of greedy heuristics for integer programming with nonnegative data, Mathematics of Operations Research, 7, 4, 515-531 (1982) · Zbl 0498.90061
[11] Erel, E.; Sabuncuoğlu, İ.; Sekerci, H., Stochastic assembly line balancing using beam search, International Journal of Production Research, 43, 7, 1411-1426 (2005) · Zbl 1068.90045
[12] Fréville, A., The multidimensional 0-1 knapsack problem: an overview, European Journal of Operational Research, 155, 1, 1-21 (2004) · Zbl 1045.90050
[13] Fry, M. J.; Lundberg, A. W.; Ohlmann, J. W., A player selection heuristic for a sports league draft, Journal of Quantitative Analysis in Sports, 3, 2 (2007)
[14] Fudenberg, D.; Tirole, J., Game theory (1991), MIT Press: MIT Press Cambridge, MA · Zbl 1339.91001
[15] Henig, M. I., Risk criteria in a stochastic knapsack problem, Operations Research, 38, 5, 820-825 (1990)
[16] Heyman, D. P.; Sobel, M. J., Stochastic models in operations research, vol. II: stochastic optimization (1984), McGraw-Hill: McGraw-Hill New York · Zbl 0531.90062
[17] Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Springer: Springer Berlin · Zbl 1103.90003
[18] Kleywegt, A. J.; Papastavrou, J. D., The dynamic and stochastic knapsack problem with random sized items, Operations Research, 49, 1, 26-41 (2001) · Zbl 1163.90714
[19] Lewis, M., Moneyball (2004), W.W. Norton & Company
[20] Martello, S.; Toth, P., Knapsack problems: algorithms and computer implementations (1990), Wiley: Wiley New York, NY, USA · Zbl 0708.68002
[21] Montgomery, D. C., Design and analysis of experiments (2001), Wiley: Wiley New York
[22] Morton, D. P.; Wood, R. K., On a stochastic knapsack problem and generalizations, (Advances in computational and stochastic optimization, logic programming, and heuristic search: interfaces in computer science and operations research (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht), 149-169 · Zbl 0893.90138
[23] Pisinger, D., Budgeting with bounded multiple-choice constraints, European Journal of Operational Research, 129, 3, 471-480 (2001) · Zbl 1116.90381
[24] Puterman, M. L., Markov decision processes (1994), Wiley · Zbl 0336.93047
[25] Rinnooy Kan, A. H.G.; Stougie, L.; Vercellis, C., A class of generalized greedy algorithms for the multi-knapsack problem, Discrete Applied Mathematics, 42, 2-3, 279-290 (1993) · Zbl 0785.90072
[26] Ross, K. W.; Tsang, D. H.K., The stochastic knapsack problem, IEEE Transactions on Communications, 37, 7, 740-747 (1989) · Zbl 0675.90066
[27] Sabuncuoğlu, İ.; Bayiz, M., Job shop scheduling with beam search, European Journal of Operational Research, 118, 2, 390-412 (1999) · Zbl 0940.90037
[28] Tergesen A. Estates: divvying up the silver. Business Week; May 29, 2008.; Tergesen A. Estates: divvying up the silver. Business Week; May 29, 2008.
[29] Wallace, A., Sequential resource allocation utilizing agents, International Journal of Production Research, 41, 11, 2481-2499 (2003)
[30] Yan, D.; Mukai, H., Stochastic discrete optimization, SIAM Journal on Control and Optimization, 30, 3, 594-612 (1992) · Zbl 0764.90066
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.