Approximating the solution of a dynamic, stochastic multiple knapsack problem

Approximating the solution of a dynamic, stochastic multiple knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor20083398
Country: Poland
Volume: 35
Issue: 3
Start Page Number: 535
End Page Number: 550
Publication Date: Jan 2006
Journal: Control and Cybernetics
Authors: ,
Keywords: optimization, programming: probabilistic, inventory: order policies
Abstract:

The model is analysed of an environment where orders arrive probabilistically over time, with their revenues and capacity requirements becoming known upon arrival. The decision is whether to accept an order, receiving a reward and reserving capacity, or reject an order, freeing capacity for possible future arrivals. The dynamic, stochastic multiple knapsack problem is modelled with stochastic dynamic programming (SDP). Multiple knapsacks are used as orders may stay in the system for multiple periods. As the state space grows exponentially in the number of knapsacks and the number of possible orders per period, linear programming and duality are utilised to quickly approximate the end-of-horizon values for the SDP. This helps mitigate end-of-study effects when solving the SDP directly, allowing for the solution of larger problems and leading to increased quality in solutions.

Reviews

Required fields are marked *. Your email address will not be published.