Minimum split coloring

Combinatorial optimization is a very important branch of optimization field. Many problems in the real world such as transportation, scheduling, production, and telecommunication can be modeled as a combinatorial optimization problem. Although a combinatorial optimization problem has a finite set of solutions, examination of this solution space is not easy to accomplish in many problems. Graph theory is one of the most studied fields in optimization for decades. There is a huge literature on this field with very different approaches. One of the most famous problems in this field is the graph coloring problem. This is due to the fact that it has a wide range of applications but in the same time, it is extremely difficult to find an efficient way to solve it. Column generation method embedded in a branch-and-bound tree is a success story in dealing with difficult optimization problems. In most of the cases, it is better than the enumeration of the solution space and dynamic programming solution method in combinatorial optimization problems. In this thesis, we consider a generalization of the graph coloring problem called Minimum Split Coloring Problem which covers an even wider application area. We develop a column generation method embedded in a branch-and-bound tree to solve the Minimum Split Coloring Problem exactly in general graphs.