Métodos de geração de colunas para problemas de atribuição
Column generation methods for assignment problems
Senne, Edson Luiz F.; Lorena, Luiz Antonio N.; Salomão, Silvely Nogueira de A.
http://dx.doi.org/10.1590/S0103-65132007000100005
Prod, vol.17, n1, p.71-83, 2007
Resumo
Este trabalho apresenta métodos de geração de colunas para dois importantes problemas de atribuição: o Problema Generalizado de Atribuição (PGA) e o Problema de Atribuição de Antenas a Comutadores (PAAC). O PGA é um dos mais representativos problemas de Otimização Combinatória e consiste em otimizar a atribuição de n tarefas a m agentes, de forma que cada tarefa seja atribuída a exatamente um agente e a capacidade de cada agente seja respeitada. O PAAC consiste em atribuir n antenas a m comutadores em uma rede de telefonia celular, de forma a minimizar os custos de cabeamento entre antenas e comutadores e os custos de transferência de chamadas entre comutadores. A abordagem tradicional de geração de colunas é comparada com as propostas neste trabalho, que utilizam a relaxação lagrangeana/surrogate. São apresentados testes computacionais que demonstram a efetividade dos algoritmos propostos.
Palavras-chave
Otimização combinatória, problemas de atribuição, relaxação lagrangeana/surrogate, geração de colunas
Abstract
This work presents column generation methods for two important assignment problems: the Generalized Assignment Problem (GAP) and the problem of assigning cells to switches in cellular mobile networks (PACS). GAP is one of the most representative combinatorial optimisation problems and can be stated as the problem of optimising the assignment of n jobs to m agents, such that each job is assigned to exactly one agent and the resource capacity of each agent is not violated. PACS consists of determining a cell assignment pattern which minimizes cabling costs between a cell and a switch and transfer costs between cells assigned to different switches, while respecting certain constraints, especially those related to limited switch's capacity. The traditional column generation process is compared with the proposed algorithms that combine the column generation and lagrangean/surrogate relaxation. Computational experiments are presented in order to confirm the effectiveness of the proposed algorithms.
Keywords
Combinatorial optimization, assignment problems, lagrangean/surrogate relaxation, column generation
References
AERTS, J.; KORST, J.; SPIEKSMA, F. Approximation of a retrieval problem for parallel disks. Lecture Notes in Computer Science, v. 2653, p. 178-188, 2003.
ALBAREDA-SAMBOLA, M.; VAN DER VLERK, M.H.; FERNÁNDEZ, E. Exact Solutions to a Class of Stochastic Generalized Assignment Problems. Research report no. 02A11, University of Groningen, Research Institute of Systems, Organisations and Management, Feb. 2002.
AMINI, M.M.; RACER, M. A rigorous comparison of alternative solution methods for the generalized assignment problem. Management Science, v. 40, p. 868-890, 1994.
BAKER, B.M. E SHEASBY, J. Accelerating the convergency of subgradient optimisation. European Journal of Operational Research, v. 117, p. 136-144, 1999.
BALACHANDRAN, V. An integer generalized transportation model for optimal log assignment in computer networks. Working Paper 34-72-3. Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburg, 1976.
BEASLEY, J.E. OR-Library. Disponível em: http://www.brunel.ac.uk/depts/ma/research/ jeb/orlib/gapinfo.html. Acesso em: 23 dez. 2004.
BOKHARI, S.H. Assignment Problems in Parallel and Distributed Computing. Kluwer Academic Publisher, Boston, USA, 1987.
BURKARD, R.E. Selected topics on assignment problems. Discrete Applied Mathematics, v. 123, n. 1-3, p. 257-302, Nov. 2002.
CATTRYSSE, D.; SALOMON, M.; VAN WASSENHOVE, L. A set partitioning heuristic for the generalized assignment problem. European Journal of Operational Research, v. 72, p. 167-174, 1994.
CATTRYSSE, D.G.; VAN WASSENHOVE, L.N. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research, v. 60, p. 260-272, 1992.
CERNY, V. Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal Optimization Theory Applications, v. 45, n. 1, p. 41-51, 1985.
CHU, P.C.; BEASLEY, J.E. A genetic algorithm for the generalised assignment problem. Computers and Operations Research, v. 24, p. 17-23, 1997.
DANTZIG. G.B.; WOLFE, P. Decomposition principle for linear programs. Operations Research, v. 8, p. 101-111, 1960.
FISCHETTI, M.; LEPSCHY, C.; MINERVA, G.; ROMANIN-JACUR, G.; TOTO, E. Frequency assignment in mobile radio systems using branch-and-cut techniques. European Journal of Operational Research, v. 123, p. 241-255, 2000.
FRENCH, A.P.; WILSON, J.M. Heuristic Solution Methods for the Multilevel Generalized Assignment Problem. Journal of Heuristics, v. 8, n. 2, p. 143-153, Mar. 2002.
GAREY, M.R.; JOHNSON, D.S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W.H. Freeman and Co., 1979. 340 p.
GRUNDEL, D.A.; KROKHMAL, P.; OLIVEIRA, C.A.S.; PARDALOS, P.M. On the average case behavior of the multidimensional assignment problem. Pacific Journal of Optimization, v. 1, n. 1, p. 39-57, 2005.
HUNG, M.S.; ROM, W.O. Solving the assignment problem by relaxation. Operations Research, v. 28, n. 4, p. 969-982, 1980.
KIRUBARAJAN, T.; BAR-SHALOM, Y.; PATTIPATI, K.R. Multiassignment for tracking a large number of overlapping objects. IEEE Transactions on Aerospace and Electronic Systems, v. 37, n. 1, p. 2-21, jan. 2001.
KOOPMANS, T.C.; BECKMANN, M.J. Assignment problems and the location of economic activities. Econometrica, v. 25, p. 53-76, 1957.
KUHN, H.W. The Hungarian method for the assignment problem. Naval Research Logistic Quaterly, v. 2, p. 83-97, 1955.
LAGUNA, M.; KELLY, J.P.; GONZALEZ-VELARDE, J.L.; GLOVER, F. Tabu search for the multilevel generalized assignment problem. European Journal of Operations Research, v. 42, p. 677–687, 1995.
LOIOLA, E.M.; ABREU, N.M.M.; BOAVENTURA NETTO, P.O. Uma revisão comentada das abordagens do problema quadrático de alocação. Pesquisa Operacional, v. 24, n. 1, p. 73-109, Jan.-Abr. 2004.
LORENA, L.A.N., PEREIRA, M.A.; SALOMÃO, S.N.A. A RElaxação lagrangeana/surrogate e o método de geração de colunas: novos limitantes e novas colunas. Revista Pesquisa Operacional, v. 23, n. 1, p. 29-47, 2003.
LORENA. L.A.N.; SENNE, E.L.F. A column generation approach to capacitated p-median problems. Computers and Operations Research, v. 31, n. 6, p. 863-876, 2004.
LUAN, F.; YAO, X. Solving real-world lecture room assignment problems by genetic algorithms, Complex Systems - From Local Interactions to Global Phenomena, Amsterdam: IOS Press, p.148-160, 1996.
MARTELLO, S.; TOTH, P. An algorithm for the generalized assignment problem. Operational Research, v. 81, p. 589-603, 1981.
MARTELLO, S.; TOTH, P. Knapsack problems: algorithms and computer implementations. New York: Wiley, 1990.
MENON, S.; GUPTA, R. Assigning cells to switches in cellular networks by incorporating a pricing mechanism into simulated annealing. IEEE Transactions on Systems, Man, and Cybernetics, Part B, v. 34, n. 1, p. 558-565, 2004. n ReferênciasMerchant, A.; Sengupta, B. Assignment of cells to switches in PCS networks. IEEE/ACM Transactions on Networks, v. 3, n. 5, p. 521-526, 1995.
NARCISO, M. G. A relaxação lagrangeana/surrogate e algumas aplicações em otimização combinatória. 1998. Tese (Doutorado em Computação Aplicada) Instituto Nacional de Pesquisas Espaciais, São José dos Campos. 134 p.
NARCISO, M. G.; LORENA, L.A.N. Lagrangean/surrogate relaxation for generalized assignment problems. European Journal of Operational Research, v. 114, p. 165-177, 1999.
NAUSS, R. M. Solving the generalized assignment problem: An optimizing and heuristic approach. INFORMS Journal on Computing, v. 15, n. 3, p. 249-266, 2003.
NOWAKOVSKI, J.; SCHWÄRZLER, W.; TRIESCH, E. USIng the generalized assignment problem in scheduling the ROSAT space telescope. European Journal of Operational Research, v. 112, n. 3, p. 531-541, 1999.
OSMAN, I. H. Heuristics for the Generalized Assignment Problem: Simulated Annealing and Tabu Search Approaches, OR Spektrum, v. 17, p. 211-225, 1995.
OSORIO, M. A.; LAGUNA M. Logic cuts for multilevel generalized assignment problems. European Journal of Operational Research, v. 151, n. 1, p. 238-246, nov. 2003.
PIERRE, S.; HOUÉTO, F. Assigning cells to switches in cellular mobile networks using taboo search. IEEE Transactions on Systems, Man and Cybernetics, Part B, v. 32, n. 3, p. 209-224, 2002.
PIERSKALLA, W. P. The multidimensional assignment problem. Operations Research, v. 16, p. 422-431, 1968.
PIGATTI, A. A. Modelos e algoritmos para o problema de alocação generalizada e aplicações. Dissertação de Mestrado, Pontifícia Universidade Católica do Rio de Janeiro, julho 2003.
PUSZTASZERI, J.; RENSING, P. E.; LIEBLING, T. M. Tracking elementary particles near their primary vertex: A combinatorial approach. Journal of Global Optimization, v. 9, n. 1, p. 41-64, July 1996.
QUINTERO, A.; PIERRE S. A memetic algorithm for assigning cells to switches in cellular mobile networks. IEEE Communication Letters, v. 6, n. 11, p. 484-486, 2002.
QUINTERO, A.; PIERRE S. Assigning cells to switches in cellular mobile networks: a comparative study. Computer Communications, v. 26, n. 9, p. 950-960, 2003.
RULAND, K. S. A model for aeromedical routing and scheduling. International Transactions in Operational Research, v. 6, n. 1, p. 57-73, 1999.
SAHA, D.; MUKHERJEE, A.; BHATTACHARYA, P. A simple heuristic for assignment of cells to switches in a PCS network. Wirelles Personal Communications, v. 12, n. 3, p. 209-223, 2000.
SENNE, E. L. F.; LORENA, L.A.N. Lagrangean/surrogate heuristics for p-median problems. In: Computing tools for modeling, optimization and simulation: interfaces in computer science and operations research. M. Laguna and J.L. Gonzalez-Velarde (eds.). Kluwer Academic Publishers, 2000, p. 115-130.
WANG, L.; GU, W. Genetic algorithms with stochastic ranking for optimal channel assignment in mobile communications. Lecture Notes in Computer Science, v. 3314, p. 154-159, 2004.
WILSON, J.M. A genetic algorithm for the generalised assignment problem. Journal of the Operational Research Society, v. 48, n. 8, p. 804-809, 1997.
WRIGHT, M.B. Speeding up the Hungarian algorithm. Computers and Operations Research, v. 17, n. 1, p. 95-96, 1990.
YAGIURA, M. Generalized assignment problem instances. Disponível em: http://www-or.amp.i.kyoto-u.ac.jp/members/yagiura/gap/. Acesso em: 10 de jan. 2003.
YAGIURA, M.; IBARAKI, T.; GLOVER, F. A path relinking approach with ejection chains for the generalized assignment problem. Technical Report 2004-002, Department of Applied Mathematics and Physics, Kyoto University, 2004a.
YAGIURA, M.; IBARAKI, T.; GLOVER, F. An ejection chain approach for the generalized assignment problem. Informs Journal on Computing, v. 16, n. 2, p. 133-151, Spring, 2004b.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email