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

Matthew R. Gibson; Jeffrey W. Ohlmann; Michael J. Fry

doi:10.1016/j.cor.2009.02.028

Back

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

Journal article

Peer reviewed

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

Matthew R. Gibson, Jeffrey W. Ohlmann and Michael J. Fry

Computers & operations research, Vol.37(3), pp.598-609

03/01/2010

DOI: 10.1016/j.cor.2009.02.028

View Online

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.

Agent-based simulation

Beam search

Discrete stochastic optimization

Knapsack problem

Sequential allocation

Stochastic ruler

Details

Title: Subtitle: An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition
Creators: Matthew R. Gibson - Department of Computer Science, University of Iowa, 14 MacLean Hall, Iowa City, IA 52242-1419, USA
Jeffrey W. Ohlmann - University of Iowa
Michael J. Fry - University of Cincinnati
Resource Type: Journal article
Publication Details: Computers & operations research, Vol.37(3), pp.598-609
Publisher: Elsevier Ltd
DOI: 10.1016/j.cor.2009.02.028
ISSN: 0305-0548
eISSN: 1873-765X
Language: English
Date published: 03/01/2010
Academic Unit: Business Analytics
Record Identifier: 9984380487602771

Metrics

1 Record Views

14 Times Cited - Web of Science