Article ID: | iaor2008457 |
Country: | United Kingdom |
Volume: | 14 |
Issue: | 2 |
Start Page Number: | 105 |
End Page Number: | 121 |
Publication Date: | Mar 2007 |
Journal: | International Transactions in Operational Research |
Authors: | Mak Vicky |
This paper studies the polytope of the minimum-span graph labelling problems with integer distance constraints (DC-MSGL). We first introduce a few classes of new valid inequalities for the DC-MSGL defined on general graphs and briefly discuss the separation problems of some of these inequalities. These are the initial steps of a branch-and-cut algorithm for solving the DC-MSGL. Following that, we present our polyhedral results on the dimension of the DC-MSGL polytope, and that some of the inequalities are facet defining, under reasonable conditions, for the polytope of the DC-MSGL on triangular graphs.