Patent ID: 8706882

Claim:
An apparatus for allocating devices to a communication route, comprising: a memory for storing network topology information defining the communication route, and device information including a device-cost assigned to each of a plurality of candidate-devices that may be allocated to a plurality of segments on the communication route; and a processor to: generate an integer/linear programming problem for obtaining a feasible device-allocation allowing the candidate-devices to be allocated to the communication route under constraints determined based on the network topology information and the device information, the integer/linear programming problem defining an objective function for calculating an objective function value, generate a sequence of feasible device-allocations, by sequentially generating a next feasible device-allocation from a current feasible device-allocation while improving the objective function value until the objective function value is not improved any more, and determine a last one of the sequence of feasible device-allocations to be an optimum device-allocation having an optimum objective function value, wherein the next feasible device-allocation is generated by replacing a basic candidate-device being used for the current feasible device-allocation with an alternative candidate-device so as to improve the objective function value, the alternative candidate-device being selected, from nonbasic candidate-devices not being used for the current feasible device-allocation, based on reduced-costs calculated for the nonbasic candidate-devices, a reduced-cost indicating a degree of a change in the objective function value when the change is caused by replacing a basic candidate-device with a nonbasic candidate-device having the reduced-cost.