Application of Graph Theory to the Solution of a Nonlinear Optimal Assignment Problem

Consider a process in which at each stage an originating center must be connected to exactly one of a set of terminating centers. The originating center has a load and each terminating center has a capacity. The originating center can be connected to a terminating center only if the terminating center has enough capacity for its load. The originating center's load and the terminating centers' capacities vary with time (i.e., from one stage to another), but they are assumed to be known at all times. The problem is to determine the optimal connection configuration at each stage of time. The costs involved are the transmission cost and the rearrangement cost. Both costs are nonlinear functions of the originating center's load. The transmission cost is the cost of connection of the originating center to a terminating center. The rearrangement cost is incurred if, in transition from one stage to the next, the connection of the originating center to a terminating center has to be changed because of insufficient capacity. Such an assignment problem may be encountered in many applications. One important application arises in the design of hierarchical telephone networks.1-3 The process of connecting a switching center to a center in the next level of hierarchy in the backbone route of such networks is called homing. The problem of determining the optimal homing configuration of a switching center over several stages during a study period can be formulated as the above assignment problem.4 1863