A Column-Generation and Branch-and-Cut Approach to the Bandwidth-Packing Problem

The telecommunications problem of assigning calls with point to point demand to a capacitated network where each call can be assigned to at most one path has been called the Bandwidth-Packing Problem. For a given network, with specified arc costs and arc capacities, one wishes to route calls (defined by a starting and ending point) through the network to maximize the profit from the calls routed. Each such call is single path routed and not all calls will be routed. We propose a branch-and-cut methodology coupled with column generation to optimally solve such problems. We examine the alternative approaches in the literature and explain how this new method takes the best of all components of methods suggested previously. The method we suggest is new in that it includes a linear programming-based heuristic for obtaining good lower bounds, uses lifted minimal covers that take into account special-ordered set constraints, and dynamically choose among three alternative branching strategies. In addition, whenever a new column is generated, it is lifted into all existing cuts. We also discuss the need to generate all tied optimal linear optimization solutions if one wishes to assure that the solution obtained is optimal. Our computational results provide solutions to problems previously unsolvable.