Abstract: For a series of practical optimization problems, we show that formulating them as graph optimization problems enables the development of competitive algorithms. The problems considered are known as: protein threading problem, contact map overlap, HP folding, a new scheduling theory problem, classification problem and the biclustering problem. The focus is on formulating them as graph optimization problems, which are solved by using Integer programming techniques.