Robust Coloring Optimization Model on Electricity Circuit Problems

Viona Prisyella Balqis; Diah Chaerani; Herlina Napitupulu

doi:10.34312/jjom.v5i1.16393

Robust Coloring Optimization Model on Electricity Circuit Problems

Viona Prisyella Balqis, Diah Chaerani, Herlina Napitupulu

Abstract

The Graph Coloring Problem (GCP) is assigning different colors to certain elements in a graph based on certain constraints and using a minimum number of colors. GCP can be drawn into optimization problems, namely the problem of minimizing the color used together with the uncertainty in using the color used, so it can be assumed that there is an uncertainty in the number of colored vertices. One of the mathematical optimization techniques in dealing with uncertainty is Robust Optimization (RO) combined with computational tools. This article describes a robust GCP using the Polyhedral Uncertainty Theorem and model validation for electrical circuit problems. The form of an electrical circuit color chart consists of corners (components) and edges (wires or conductors). The results obtained are up to 3 colors for the optimization model for graph coloring problems and up to 5 colors for robust optimization models for graph coloring problems. The results obtained with robust optimization show more colors because the results contain uncertainty. When RO GCP is applied to an electrical circuit, the model is used to place the electrical components in the correct path so that the electrical components do not collide with each other.

Keywords

Robust Optimization; Graph Coloring Problem; Electricity Problem

Full Text:

PDF

References

W.-J. van Hoeve, “Graph Coloring Lower Bounds from Decision Diagrams,” in Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 2020, pp. 405–418, doi: 10.1007/978-3-030-45771-6 31. [Online]. Available: http://link.springer.com/10.1007/978-3-030-45771-6 31

A. Elumalai, “Graph coloring and its implementation,” Malaya Journal of Matematik, vol. S, no. 2, pp. 1672–1674, 1672, doi:https://doi.org/10.26637/MJM0S20/0445.

I. M. Dıaz, G. Nasini, and D. Severın, “A Linear Integer Programming Approach for The Equitable Coloring Problem,” Information Sciences, pp. 2–5, 2004.

R. Nickel, “Graph Coloring: Application of the Ellipsoid Method in Combinatorial Optimization,” FernUni Hagen, pp. 408–438, 2005, doi:10.1201/b16132-29.

P. Hansen, M. Labbe, and D. Schindl, “Set covering and packing formulations of ´graph coloring: Algorithms and first polyhedral results,” Discrete Optimization, vol. 6, no. 2, pp. 135–147, may 2009, doi: 10.1016/j.disopt.2008.10.004. [Online]. Available: https://linkinghub.elsevier.com/retrieve/pii/S1572528608000716

E. K. Burke, J. Marecek, A. J. Parkes, and H. Rudov ˇ a, “A supernodal formulation of ´vertex colouring with applications in course timetabling,” Annals of Operations Research, vol. 179, no. 1, pp. 105–130, sep 2010, doi: 10.1007/s10479-010-0716-z. [Online]. Available:http://link.springer.com/10.1007/s10479-010-0716-z

A. Jabrayilov and P. Mutzel, “New Integer Linear Programming Models for the Vertex Coloring Problem,” in Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), 2018, pp. 640–652, doi: 10.1007/978-3-319-77404-6 47. [Online]. Available: http://link.springer.com/10.1007/978-3-319-77404-6 47

P. Jovanovic, N. Pavlovi ´ c, I. Belo ´ sevi ˇ c, and S. Milinkovi ´ c, “Graph coloring-based approach ´for railway station design analysis and capacity determination,” European Journal of Operational Research, vol. 287, no. 1, pp. 348–360, nov 2020, doi:10.1016/j.ejor.2020.04.057.[Online]. Available:https://linkinghub.elsevier.com/retrieve/pii/S0377221720304100

D. Marx, “Graph colouring problems and their applications in scheduling,” Periodica Polytechnica Electrical Engineering, vol. 48, no. 1-2, pp. 11–16, 2004.

h. Yanıkoglu, B. L. Gorissen, and D. den Hertog, “A survey of adjustable robust ˘optimization,” European Journal of Operational Research, vol. 277, no. 3, pp. 799–813, sep 2019, doi: 10.1016/j.ejor.2018.08.031. [Online]. Available:https://linkinghub.elsevier.com/retrieve/pii/S0377221718307264

N. K. Kabang, Y. Yundari, and F. Fran, “Bilangan kromatik lokasi pada graf bayangan dan graf middle dari graf bintang,” Bimaster : Buletin Ilmiah Matematika, Statistika dan Terapannya, vol. 9, no. 2, pp. 329–336, mar 2020, doi: 10.26418/bbimst.v9i2.39977. [Online]. Available:https://jurnal.untan.ac.id/index.php/jbmstr/article/view/39977

M. A. K. Arsyad, L. Yahya, D. Wungguli, and N. I. Yahya, “Pewarnaan Graf pada Penjadwalan Pengangkutan Sampah di Kota Gorontalo,” OSF Preprints, pp. 1–18, 2020, doi:10.31219/osf.io/rq6cg. [Online]. Available: 10.31219/osf.io/rq6cg

A. Maiti and B. Tripathy, “Applying Colored-Graph Isomorphism for Electrical Circuit Matching in Circuit Repository,” International Journal of Computer Science, vol. 9, no. 3, pp. 391–395, 2012. [Online]. Available: http://www.doaj.org/doajfunc=fulltext&aId=1158414

D. Bertsimas, D. B. Brown, and C. Caramanis, “Theory and Applications of Robust Optimization,” SIAM Review, vol. 53, no. 3, pp. 464–501, jan 2011, doi: 10.1137/080734510. [Online]. Available: http://epubs.siam.org/doi/10.1137/080734510

A. Ben-Tal and A. Nemirovski, “Robust optimization methodology and applications,”Mathematical Programming, vol. 92, no. 3, pp. 453–480, may 2002, doi: 10.1007/s101070100286. [Online]. Available: http://link.springer.com/10.1007/s101070100286

H. Xu, C. Caramanis, and S. Mannor, “A Distributional Interpretation of Robust Optimization,” Mathematics of Operations Research, vol. 37, no. 1, pp. 95–110, feb 2012, doi:10.1287/moor.1110.0531. [Online]. Available:http://pubsonline.informs.org/doi/10.1287/moor.1110.0531

D. D. Hertog, “Practical Robust Optimization - an introduction,” in NGB/LNMB Seminar. Tilburg: Tilburg University, 2013, pp. 1–53.

B. L. Gorissen, h. Yanıkoglu, and D. den Hertog, “A practical guide to robust optimization,” Omega, vol. 53, pp. 124–137, jun 2015, doi: 10.1016/j.omega.2014.12.006. [Online]. Available:https://linkinghub.elsevier.com/retrieve/pii/S0305048314001698

A. Ben-Tal, L. E. Ghaoui, and A. Nemirovski, “Robust Optimization,” in Princeton Series in Applied Mathematics. New Jersey: Princeton University Press, 2009.

S. S. Rao, Engineering Optimization Theory and Practice, 4th ed. New Jersey: John Wiley & Sons, Inc., 2009. ISBN 9780470183526

D. Chaerani and C. Roos, “Handling Optimization under Uncertainty Problem Using Robust Counterpart Methodology,” Jurnal Teknik Industri, vol. 15, no. 2, pp. 111–118, dec 2013, doi: 10.9744/jti.15.2.111-118. [Online]. Available: http://puslit2.petra.ac.id/ejournal/index.php/ind/article/view/18848

DOI: https://doi.org/10.34312/jjom.v5i1.16393