Eliminação Paralela de Termos Dominantes no Problema da Mochila
Resumo
Um dos problemas mais conhecidos em otimização combinatória é o problema da mochila ilimitado. Devido a sua importância diversos autores buscaram formas eficientes de resolvê-lo. Por um lado, diversos estudos da paralelização deste problema foram feitos. Por outro lado, várias técnicas de eliminação de objetos também foram encontradas. Neste trabalho nós unimos as duas possibilidades apresentando algoritmos paralelos para a eliminação de objetos. Para validação dos algoritmos, os mesmos foram implementados em Java e executados em um cluster de computadores.
Referências
V. Aleksandrov and S. Fidanova. Non-uniform recurrence equations on 2d regular arrays. In Advance in Numerical Methods and Applications, in Proc. of NMA94, pages 217-225,. August 1994.
V. Aleksandrov and S. Fidanova. On the expected execution time for a class of non uniform recurrence equations mapped onto ld array. Parallel Algorithms and Applications, 1:303 - 314, 1994.
R. Andonov and F. Gruau. A 2D modular toroidal systolic array for the Knapsack problem. In ASAP '91, pages 458-472, 1991.
R. Andonov and P. Quinton. Efficient linear systolic array for Knapsack problem. In CONPAR'92, number 634 in LNCS, pages 247-258, 1992.
R. Andonov and S. Rajopadhye. Knapsack on VLSI: from algorithm to optimal circuits. IEEE Transactions on Parallel and Distributed Systems, 8(6):545 - 562, 1997.
G-H. Chen, M-S. Chem, and J-H. Jang. Pipeline architectures for dynamic programming algorithms. Parallel Computing, 13(1): 111 - 117, 1990.
G-H. Chen and J-H. Jang. An improved parallel algorithm for 0/1 knapsack problem. Parallel Computing, 18(7):811-821, 1992.
K. Dudzinski. A note on dominance relation in unbounded knapsack problem. Operations Research Letters 10, 1991.
M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory o.f NP-completeness. W.H. Freeman and Comp., San Francisco, 1979.
T. Gerasch and P. Wang. A survey of parallel algorithm for one-dimensional integer Knapsack problems. Infor, 32(3): 163-186, 1993.
P.C. Gil more and R.E Gomory. A linear programming approach to the cutting stock problem - part ii. Operations Research 11, 1963.
A. Goldman and D. Trystram. An efficient parallel algorithm for solving the Knapsack problem on hypercube. Journal of Parallel and Distributed Computing, (accepted), 2002.
E. Horowitz and S. Sahni. Computing partitions with applications to the Knapsack problem. Journal of ACM, 21:277 - 292, 1974.
T.C. Hu. Combinatorial Algorithms, chapter 3. Addison Wesley, 1982.
J. Lee, E. Shragowitz, and S. Sahni. A hypercube algorithm for the 0/1 Knapsack problem. Journal of Parallel and Distributed Computing, 5(4):438-456, 1988.
J. Lin and J. Storer. Processor efficient hypercube algorithm for the Knapsack problem. Journal of Parallel and Distributed Computing, 13(3):332 - 337, 1991.
S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, New York, 1990.
D.G. Morales, F. Almeida, C. Rodríguez, J. L. Roda, I. Coloma, and A. Delgado. Parallel dynamic programming and automata theory. Parallel Computing, 26:113 - 134, 2000.
C.M. Pancake and C. Lengauer. Special issue on high performance java. Communications of ACM, 44(10), 2001.
D. Pisinger. Algorithms for knapsack problems. Ph.D Thesis, 1995.
V. Poirriez R. Andonov and S. Rajopadhye. Unbounded Knapsack problem: Dynamic programming revisited. European Journal of Operational Research, 123:394 - 407, 2000.
N. Zhu and K. Broughan. On dominated terms in the general Knpasack problem. Operations Research Letters, 21:31-37, 1997.
V. Aleksandrov and S. Fidanova. On the expected execution time for a class of non uniform recurrence equations mapped onto ld array. Parallel Algorithms and Applications, 1:303 - 314, 1994.
R. Andonov and F. Gruau. A 2D modular toroidal systolic array for the Knapsack problem. In ASAP '91, pages 458-472, 1991.
R. Andonov and P. Quinton. Efficient linear systolic array for Knapsack problem. In CONPAR'92, number 634 in LNCS, pages 247-258, 1992.
R. Andonov and S. Rajopadhye. Knapsack on VLSI: from algorithm to optimal circuits. IEEE Transactions on Parallel and Distributed Systems, 8(6):545 - 562, 1997.
G-H. Chen, M-S. Chem, and J-H. Jang. Pipeline architectures for dynamic programming algorithms. Parallel Computing, 13(1): 111 - 117, 1990.
G-H. Chen and J-H. Jang. An improved parallel algorithm for 0/1 knapsack problem. Parallel Computing, 18(7):811-821, 1992.
K. Dudzinski. A note on dominance relation in unbounded knapsack problem. Operations Research Letters 10, 1991.
M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory o.f NP-completeness. W.H. Freeman and Comp., San Francisco, 1979.
T. Gerasch and P. Wang. A survey of parallel algorithm for one-dimensional integer Knapsack problems. Infor, 32(3): 163-186, 1993.
P.C. Gil more and R.E Gomory. A linear programming approach to the cutting stock problem - part ii. Operations Research 11, 1963.
A. Goldman and D. Trystram. An efficient parallel algorithm for solving the Knapsack problem on hypercube. Journal of Parallel and Distributed Computing, (accepted), 2002.
E. Horowitz and S. Sahni. Computing partitions with applications to the Knapsack problem. Journal of ACM, 21:277 - 292, 1974.
T.C. Hu. Combinatorial Algorithms, chapter 3. Addison Wesley, 1982.
J. Lee, E. Shragowitz, and S. Sahni. A hypercube algorithm for the 0/1 Knapsack problem. Journal of Parallel and Distributed Computing, 5(4):438-456, 1988.
J. Lin and J. Storer. Processor efficient hypercube algorithm for the Knapsack problem. Journal of Parallel and Distributed Computing, 13(3):332 - 337, 1991.
S. Martello and P. Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, New York, 1990.
D.G. Morales, F. Almeida, C. Rodríguez, J. L. Roda, I. Coloma, and A. Delgado. Parallel dynamic programming and automata theory. Parallel Computing, 26:113 - 134, 2000.
C.M. Pancake and C. Lengauer. Special issue on high performance java. Communications of ACM, 44(10), 2001.
D. Pisinger. Algorithms for knapsack problems. Ph.D Thesis, 1995.
V. Poirriez R. Andonov and S. Rajopadhye. Unbounded Knapsack problem: Dynamic programming revisited. European Journal of Operational Research, 123:394 - 407, 2000.
N. Zhu and K. Broughan. On dominated terms in the general Knpasack problem. Operations Research Letters, 21:31-37, 1997.
Publicado
28/10/2002
Como Citar
ARRUDA, Flávio Regis de; GOLDMAN, Alfredo.
Eliminação Paralela de Termos Dominantes no Problema da Mochila. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 3. , 2002, Vitória.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2002
.
p. 89-94.
DOI: https://doi.org/10.5753/wscad.2002.20766.
