Systematic Literature Review Robust Graph Coloring on Electric Circuit Problems

Authors

  • Viona Prisyella Balqis Master of Mathematics Student, Faculty of Mathematics and Natural Sciences, Padjadjaran University
  • Diah Chaerani Department of Mathematics, Faculty of Mathematics and Natural Sciences, Padjadjaran University
  • Herlina Napitupulu Department of Mathematics, Faculty of Mathematics and Natural Sciences, Padjadjaran University

DOI:

https://doi.org/10.31764/jtam.v6i4.9446

Keywords:

PRISMA, Robust Optimization, Graph Coloring Problem, Electricity Problem.

Abstract

Graph Coloring Problem (GCP) is the assignment of colors to certain elements in a graph based on certain constraints. GCP is used by assigning a color label to each node with neighboring nodes assigned a different color and the minimum number of colors used. Based on this, GCP can be drawn into an optimization problem that is to minimize the colors used. Optimization problems in graph coloring can occur due to uncertainty in the use of colors to be used, so it can be assumed that there is an uncertainty in the number of colored vertices. One of the mathematical optimization methods in the presence of uncertainty is Robust Optimization (RO). RO is a modeling methodology combined with computational tools to process optimization problems with uncertain data and only some data for which certainty is known. This paper will review research on Robust GCP with model validation to be applied to electrical circuit problems using a systematic review of the literature. A systematic literature review was carried out using the Preferred Reporting Items for Systematic reviews and Meta Analysis (PRISMA) method. The keywords used in this study were used to search for articles related to this research using a database. Based on the results of the search for articles obtained from PRISMA and Bibliometric R Software, it was found that there was a relationship between the keywords Robust Optimization and Graph Coloring, this means that at least there is at least one researcher who has studied the problem. However, the Electricity keyword has no relation to the other two keywords, so that a gap is obtained and it is possible if the research has not been studied and discussed by other researchers. Based on the results of this study, it is hoped that it can be used as a consideration and a better solution to solve optimization problems.

References

Arsyad, M. A. K., Yahya, L., Wungguli, D., Yahya, N. I. (n.d.). Artikel preprint. 1–18.

Ben-Tal, A., & Nemirovski, A. (2002). Robust optimization - Methodology and applications. Mathematical Programming, Series B, 92(3), 453–480. https://doi.org/10.1007/s101070100286

Ben-Tal, A., Ghaoui, L. E., Nemirovski, A. (2009). Robust Optimization : Princeton Series. New Jersey: Princeton University Press.

Bertsimas, D., Brown, D. B., Caramanis, C. (2011). Robust optimization. Society for Industrial and Applied Mathematics, 53(3), 464–501.

Budgen, D., Brereton, P. (2006). Performing Systematic Literature Reviews in Software Engineering, 82(2), 1051–1052. https://doi.org/10.1080/00378941.1935.10832973

Burke, E. K., MareÄek, J., Parkes, A. J., & Rudová, H. (2010). A supernodal formulation of vertex colouring with applications in course timetabling. Annals of Operations Research, 179(1), 105–130. https://doi.org/10.1007/s10479-010-0716-z

Chaerani, D., & Roos, C. (2013). Handling Optimization under Uncertainty Problem Using Robust Counterpart Methodology. Jurnal Teknik Industri, 15(2), 111–118. https://doi.org/10.9744/jti.15.2.111-118

Diaz, M. I., Nasini, G., Savirin, d., (2004). A Linear Integer Programming Approach for The Equitable Coloring Problem. Information Sciences, 2–5.

Dunning, I., Huchette, J., & Lubin, M. (2017). JuMP: A modeling language for mathematical optimization. SIAM Review, 1-26. https://doi.org/10.1137/15M1020575

Elumalai, A. (2020). Graph coloring and its implementation. Malaya Journal of Matematik, S(2), 1672–1674. https://doi.org/10.26637/MJM0S20/0445

Froger, A., Gendreau, M., Mendoza, J. E., Pinson, E. (2017). A branch-and-check approach for a wind turbine maintenance scheduling problem. Computers and Operations Research, 88, 117-136. https://doi.org/10.1016/j.cor.2017.07.001.c

Gorissen, B. L., Yanikoğlu, I., & den Hertog, D. (2015). A practical guide to robust optimization. Omega (United Kingdom), 53, 124–137. https://doi.org/10.1016/j.omega.2014.12.006

Hansen, P., Labbé, M., & Schindl, D. (2009). Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results. Discrete Optimization, 6(2), 135–147. https://doi.org/10.1016/j.disopt.2008.10.004

Hassan, H. K., Mohamed, A., & Alali, A. (2016). DSA–based Energy Efï¬cient Cellular Networks Integration with The Smart Grid.

Hertog, D. Den. (2015). Practical Robust Optimization - an introduction. Netherlands: Tillburg University.

Jabrayilov, A., & Mutzel, P. (2018). New integer linear programming models for the vertex coloring problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 10807 LNCS(23), 640–652. https://doi.org/10.1007/978-3-319-77404-6_47

Jovanović, P., Pavlović, N., Belošević, I., & Milinković, S. (2020). Graph coloring-based approach for railway station design analysis and capacity determination. European Journal of Operational Research, 287(1), 348–360. https://doi.org/10.1016/j.ejor.2020.04.057

Kabang, N. K., Yundari., Fran, F. (2020). Bilangan kromatik lokasi pada graf bayangan dan graf middle dari graf bintang. 09(2), 329–336.

Maiti, A., & Tripathy, B. (2012). Applying Colored-Graph Isomorphism for Electrical Circuit Matching in Circuit Repository. International Journal of Computer Science Issues, 9(3), 391–395.

Marx, D. (2004). Graph colouring problems and their applications in scheduling. Periodica Polytechnica Electrical Engineering, 48(1–2), 11–16.

Nickel, R. (2005). Graph Coloring. 408–438. https://doi.org/10.1201/b16132-29

Page, M. J., McKenzie, J. E., Bossuyt, P. M., Boutron, I., Hoffmann, T. C., Mulrow, C. D., Shamseer, L., Tetzlaff, J. M., Akl, E. A., Brennan, S. E., Chou, R., Glanville, J., Grimshaw, J. M., Hróbjartsson, A., Lalu, M. M., Li, T., Loder, E. W., Mayo-Wilson, E., McDonald, S., McGuinness, L. A., Stewart, L. A., Thomas, J., Tricco, A. C., Welch, V. A., Whiting, P., Moher, D. (2021). The PRISMA 2020 statement: An updated guideline for reporting systematic reviews. The BMJ, 372. https://doi.org/10.1136/bmj.n71

Porumbel, D. (2018). Cutting Planes by Projecting Interior Points onto Polytope Facets. Technical Report CS Laboratory CEDRIC-18-4309 of CNAM, Paris. http://cedric.cnam.fr/~porumbed/projcutplanes/main.pdf

Rao, S. S. (2009). Engineering Optimization. In Sheet Metal Forming Optimization. https://doi.org/10.4324/9781315156101-4

Selcuk, A. A. (2019). A Guide for Systematic Reviews: PRISMA. Turkish Archives of Otorhinolaryngology, 57(1), 57–58. https://doi.org/10.5152/tao.2019.4058

Shehab, M., Khader, A. T., & Al-Betar, M. A. (2017). A survey on applications and variants of the cuckoo search algorithm. Applied Soft Computing Journal, 61, 1041–1059. https://doi.org/10.1016/j.asoc.2017.02.034

Van Hoeve, W. J. (2020). Graph Coloring Lower Bounds from Decision Diagrams. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12125 LNCS, 405–418. https://doi.org/10.1007/978-3-030-45771-6_31

Xiao, Y., & Watson, M. (2019). Guidance on Conducting a Systematic Literature Review. Journal of Planning Education and Research, 39(1), 93–112. https://doi.org/10.1177/0739456X17723971

Xiong, J., Acar, E., Agrawal, B., Conn, A. R., Ditlow, G., Feldmann, P., Finkler, U., Gaucher, B., Gupta, A., Heng, f-L., Koc, J. R. K. A., Kung, D., Phan, D., Singhee, A., Smith, B. (2011). Framework for Largeâ€Scale Modeling and Simulation of Electricity Systems for Planning, Monitoring, and Secure Operations of Nextâ€generation Electricity Grids. Computational Needs for the Next Generation Electric Grid Workshop, 1, 1–6. http://winmec.ucla.edu/smartgrid/technology.html

Xu, H., Caramanis, C., & Mannor, S. (2010). A distributional interpretation of robust optimization. Forty-Eighth Annual Allerton Conference Allerton House, 0(0), 552–556. https://doi.org/10.1287/moor.1110.0531

Yang, X., Wang, Z., Zhang, H., Ma, N., Yang, N., Liu, H., Zhang, H & Yang, L. (2022). A Review: Machine Learning for Combinatorial Optimization Problems in Energy Areas. Algorithms, 1-43. https://doi.org/10.3390/a15060205

Yanıkoğlu, İ., Gorissen, B. L., & den Hertog, D. (2019). A survey of adjustable robust optimization. European Journal of Operational Research, 277(3), 799–813. https://doi.org/10.1016/j.ejor.2018.08.031

Downloads

Published

2022-10-07

Issue

Vol. 6 No. 4 (2022): October

Section

Articles

License

Authors who publish articles in JTAM (Jurnal Teori dan Aplikasi Matematika) agree to the following terms:

  1. Authors retain copyright of the article and grant the journal right of first publication with the work simultaneously licensed under a CC-BY-SA or The Creative Commons Attribution–ShareAlike License.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).