Application of linear programming to the optimal difference triangle set problem

Difference triangle sets have a number of applications in telecommunications. The authors describe a linear programming model for finding improved lower bounds on the size of such sets. Two integer linear programming formulations for finding minimal difference triangle sets are presented. The linear programming relaxation of the second formulation is strengthened with a family of valid inequalities and solved to yield improved lower bounds. Numerical results for selected difference triangle sets are given