Title of article
An agent-basedstochasticrulerapproachforastochasticknapsackproblemwith sequential competition
Author/Authors
Matthew R.Gibson، نويسنده , , JeffreyW.Ohlmannb، نويسنده , , MichaelJ.Fryc، نويسنده ,
Issue Information
ماهنامه با شماره پیاپی سال 2010
Pages
12
From page
598
To page
609
Abstract
We examineasituationinwhichadecision-makerexecutesasequenceofresourceallocationdecisions
over time,buttheavailabilityoftheindivisibleresourcesatfutureepochsisuncertainduetoactions
of competitors.Wecastthisproblemasaspecializedtypeofstochasticknapsackprobleminwhichthe
uncertainty ofitem(resource)availabilityisinducedbycompetitorsconcurrentlyfillingtheirownre-
spective knapsacks.Utilizingamulti-periodboundedmultiple-choiceknapsackframework,weintroduce
a generaldiscretestochasticoptimizationmodelthatallowsanonlinearobjectivefunction,cardinality
constraints, andaknapsackcapacityconstraint.Utilizingasetofgreedyselectionrulesandagent-based
modeling tosimulatethecompetitorsʹactions,wesolvetheproblemwithastochasticrulerapproach
that incorporatesbeamsearchtodetermineitemselectionofthetypesspecifiedbythesolutionrep-
resentation. Weillustratethecomputationaleffectivenessofourapproachoninstancesmotivatedbya
sports leaguedraftaswellasgenericprobleminstancesbasedontheknapsackliterature.
Keywords
Sequential allocation , Discrete stochastic optimization , Stochastic ruler , Beam search , Knapsack problem , Agent-based simulation
Journal title
Computers and Operations Research
Serial Year
2010
Journal title
Computers and Operations Research
Record number
927673
Link To Document