Hello guys.
I should do branch and bound on vertex coloring.
Lower bound function: Let S be a partial solution, in which we have assigned colours to vertices 1, 2, …, i. Our lower bound on the best possible solution obtainable from S must obviously include the number of colours used so far … can we do better? Maybe. We can scan the vertices not yet coloured. If any of them are adjacent to vertices covering the full set of colours used so far, then we will need at least one more colour. If any such vertices are also ajacent to each other, we will need at least two more colours. This test would take O(n^2) time, but since we are doomed to exponential time in the worst case anyway, spending O(n^2) to help reduce the tree is probably worthwhile.
So we can define L(S) = “number of colours used so far” + “number of colours we will be forced to use in the future”
Remember that the second part of L(S) doesn’t have to be exact - but it must be a true lower bound. That is, if it is not exact it must be less than the exact value.
Upper bound function: Let S be a partial solution, in which we have assigned colours to vertices 1, 2, …, i. As a simple upper bound on the number of colours used in the best solution obtainable from S, we could use U(S) = “number of colours used so far” + “number of vertices not yet coloured”, since the worst thing that could happen is that each remaining vertex needs its own colour. However, we can try to do better. If we apply any kind of heuristic (such a Greedy-style heuristic based on “for each remaining vertex, choose the legal colour that has been used the most often (note that the legal colours for each vertex may change as we go along)”) we have a chance of arriving at a solution that uses close to the optimal number of colours. If we are fortunate, this will give us a relatively tight upper bound on the optimal solution.
So we can define U(S) = “number of colours used so far” + “number of colours used to colour the remaining vertices by applying the Greedy heuristic”.
I’m having problem with implementation. I alredy did Local search on vertex coloring and partial simulated annealing. If someone could help me implement branch and bound,i’d be very thankful.
If someone is interested how these 2 look like,i’d gladly post my soultions. ( variable names and class names and method names are all written in bosnian 
)
Thanks guys.