Multiplex communications – Network configuration determination
Reexamination Certificate
2011-07-12
2011-07-12
Kumar, Pankaj (Department: 2467)
Multiplex communications
Network configuration determination
C370S255000, C370S396000
Reexamination Certificate
active
07978629
ABSTRACT:
A method determines an optimal or near-optimal conveyance network layout in which revenue from serviced customer locations is maximized while the cost of installing and/or maintaining the conveyance is minimized. The conveyance may, for example, be a fiber optic telecommunications cable or a power or utility distribution system. Algorithms in the method generate primal and dual bounds in a Prize-Collecting Steiner Tree Problem in Graphs (PCSPG). Those algorithms originate from a Lagrangian Non-Delayed Relax-and-Cut (NDRC) based approach and incorporate ingredients such as a new PCSPG reduction test, an effective Local Search procedure and a modification in the NDRC framework that allows additional reductions in duality gaps to be attained.
REFERENCES:
patent: 2006/0146716 (2006-07-01), Lun et al.
Alexandre Salles de Cunha, et al.; “A Relax-And-Cut Algorithm for the Prize-Collecting Steiner Problem in Graphs”, Discrete Applied Mathematics; vol. 157, Issue 6, pp. 1198-1217, Mar. 28, 2009.
Abilio Lucena, et al.; “Strong Lower Bounds for the Prize-Collecting Steiner Problem in Graphs” Discrete Applied Mathematics, pp. 277-294, 2004.
Mohamed Haouari, et al.; “A Hybrid Lagrangian Genetic Algorithm for the Prize Collecting Steiner Tree Problem”, Computers and Operations Research, pp. 1274-1288, 2006.
Abilio Lucena, “Non Delayed Relax-and Cut Algorithms”, Annals of Operations Research, 140, pp. 375-410, 2005.
Egon Balas; “The Prize Collecting Traveling Salesman Problem”; Networks, vol. 19, pp. 621-636, 1989.
Alexandre Salles da Cunha, et al.; “Lower and Upper Bounds for the Degree-Constrained Minimum Spanning Tree Problem”; Networks, pp. 55-66, 2007.
Arie Segev; The Node-Weighted Steiner Tree Problem; Networks, vol. 17, pp. 1-17, 1987.
Celso C. Ribeiro, et al.; “Tabu Search for the Steiner Problem in Graphs”; Networks, vol. 36(2), pp. 138-146, 2000.
J. E. Beasley; “An Algorithm for the Steiner Problem in Graphs”; Networks, vol. 14, pp. 147-159, 1984.
Cees Duin et al.; “Efficient Path and Vertex Exchange in Steiner Tree Algorithms”; Networks, pp. 89-105, 1997.
Abillio Lucena; “Steiner Problem in Graphs: Lagrangean Relaxation and Cutting-Planes”; Netflow93; pp. 147-154; 1993.
Alexandre Salles da Cunha, et al.; “A Relax and Cut Algorithm for the Prize Collecting Steiner Problem in Graphs”; Mathematical Programming in Rio; pp. 72-78; Nov. 9-12, 2003.
da Cunha Alexandre Salles
de Carvalho Resende Mauricio Guilherme
Lucena Abilio
Maculan Nelson
AT&T Intellectual Property I L.P.
Kumar Pankaj
Tsegaye Saba
LandOfFree
Method for network design to maximize difference of revenue... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for network design to maximize difference of revenue..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for network design to maximize difference of revenue... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2674609