- Tytuł:
- Approximating the solution of a dynamic, stochastic multiple knapsack problem
- Autorzy:
-
Hartman, J. C.
Perry, T. C. - Powiązania:
- https://bibliotekanauki.pl/articles/970874.pdf
- Data publikacji:
- 2006
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
programowanie liniowe
dualność
stochastic dynamic programming
approximate dynamic programming
linear programming
duality - Opis:
- We model 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. We model the dynamic, stochastic multiple knapsack problem (DSMKP) 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, we utilize linear programming and duality 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.
- Źródło:
-
Control and Cybernetics; 2006, 35, 3; 535-550
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł