Minimum split coloring

Abstract

Combinatorial optimization is a very important branch of optimization eld. 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 nite set of solutions, examination of this solution space is not easy to accomplish in many problems. Graph theory is one of the most studied elds in optimization for decades. There is a huge literature on this eld with very di erent approaches. One of the most famous problems in this eld 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 di cult to nd an e cient way to solve it. Column generation method embedded in a branch-and-bound tree is a success story in dealing with di cult 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.