Patent ID: 7978629
Filing Date: 2011-07-12
Classification: H04L

Abstract:
1. A method for installing a conveyance linking a service provider location with customer locations selected from potential customer locations located on potential conveyance routes, the installed conveyance comprising a network yielding a total profit within a predetermined bound of a maximum possible total revenue, each potential customer location being associated with a potential customer revenue and each potential conveyance route being associated with a potential cost of the conveyance, the method comprising: formulating an optimization problem for the network as a prize-collecting Steiner tree problem in graphs (PCSPG) with potential conveyance routes x replacing each y dualizing a subset of the GSEC inequalities in a Lagrangian fashion; in a computer processor, performing the following in a subgradient method (SM) iteration k on a solution ( if the iteration has not been terminated and if an iteration limitation criterion has not been reached, then initiating a new iteration; if the iteration has been terminated, or if the iteration limitation criterion has been reached, then outputting an optimal or near-optimal solution to the PCSPG; and installing the conveyance along selected potential conveyance routes according to the output solution.