How to optimally paint your door
Alireza Soroudi, PhD
Lead Data Scientist @ bluecrux || SMIEEE || Optimization expert || Healthcare management || Lab Digitalization || Power and Energy systems || Developer || Author / Speaker || (views are mine)
If you visit Ireland you can see colorful doors almost every where (usually no two neighbors?have the same door color)
Graph coloring is an old operation research problem. The question is how to assign colors to each graph node to make sure no two connected nodes share the same color.
It has several applications such as
I decided to paint the IEEE test power systems (IEEE 300bus and IEEE 118bus systems).
The MILP problem formulation is quite simple as follows:
The problem is solved in Pyomo package, here is the Python code
The colored graph (IEEE 300 Bus system) can be observed as follows (3 colors will be needed):
As it can be seen, the number of nodes painetd by each color are not the same. (Red is used more), We can add some constraints to resolve this issue:
Keeping the same number of colors and resolving the problem will give us a better answer as follows:
We can do the same for IEEE 118 bus network (4 colors will be needed)
We can do the same for edge coloring (no two edges having a common node should have the same color)
Professor in Operations Research
3 年Alireza, again thanks for sharing this piece of online optimization. As a simple comment, the optimal solution of the door painting problem is 2 :-) If in your street you have 20 doors to paint and 8 colors, you may maximize the number of doors between two doors of the same color. The model in Julia is given below as well as the solution. As you can see, patterns are repeated. Once again, thanks for all of this newsletter I like it very much.
Dentist | Healthcare Data Science / A.i | Generative A.i for healthcare "clinical LLM's" | Digital Healthcare Transformation & Integration | MSc Operations Research | Applied Statistics(FGSSR) | DTQM( AICPD).
3 年Great as usual Thank you
John Mario Chica Rodriguez?