Coloracao de Grafos - Algoritmo para Otimizacao Discreta

Discrete Optimization Assignment Graph Coloring 1 Problem Statement In this assignment you will design an algorithm to find the smallest coloring of a graph1 You are provided with a graph and your task is to label the graphs nodes with as few colors as possible such that all pairs of nodes joined by an edge do not have the same color Figure 1 illustrates a graph and a three coloring of that graph The nodes of the graph are labeled with black numbers while the coloring of the graph is labeled with white numbers You may notice that a three coloring is not a minimal coloring of this graph In fact a two coloring is possible 0 1 2 3 a A graph 0 1 2 2 0 1 2 3 b A threecoloring of the graph Figure 1 A Graph Coloring Example 2 Assignment Write an algorithm to minimize the coloring of a graph The problem is mathematically formulated in the following way Given a graph G N E with nodes N 0 n 1 and edges E let ci N be a variable denoting the color of node i Then the graph coloring problem is formalized as the following optimization problem minimize max i0n1 ci subject to ci cj i j E 3 Data Format Specification The input consists of E 1 lines The first line contains two numbers N and E It is followed by E lines each line represents an edge ui vj where ui vj 0 N 1 1See httpmathworldwolframcomChromaticNumberhtml 1 Input Format N E u0 v0 u1 v1 uE1 vE1 The output has two lines The first line contains two values obj and opt obj is the numbers of colors used in the coloring ie the objective value opt should be 1 if your algorithm proved optimality and 0 otherwise The next line is a list of n values in N one for each of the ci variables This line encodes the solution Output Format obj opt c0 c1 c2 cn1 Examples based on Figure 1 Input Example 4 3 0 1 1 2 1 3 Output Example 3 0 0 1 2 2 4 Instructions Edit solverpy and modify the solve itinput data function to solve the optimization problem described above The function argument input data contains the problem data in the format described above The return value of solve it is a solution to the problem in the output format described above Your solve it implementation can be tested with the command python solverpy datainputFileName You should limit the solve it method to terminate within 5 hours otherwise the submission will not be eligible for full credit You may choose to implement your solver directly in python or modify the solve it function to call an external application Resources You will find several graph coloring instances in the data directory provided with the handout 2 Handin Run submitpy with the command python submitpy Follow the instructions to apply your solve it method on the various assignment parts You can submit multiple times and your grade will be the best of all submissions However it may take several minutes before your assignment is graded please be patient You can track the status of your submission on the feedback section of the assignment website Grading Infeasible solutions ie those that do not conform to the output format or violate problem constraints will receive 0 points Feasible solutions will receive at least 3 points Feasible solutions passing a low quality bar will receive at least 7 points and solutions meeting a high quality bar will receive all 10 points The grading feedback indicates how much your solution must improve to receive a higher grade Collaboration Rules In all assignments we encourage collaboration and the exchange of ideas on the discussion forums However please refrain from the following 1 Posting code or pseudocode related to the assignments 2 Using code which is not your own 3 Posting or sharing problem solutions Discussion of solution quality ie objective value and algorithm performance ie run time is allowed and the assignment leader board is designed to encourage such discussions Warnings 1 It is recommended you do not modify the data directory Modifying the files in the data directory risks making your assignment submissions incorrect 2 You cannot rename the solverpy file or the solve it method 3 Be careful when using global variables in your implementation The solve it method will be run repeatedly and it is your job to clear the global data between runs 4 solverpy must remain in the same directory as submitpy Hint The optimal value for datagc 1000 5 is near 85 5 Technical Requirements You will need to have python 279 or 35 at least installed on your system installation instruc tions httpwwwpythonorgdownloads 3