COMB INEQUALITIES FOR THE DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM
The Degree Constrained Minimum Spanning Tree Problem (DCMST) is a problem of finding the minimum spanning tree in a given weighted graph (all weights are non negative), whilst also satisfies the degree requirement in every vertex. Since the DCMST can be formulated as MILP, then all constraints are valid inequalities, and among those constraints some are facets defining. In this paper we will discuss how to find constraints that constitute comb inequalities for the DCMST for vertex order 5 to 15 with increments 1.
Keywords: degree constrained, minimum spanning tree, valid inequality, facet, comb
Article MetricsAbstract view : 604 times
PDF - 305 times
- There are currently no refbacks.