A heuristic method for solving the problem of partitioning graphs with supply and demand | Annals of Operations Research Skip to main content
Springer Nature Link
Log in

A heuristic method for solving the problem of partitioning graphs with supply and demand

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper we present a greedy algorithm for solving the problem of the maximum partitioning of graphs with supply and demand (MPGSD). The goal of the method is to solve the MPGSD for large graphs in a reasonable time limit. This is done by using a two stage greedy algorithm, with two corresponding types of heuristics. The solutions acquired in this way are improved by applying a computationally inexpensive, hill climbing like, greedy correction procedure. In our numeric experiments we analyze different heuristic functions for each stage of the greedy algorithm, and show that their performance is highly dependent on the properties of the specific instance. Our tests show that by exploring a relatively small number of solutions generated by combining different heuristic functions, and applying the proposed correction procedure we can find solutions within only a few percent of the optimal ones.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  • Alfa, A. S., Heragu, S. S., & Chen, M. (1991). A 3-opt based simulated annealing algorithm for vehicle routing problems. Computers & Industrial Engineering, 21(14), 635–639.

    Article  Google Scholar 

  • Andreev, K., & Räcke, H. (2004). Balanced graph partitioning. In Proceedings of the sixteenth annual ACM symposium on parallelism in algorithms and architectures SPAA ’04 (pp. 120–124). New York: ACM

  • Arefifar, S., Mohamed, Y., & EL-Fouly, T. H. M. (2012). Supply-adequacy-based optimal construction of microgrids in smart distribution systems. IEEE Transactions on Smart Grid, 3(3), 1491–1502.

    Article  Google Scholar 

  • Barnes, E., Vannelli, A., & Walker, J. (1988). A new heuristic for partitioning the nodes of a graph. SIAM Journal on Discrete Mathematics, 1(3), 299–305.

    Article  Google Scholar 

  • Boulaxis, N., & Papadopoulos, M. (2002). Optimal feeder routing in distribution system planning using dynamic programming technique and GIS facilities. IEEE Transactions on Power Delivery, 17(1), 242–247.

    Article  Google Scholar 

  • Chaudhuri, P. (1998). An optimal distributed algorithm for finding articulation points in a network. Computer Communications, 21(18), 1707–1715.

    Article  Google Scholar 

  • Croes, G. A. (1958). A method for solving traveling-salesman problems. Operations Research, 6(6), 791–812.

    Article  Google Scholar 

  • Galinier, P., Boujbel, Z., & Coutinho Fernandes, M. (2011). An efficient memetic algorithm for the graph partitioning problem. Annals of Operations Research, 191, 1–22.

    Article  Google Scholar 

  • Ito, T., Zhou, X., & Nishizeki, T. (2005). Partitioning trees of supply and demand. International Journal of Foundations of Computer Science, 16(4), 803–827.

    Article  Google Scholar 

  • Ito, T., Demaine, E. D., Zhou, X., & Nishizeki, T. (2008). Approximability of partitioning graphs with supply and demand. Journal of Discrete Algorithms, 6(4), 627–650.

    Article  Google Scholar 

  • Ito, T., Hara, T., Zhou, X., & Nishizeki, T. (2012). Minimum cost partitions of trees with supply and demand. Algorithmica, 64(3), 400–415.

    Article  Google Scholar 

  • Jovanovic, R., & Bousselham, A. (2014). A greedy method for optimizing the self-adequacy of microgrids presented as partitioning of graphs with supply and demand. In International renewable and sustainable energy conference (IRSEC), 2014 (pp. 565–570).

  • Jovanovic, R., & Tuba, M. (2011). An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Applied Soft Computing, 11(8), 5360–5366.

    Article  Google Scholar 

  • Jovanovic, R., & Tuba, M. (2013). Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem. Computer Science and Information Systems, 10(1), 133–149.

  • Kawabata, M., & Nishizeki, T. (2013). Partitioning trees with supply, demand and edge-capacity. IEICE Transactions, 96–A(6), 1036–1043.

    Article  Google Scholar 

  • Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 291–307.

    Article  Google Scholar 

  • Kim, Y. H., & Moon, B. R. (2004). Lock-gain based graph partitioning. Journal of Heuristics, 10(1), 37–57.

    Article  Google Scholar 

  • Kukreja, K. (2013). Articulation points or cut vertices in a graph. http://kartikkukreja.wordpress.com/2013/11/09/articulation-points-or-cut-vertices-in-a-graph/.

  • Maniezzo, V., Mingozzi, A., & Baldacci, R. (1998). A bionomic approach to the capacitated p-median problem. Journal of Heuristics, 4(3), 263–280. doi:10.1023/A:1009665717611.

    Article  Google Scholar 

  • Marinakis, Y., Migdalas, A., & Pardalos, P. (2005). Expanding neighborhood grasp for the traveling salesman problem. Computational Optimization and Applications, 32(3), 231–257.

    Article  Google Scholar 

  • Morishita, S., & Nishizeki, T. (2013). Parametric power supply networks. In D. Z. Du & G. Zhang (Eds.), Computing and combinatorics, lecture notes in computer science (Vol. 7936, pp. 245–256). Berlin: Springer.

    Google Scholar 

  • Morton, A. B., & Mareels, I. M. (2000). An efficient brute-force solution to the network reconfiguration problem. IEEE Transactions on Power Delivery, 15(3), 996–1000.

    Article  Google Scholar 

  • Narayanaswamy, N.S., & Ramakrishna, G. (2012). Linear time algorithm for tree t-spanner in outerplanar graphs via supply–demand partition in trees. In CoRR, abs/1210.7919.

  • Popa, A. (2013). Modelling the power supply network—hardness and approximation. In T. H. Chan, L. Lau, & L. Trevisan (Eds.), Theory and applications of models of computation, lecture notes in computer science (Vol. 7876, pp. 62–71). Berlin: Springer.

    Chapter  Google Scholar 

  • Reinelt, G., & Wenger, K. M. (2010). Generating partitions of a graph into a fixed number of minimum weight cuts. Discrete Optimization, 7(12), 1–12.

    Article  Google Scholar 

  • Reinelt, G., Theis, D. O., & Wenger, K. M. (2008). Computing finest mincut partitions of a graph and application to routing problems. Discrete Applied Mathematics, 156(3), 385–396.

    Article  Google Scholar 

  • Scheuerer, S., & Wendolsky, R. (2006). A scatter search heuristic for the capacitated clustering problem. European Journal of Operational Research, 169(2), 533–547.

    Article  Google Scholar 

  • Teng, J. H., & Lu, C. N. (2002). Feeder-switch relocation for customer interruption cost minimization. IEEE Transactions on Power Delivery, 17(1), 254–259.

    Article  Google Scholar 

  • Tupia, M., Cueva, R., & Guanira, M. (2013). A grasp algorithm with 2-opt improvement for job scheduling enviroment in ceramics production lines. Advances in Information Sciences & Service Sciences, 5(15), 13–23.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Qatar Environment and Energy Research Institute (QEERI) Hamad bin Khalifa University, PO Box 5825, Doha, Qatar

    Raka Jovanovic & Abdelkader Bousselham

  2. Institute of Information Systems, University of Hamburg, Von-Melle-Park 5, 20146, Hamburg, Germany

    Stefan Voß

  3. Escuela de Ingeniera Industrial, Pontificia Universidad Católica de Valparaíso, Valparaiso, Chile

    Stefan Voß

Authors
  1. Raka Jovanovic
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Abdelkader Bousselham
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Stefan Voß
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Raka Jovanovic.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jovanovic, R., Bousselham, A. & Voß, S. A heuristic method for solving the problem of partitioning graphs with supply and demand. Ann Oper Res 235, 371–393 (2015). https://doi.org/10.1007/s10479-015-1930-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-015-1930-5

Keywords