Graph Coloring is one of the famous problems in the Graph Theory literature. The idea is...

Transcribed Image Text:

Graph Coloring is one of the famous problems in the Graph Theory literature. The idea is to find a way to color the vertices of a graph such that no two adjacent vertices are of the same color. There are many algorithms to find solution for this problem, and binary integer programming is one of them. The problem is basically to assign colors to vertices, while using the minimum number of colors. One of the application areas is "map coloring": The regions on the map should be colored so that each region can be differentiated. The same color cannot be used to color any two adjacent regions. A trivial example is given in the figure, where the solution can be easily seen by just looking, but don't forget, the problem complexity increases exponentially as the number of vertices/countries increases. But we will not deal with it in this exam. (Lingo is not capable to solve it when there are 6 countries) You are asked to write a BIP model for this problem. You need to decide which countries should be assigned to which color. The aim is to use minimum number of colors used. You have 5 countries: 1. Poland 2. Czechia 3. Slovakia 4. Austria 5. Hungary And 5 colors: 1. Red 2. Blue 3. Green 4. Yellow 5. Orange b) Write your objective function (minimize the number of colors used) (5 points) c) Write your constraints Adjacency matrix: 01100 10110 11011 Czech Republic 01101 00110 Poland a) Define the decision variables. (you will need 2 different set of binary decision variables) (5 points) Slovakia Austria Hungary a. Each country should have exactly one color. (5 points) b. Any two adjacent countries cannot have the same color. (you may need an adjacency matrix, which is given below. And also be careful: you will need to include if the color is in use or not-don't just write "1" on your right hand side) (10 points) d) Solve the model, provide the resulting screenshot. Write down the solution: color-country assignment. (10 points) Graph Coloring is one of the famous problems in the Graph Theory literature. The idea is to find a way to color the vertices of a graph such that no two adjacent vertices are of the same color. There are many algorithms to find solution for this problem, and binary integer programming is one of them. The problem is basically to assign colors to vertices, while using the minimum number of colors. One of the application areas is "map coloring": The regions on the map should be colored so that each region can be differentiated. The same color cannot be used to color any two adjacent regions. A trivial example is given in the figure, where the solution can be easily seen by just looking, but don't forget, the problem complexity increases exponentially as the number of vertices/countries increases. But we will not deal with it in this exam. (Lingo is not capable to solve it when there are 6 countries) You are asked to write a BIP model for this problem. You need to decide which countries should be assigned to which color. The aim is to use minimum number of colors used. You have 5 countries: 1. Poland 2. Czechia 3. Slovakia 4. Austria 5. Hungary And 5 colors: 1. Red 2. Blue 3. Green 4. Yellow 5. Orange b) Write your objective function (minimize the number of colors used) (5 points) c) Write your constraints Adjacency matrix: 01100 10110 11011 Czech Republic 01101 00110 Poland a) Define the decision variables. (you will need 2 different set of binary decision variables) (5 points) Slovakia Austria Hungary a. Each country should have exactly one color. (5 points) b. Any two adjacent countries cannot have the same color. (you may need an adjacency matrix, which is given below. And also be careful: you will need to include if the color is in use or not-don't just write "1" on your right hand side) (10 points) d) Solve the model, provide the resulting screenshot. Write down the solution: color-country assignment. (10 points)

Answer rating: 100% (QA)

a Define the decision variables you will need 2 different set of binary decision variables 5 points ... View the full answer