Network Loading Problem: Valid inequalities from 5- and higher partitions

This paper addresses the well-known Network Loading Problem, and develops several large new classes of valid inequalities based on p-partitions of the graph. The total capacity inequalities are obtained by recursively applying a simple C-G procedure to the cut inequalities, and can be efficiently computed for p-partitions with p ≤ 10. Another class of inequalities called one-two inequalities are separated by solving a sequence of LPs, heuristically modifying the LHS coefficients of the inequality until a violated inequality is found. The spanning tree inequalities are based on a simple observation that if the demand graph of a problem is connected, the solution must be at least a tree, i.e. have (n−1) or more edges. The conditions under which these inequalities are facet-defining are analyzed. The effectiveness of these inequalities in obtaining substantially tighter bounds and reduced solutions times is demonstrated via several computational experiments. More than 10-fold reduction in the solution time is obtained on several benchmark problems.