Acerca de una versión dinámica del problema de la mochila

Bruno Silva, Luis Miguel Torres

Resumen


El problema de la mochila (Knapsack Problem, KP) es un problema clásico de optimización combinatoria que ha sido ampliamente estudiado por más de un siglo. Es uno de los problemas de programación lineal entera más simples; aparece como subproblema en otros problemas más complejos; y tiene muchas aplicaciones prácticas, en áreas tan diversas como el corte de material, la selección de inversiones de capital y portafolios financieros, la correcta administración de recursos de cómputo, del ancho de banda de una conexión, del espacio de almacenamiento en discos duros, etc. Variantes dinámicas de este problema han sido estudiadas por sus aplicaciones prácticas, aunque no en gran extensión y con pocos resultados obtenidos hasta el presente. La variante considerada en este artículo consiste en agregar una dimensión temporal (discreta) al problema clásico: a cada objeto se le asigna una duración, que indica el intervalo de tiempo que éste debe permanecer dentro de la mochila cada vez que es seleccionado. Se busca maximizar el valor total almacenado en la mochila dentro de un horizonte temporal. Formulamos un modelo de programación lineal entero para este problema y presentamos un algoritmo de solución exacto basado en el esquema branch-and-bound. Adicionalmente, estudiamos su comportamiento y su desempeño computacional.

 

Abstract: The Knapsack Problem (KP) is a classical combinatorial optimization problem that has been widely studied for more than a hundred years (see, for a example [12] and the references there in). It is one of the simplest linear integer programming problems and appears as a subproblem in other more complex problems. It has many practical applications in such diverse areas as cutting-stock [6]; investment selection in capital and financial portfolios [10]; the correct administration of a computer RAM memory, band-width of a connection, disk space [14], etc. Dynamic variants of this problem have been studied for their practical applications, although not in a wide extension and with few results reported up to the present. In this paper we consider a variant which consists in adding a (discrete) temporal dimensión to the classic problem: a duration is assigned to each object indicating the interval of time that it has to remain inside the knapsack whenever it is chosen. The objective is to maximize the total value stored in the knapsack within a certain temporal horizon T. We formulate an integer programming model for this problem and develop an exact solution algorithm based on the branch-and-bound scheme. Furthermore, we report results on its computational behavior and performance.


Citas


T. Achterberg. Scip: Solving constraint integer programs. Mathematical Programming Computation, 1(1):1–41, 2009.http://mp.zib.de/index.php/MPC/artile/view/4.

E. Balas and E. Zemel. An algorithm for large zerooneknapsack problems. Math.Oper. Res., 28(5):1130–1154, 1980.

M. Bartlett, A. Frisch, Y. Hamadi, I.Miguel, S. Tarim,and C. Unsworth. The temporal knapsack problemand its solution. In R. Barták and M. Milano, editors,Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, volume 3524 of Lecture Notes in Computer Science, pages34–48. Springer Berlin / Heidelberg, 2005.

G. Dantzig. Discrete variable extremum problems. Math. Oper. Res., 5(2):266–277, Apr. 1957.

M. R. Garey and D. S. Johnson. Computers and Intractability:A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York, NY, USA, 1979.

P. Gilmore and R. Gomory. A linear programmingapproach to the cutting stock problem. Math. Oper.Res., 9(6):849–859,Nov. 1961.

E. Horowitz and S. Sahni. Computing partitionswith applications to the knapsack problem. J. ACM,21:277–292, April 1974.

R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, The IBM ResearchSymposia Series, pages 85–103. PlenumPress,New York, 1972.

H. Kellerer and U. Pferschy. A new fully polynomialtime approximation scheme for the knapsackproblem. J. Comb. Optim., 3(1):59–71, 1999.

H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, Germany, 2004.

S. Martello and P. Toth. An upper bound for thezero-one knapsack problemand a branch and bound algorithm. European Journal of Operational Research,1(3):169–175,May 1977.

S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. Wiley, NewYork, NY, USA, 1990.

J. D. Papastavrou, S. Rajagopalan, and A. J. Kleywegt. The dynamic and stochastic knapsack problem with deadlines. Management Science, 42:1706–1718, December 1996.

R. Parra-Hernandez, D. Vanderster, and N. J. Dimopoulos. Resource management and knapsack formulations on the grid. In Proceedings of the 5thIEEE/ACM International Workshop on Grid Computing, GRID ’04, pages 94–101,Washington, DC, USA,2004. IEEE Computer Society.

D. Pisinger. David pisinger’s optimization codes. http://www.diku.dk/~pisinger/ odes.html.

B. Silva. Algoritmos de solución para una versión dinámica del problema de la mochila. Tesis de grado en Ingeniería Matemática, Escuela Politécnica Nacional, Quito, Ecuador, 2014.

V. V. Vazirani. Approximation algorithms. Springer, Berlin, 2001.


Texto completo: PDF

Refbacks

  • No hay Refbacks actualmente.


Creative Commons License
Este trabajo está licenciado bajo la licencia Creative Commons Attribution 3.0 .

El material presente en este sitio es de acceso abierto, es permitido su reproducción siempre y cuando se referencie a esta revista como su autor.