Research Article
BibTex RIS Cite

A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets

Year 2017, Volume: 17 Issue: 1, 93 - 100, 24.04.2017

Abstract

In the simple task assignment problem, at most one task should be assigned to each agent; this
constraint is relaxed in the multiple task assignment problems. The goal of the well-known Generalized
Assignment Problem is to assign tasks to agents such that the capacity of the agent does not exceed its
limits as it minimizes the total cost. In this study we present a novel approach to solve the general
assignment problem by using the hypergraphs. Hypergraphs can be considered as the generalization of
the graphs in such way that an edge can connect any number of vertices, and can be seen as the set
systems. In the hypergraph multi-assignment problem, we are looking for a cost minimizing solution to
tasks assignment to the agents which are the individual hyperedges. For this purpose, we first
determine the tasks as hyperedges and then obtain the vertex cover of the simple graph representation
of a hypergraph. Amongst the all possible covers, we choose the cost minimizing one as the solution.

References

  • Avella, P., Boccia, M., Vasilyev, I., 2010. A computational study of exact knapsack separation for the generalized assignment problem. Computational Optimization and Applications, 45(3), 543—555.
  • Balcı, M. A., Atmaca, S. P., Akgüller, Ö., 2016. Hyperpath Centers. In Advanced Computational Methods for Knowledge Engineering, Vol 473, 129—137.
  • Cherng, J.S., Lo, M.J., 2001. A hypergraph based clustering algorithm for spatial data sets, Data Mining, ICDM 2001, Proceedings IEEE International Conference on, pp. 83—90. IEEE.
  • Dıaz, J. A., Fernández, E., 2001. A tabu search heuristic for the generalized assignment problem. European Journal of Operational Research, 132(1), 22—38.
  • Fisher, M. L., Jaikumar, R., 1981. A generalized assignment heuristic for vehicle routing, Networks, 11(2), 109—124.
  • Fisher, M. L., Jaikumar, R., Van Wassenhove, L. N., 1986. A multiplier adjustment method for the generalized assignment problem. Management Science, 32(9), 1095—1103.
  • Liu, L., Mu, H., Song, Y., Luo, H., Li, X., Wu, F., 2012. The equilibrium generalized assignment problem and genetic algorithm. Applied Mathematics and Computation, 218(11), 6526—6535.
  • Nauss, R. M., 2003. Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS Journal on Computing, 15(3), 249—266.
  • Özbakir, L., Baykasoğlu, A., Tapkan, P. 2010. Bees algorithm for generalized assignment problem. Applied Mathematics and Computation, 215(11) 3782—3795.
  • Privault, C., Herault, L., 1998. Solving a real world assignment problem with a metaheuristic. Journal of Heuristics, 4(4), 383—398.
  • Ross, G. T., Soland, R. M., 1975. A branch and bound algorithm for the generalized assignment problem. Mathematical programming, 8(1), 91—103.
  • Savelsbergh, M., 1997. A branch-and-price algorithm for the generalized assignment problem. Operations Research, 45(6), 831—841.
  • Sethanan, K., Pitakaso, R., 2016. Improved differential evolution algorithms for solving generalized assignment problem. Expert Systems with Applications, 45, 450—459.
  • Shtub, A., Kogan, K., 1998. Capacity planning by the dynamic multi-resource generalized assignment problem (DMRGAP). European Journal of Operational Research, 105(1), 91—99.
  • Subtil, R.F., Carrano, E. G., Souza, M .J., Takahashi, R. H., 2010. Using an enhanced integer NSGA-II for solving the multi objective generalized assignment problem. In Proceedings of the 2010 IEEE congress on evolutionary computation(CEC), 1—7, IEEE.
  • Yu, J., Tao, D., Wang, M., 2012. Adaptive hypergraph learning and its application in image classification, IEEE Transactions on Image Processing,, 21(7), 3262—3272.
  • Yu, J., Tao, D., Li, J., Cheng, J., 2014. Semantic preserving distance metric learning and applications, Information Sciences, 281, 674—686.
  • Zhang, H., Yu, J., Wang, M., Liu, Y., 2012. Semisupervised distance metric learning based on local linear regression for data clustering. Neurocomputing, 93, 100—105.
  • Zhang, L., Gao, Y., Hong, C., Feng, Y., Zhu, J., Cai, D., 2014. Feature correlation hypergraph: exploiting high-order potentials for multimodal recognition. Cybernetics, IEEE Transactions on Cybernetics, 44(8), 1408—1419.
  • http://www.muglasm.gov.tr/sayfa/62/acil-saglikhizmetleri- istasyonlari, (29.05.2016)
  • http://people.brunel.ac.uk/~mastjjb/jeb/orlib/gapinfo.h tml, (16.01.2017)
Year 2017, Volume: 17 Issue: 1, 93 - 100, 24.04.2017

Abstract

References

  • Avella, P., Boccia, M., Vasilyev, I., 2010. A computational study of exact knapsack separation for the generalized assignment problem. Computational Optimization and Applications, 45(3), 543—555.
  • Balcı, M. A., Atmaca, S. P., Akgüller, Ö., 2016. Hyperpath Centers. In Advanced Computational Methods for Knowledge Engineering, Vol 473, 129—137.
  • Cherng, J.S., Lo, M.J., 2001. A hypergraph based clustering algorithm for spatial data sets, Data Mining, ICDM 2001, Proceedings IEEE International Conference on, pp. 83—90. IEEE.
  • Dıaz, J. A., Fernández, E., 2001. A tabu search heuristic for the generalized assignment problem. European Journal of Operational Research, 132(1), 22—38.
  • Fisher, M. L., Jaikumar, R., 1981. A generalized assignment heuristic for vehicle routing, Networks, 11(2), 109—124.
  • Fisher, M. L., Jaikumar, R., Van Wassenhove, L. N., 1986. A multiplier adjustment method for the generalized assignment problem. Management Science, 32(9), 1095—1103.
  • Liu, L., Mu, H., Song, Y., Luo, H., Li, X., Wu, F., 2012. The equilibrium generalized assignment problem and genetic algorithm. Applied Mathematics and Computation, 218(11), 6526—6535.
  • Nauss, R. M., 2003. Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS Journal on Computing, 15(3), 249—266.
  • Özbakir, L., Baykasoğlu, A., Tapkan, P. 2010. Bees algorithm for generalized assignment problem. Applied Mathematics and Computation, 215(11) 3782—3795.
  • Privault, C., Herault, L., 1998. Solving a real world assignment problem with a metaheuristic. Journal of Heuristics, 4(4), 383—398.
  • Ross, G. T., Soland, R. M., 1975. A branch and bound algorithm for the generalized assignment problem. Mathematical programming, 8(1), 91—103.
  • Savelsbergh, M., 1997. A branch-and-price algorithm for the generalized assignment problem. Operations Research, 45(6), 831—841.
  • Sethanan, K., Pitakaso, R., 2016. Improved differential evolution algorithms for solving generalized assignment problem. Expert Systems with Applications, 45, 450—459.
  • Shtub, A., Kogan, K., 1998. Capacity planning by the dynamic multi-resource generalized assignment problem (DMRGAP). European Journal of Operational Research, 105(1), 91—99.
  • Subtil, R.F., Carrano, E. G., Souza, M .J., Takahashi, R. H., 2010. Using an enhanced integer NSGA-II for solving the multi objective generalized assignment problem. In Proceedings of the 2010 IEEE congress on evolutionary computation(CEC), 1—7, IEEE.
  • Yu, J., Tao, D., Wang, M., 2012. Adaptive hypergraph learning and its application in image classification, IEEE Transactions on Image Processing,, 21(7), 3262—3272.
  • Yu, J., Tao, D., Li, J., Cheng, J., 2014. Semantic preserving distance metric learning and applications, Information Sciences, 281, 674—686.
  • Zhang, H., Yu, J., Wang, M., Liu, Y., 2012. Semisupervised distance metric learning based on local linear regression for data clustering. Neurocomputing, 93, 100—105.
  • Zhang, L., Gao, Y., Hong, C., Feng, Y., Zhu, J., Cai, D., 2014. Feature correlation hypergraph: exploiting high-order potentials for multimodal recognition. Cybernetics, IEEE Transactions on Cybernetics, 44(8), 1408—1419.
  • http://www.muglasm.gov.tr/sayfa/62/acil-saglikhizmetleri- istasyonlari, (29.05.2016)
  • http://people.brunel.ac.uk/~mastjjb/jeb/orlib/gapinfo.h tml, (16.01.2017)
There are 21 citations in total.

Details

Primary Language English
Journal Section Articles
Authors

Mehmet Ali Balcı

Publication Date April 24, 2017
Submission Date May 29, 2016
Published in Issue Year 2017 Volume: 17 Issue: 1

Cite

APA Balcı, M. A. (2017). A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, 17(1), 93-100.
AMA Balcı MA. A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi. April 2017;17(1):93-100.
Chicago Balcı, Mehmet Ali. “A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets”. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi 17, no. 1 (April 2017): 93-100.
EndNote Balcı MA (April 1, 2017) A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi 17 1 93–100.
IEEE M. A. Balcı, “A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets”, Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, vol. 17, no. 1, pp. 93–100, 2017.
ISNAD Balcı, Mehmet Ali. “A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets”. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi 17/1 (April 2017), 93-100.
JAMA Balcı MA. A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi. 2017;17:93–100.
MLA Balcı, Mehmet Ali. “A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets”. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi, vol. 17, no. 1, 2017, pp. 93-100.
Vancouver Balcı MA. A Hypergraph Solution to Generalized Assignment Problem and Application to Spatial Data Sets. Afyon Kocatepe Üniversitesi Fen Ve Mühendislik Bilimleri Dergisi. 2017;17(1):93-100.