MANAGING CAPACITIES AND STRUCTURES IN STOCHASTIC NETWORKS

• US 20130018829A1
• Filed: 07/15/2011
• Published: 01/17/2013
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dieker, Antonius B., Ghosh, Soumyadip, Squillante, Mark S.
• Granted Patent: US 8,635,175 B2
• Time in Patent Office: Days
• US Class Current: 706/14
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A system, method and computer program product for managing capacities and structures in a stochastic network. The method includes mapping the stochastic network to a general analytic model, e.g., a Brownian model, decomposing the general analytic model of the stochastic network into a set of smaller general analytic models, determining the capacities/structures for the set of analytic models as an intermediate solution for the capacities/structures of the stochastic network; and, determining the capacities/structures for the stochastic network starting at the intermediate solution for the capacities/structures using simulation-based methods.

Claims

1. A computer-implemented method for managing structures in stochastic networks comprising:

creating a general analytical model for a stochastic network;

decomposing the general analytic model into a set of one or more decomposed analytic models;

generating an optimization problem based on one or more of;

capacities and structures in each of the one or more decomposed analytic models;

obtaining an approximate solution to the optimization problem including identifying a value for the one or more of capacities and structures for the set of analytic models as an intermediate solution for the one or more of;

capacities and structures of the stochastic network; and

,

determining the one or more of;

capacities and structures for the stochastic network based on the intermediate solution,

wherein a programmed processor device is configured to perform one or more of the creating, decomposing, generating, obtaining and determining

2. The computer-implemented method according to claim 1, further comprising:

running, via a processor device, one or more of;

numerical solutions and simulations to obtain parameters for the decomposed analytic models.

3. The computer-implemented method according to claim 1, wherein the determining the one or more of:

capacities and structures for the stochastic network further comprises;

converting an identified optimal value for the one or more of;

capacities and structures of the general analytical model to a corresponding value for the original stochastic network.

4. The computer-implemented method according to claim 1, wherein the general analytical model is a general Queueing Network model.

5. The computer-implemented method according to claim 1, wherein the general analytical model is a Brownian Motion network model.

6. The computer-implemented method according to claim 1, further comprising one or more of:

specifying an initial iterate value for the optimization variable of a capacity or structure to be optimized;

evaluating the network at a current iterate to determine the parameters of a functional form of the decomposed analytical model at the current iterate;

optimizing the decomposed analytical model to obtain a next iterate of the optimization variable (capacity/structure);

determining whether the next iterate meets a pre-determined stopping criteria, and;

returning the current iterate as the (approximate) optimal solution if the next iterate meets the pre-determined stopping criteria.

7. The computer-implemented method according to claim 6, further comprising:

setting a new iterate as a current value if the next iterate does not meet the pre-determined stopping criteria, and

repeating the evaluating, optimizing and determining stopping criteria steps at the current iterate value to determine the parameters of a functional form of the decomposition analytic model at the new iterate.

8. The computer-implemented method according to claim 6, wherein said stochastic network is represented as nodes, said method further including:

performing adaptive control to model the sharing of a service provided across multiple nodes of the stochastic network and one or more of;

executing a set of nodes in series, in parallel or, in any combination thereof.

9. The computer-implemented method according to claim 6, wherein the optimizing step reflects constraints placed on a decision process, the constraints comprising:

a fixed investment budget, minimum required service guarantees.

10. The computer-implemented method according to claim 1, further comprising:

determining the capacities over multiple time periods or over a continuum of time.

11. A system for managing structures in stochastic networks comprising:

a memory storage device;

a processor device coupled to the memory storage device and configured to perform a method comprising;

creating a general analytical model for a stochastic network;

decomposing the general analytic model into a set of one or more decomposed analytic models;

generating an optimization problem based on one or more of capacities and structures in each of the one or more decomposed analytic models;

obtaining an approximate solution to the optimization problem including identifying a value for the one or more of;

capacities and structures for the set of analytic models as an intermediate solution for the one or more of;

capacities and structures of the stochastic network; and

,

determining the one or more of;

capacities and structures for the stochastic network based on the intermediate solution.

12. The system according to claim 11, further comprising:

running, via the processor device, one or more of;

numerical solutions and simulations to obtain parameters for the decomposed analytic models.

13. The system according to claim 11, wherein the determining the one or more of:

capacities and structures for the stochastic network further comprises;

converting an identified optimal value for the one or more of;

capacities and structures of the general analytical model to a corresponding value for the original stochastic network.

14. The system according to claim 11, wherein the general analytical model is a general Queueing Network model.

15. The system according to claim 11, wherein the general analytical model is a Brownian Motion network model.

16. The system according to claim 11, wherein the further comprising one or more of:

specifying an initial iterate value for the optimization variable of a capacity or structure to be optimized;

evaluating the network at a current iterate to determine the parameters of a functional form of the decomposed analytical model at the current iterate;

optimizing the decomposed analytical model to obtain a next iterate of the optimization variable (capacity/structure);

determining whether the next iterate meets a pre-determined stopping criteria, and;

returning the current iterate as the (approximate) optimal solution if the next iterate meets the pre-determined stopping criteria.

17. The system according to claim 16, further comprising:

setting a new iterate as a current value if the next iterate does not meet the pre-determined stopping criteria, and

repeating the evaluating, optimizing and determining stopping criteria steps at the current iterate value to determine the parameters of a functional form of the decomposition analytic model at the new iterate.

18. The system according to claim 16, wherein said stochastic network is represented as nodes, said method further including:

performing adaptive control to model the sharing of a service provided across multiple nodes of the stochastic network and one or more of;

executing a set of nodes in series, in parallel or, in any combination thereof.

19. The system according to claim 16, wherein the optimizing step reflects constraints placed on a decision process, the constraints comprising:

a fixed investment budget, minimum required service guarantees.

20. The system according to claim 16, wherein the capacities are determined over multiple time periods or over a continuum of time.

21. A computer program product for managing structures in stochastic networks, the computer program product comprising a storage medium readable by a processing circuit and storing instructions run by the processing circuit for performing a method to:

create a general analytical model for a stochastic network;

decompose the general analytic model into a set of one or more decomposed analytic models;

generate an optimization problem based on one or more of capacities and structures in each of the one or more decomposed analytic models;

obtain an approximate solution to the optimization problem including identifying a value for the one or more of;

capacities and structures for the set of analytic models as an intermediate solution for the one or more of;

capacities and structures of the stochastic network; and

,

determine the one or more of;

capacities and structures for the stochastic network based on the intermediate solution

22. The computer program product according to claim 21, further comprising:

running, via a processor device, one or more of;

numerical solutions and simulations to obtain parameters for the decomposed analytic models.

23. The computer program product according to claim 21, wherein the determining the one or more of:

capacities and structures for the stochastic network further comprises;

converting an identified optimal value for the one or more of;

capacities and structures of the general analytical model to a corresponding value for the original stochastic network.

24. The computer program product according to claim 21, further comprising one or more of:

specifying an initial iterate value for the optimization variable of a capacity or structure to be optimized;

evaluating the network at a current iterate to determine the parameters of a functional form of the decomposed analytical model at the current iterate;

optimizing the decomposed analytical model to obtain a next iterate of the optimization variable (capacity/structure);

determining whether the next iterate meets a pre-determined stopping criteria, and;

returning the current iterate as the approximate optimal solution if the next iterate meets the pre-determined stopping criteria

25. The computer program product according to claim 24, further comprising:

setting a new iterate as a current value if the next iterate does not meet the pre-determined stopping criteria, and

repeating the evaluating, optimizing and determining stopping criteria steps at the current iterate value to determine the parameters of a functional form of the decomposition analytic model at the new iterate.