STOCHASTIC KNAPSACK PROBLEM: APPLICATION TO TRANSPORTATION PROBLEMS
AUTOR(ES)
Kosuch, Stefanie, Letournel, Marc, Lisser, Abdel
FONTE
Pesqui. Oper.
DATA DE PUBLICAÇÃO
2017-09
RESUMO
ABSTRACT In this paper, we study the stochastic knapsack problem with expectation constraint. We solve the relaxed version of this problem using a stochastic gradient algorithm in order to provide upper bounds for a branch-and-bound framework. Two approaches to estimate the needed gradients are studied, one based on Integration by Parts and one using Finite Differences. The Finite Differences method is a robust and simple approach with efficient results despite the fact that estimated gradients are biased, meanwhile Integration by Parts is based upon more theoretical analysis and permits to enlarge the field of applications. Numerical results on a dataset from the literature as well as a set of randomly generated instances are given.
Documentos Relacionados
- LAGRANGE MULTIPLIERS IN THE PROBABILITY DISTRIBUTIONS ELICITATION PROBLEM: AN APPLICATION TO THE 2013 FIFA CONFEDERATIONS CUP
- The air transportation hub-and-spoke design problem: comparison between a continuous and a discrete solution method
- Contractual solutions to the holdup problem: a survey
- THE PESTICIDE PROBLEM: AN ECONOMIC APPROACH TO PUBLIC POLICY
- Nonextensive statistical mechanics applied to protein folding problem: kinetics aspects