An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition

Authored by Matthew R. Gibson, Jeffrey W. Ohlmann, Michael J. Fry

Date Published: 2010-03

DOI: 10.1016/j.cor.2009.02.028

Sponsors: No sponsors listed

Platforms: No platforms listed

Model Documentation: Other Narrative Pseudocode Mathematical description

Model Code URLs: Model code not found

Abstract

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. (C) 2009 Elsevier Ltd. All rights reserved.

Tags

agent-based simulation Beam search Discrete stochastic optimization Knapsack problem Sequential allocation Stochastic ruler