Integer linear programming formulations for treewidth

In this paper we consider an ILP-based approach to tackle the problem of determining a treewidth of the graph. We give an overview of existing attempts and develop further LP-based techniques for the problem. We present two different ILP formulations for the treewidth. To obtain the first one we merge the chordalization-based ILP by Koster and Bodlaender and flow metrics approach by Bornstein and Vempala. The second brand-new ILP is based on the structural properties of the tree-decomposition. It has a nice application of the local branching techniques by Fischetti and Lodi.