The One-Terminal TELPAK Problem

To lease long-distance telecommunications facilities, the lessee submits, for billing purposes, a configuration of individual channels and bulk units of channels, called TELPAKS, that implements his requirements. The bulk rate charged for a TELPAK results in the cost being a piecewise linear function of the number of channels. This leads to a network-synthesis problem with a nonlinear cost function that is neither concave nor convex. We give a characterization of an optimal solution and present a method for obtaining a low-cost configuration when all requirements are to a single point.