Managing capacities and structures in stochastic networks

• US 8,635,175 B2
• Filed: 07/15/2011
• Issued: 01/21/2014
• Est. Priority Date: 07/15/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dieker, Antonius B., Ghosh, Soumyadip, Squillante, Mark S.
• Primary Examiner(s): CHANG, LI WU
• Application Number:
  US13/183,869
• Publication Number:
  US 20130018829A1
• Time in Patent Office: 921 Days
• Field of Search: None
• 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 capacities and a topological configuration of network structures in each of the one or more decomposed analytic models;

iteratively obtaining an approximate solution to the optimization problem by;

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

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

jointly optimizing the decomposed analytical models with the determined parameters to obtain a next iterate of the optimization variables of the capacities and network structures;

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

returning the current iterate as values for the capacities and network structures as an approximate solution if the next iterate meets the pre-determined stopping criteria;

or

setting new iterate values for optimization variables of the capacities and the network structures to be optimized as current iterate values and repeating the evaluating, jointly optimizing and stopping criteria determining at the current iterate values to determine the parameters of the functional form of each decomposed analytic model; and

determining the capacities and the topological configuration of network structures for the stochastic network based on the approximate solution,

wherein a programmed hardware processor device is configured to perform one or more of the creating, decomposing, generating, specifying, evaluating, jointly optimizing and stopping criteria determining.

2. The computer-implemented method according to claim 1, wherein said network evaluating comprises:

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

numerical solutions and simulations to obtain parameters for the functional form of each decomposed analytic model.

3. The computer-implemented method according to claim 1, wherein the determining the capacities and the topological configuration of the structures for the stochastic network further comprises:

converting an identified optimal value for the capacities and topological configuration of the 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, wherein said stochastic network is represented as nodes, said method further including:

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

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

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

a fixed investment budget, minimum required service guarantees.

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

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

9. The method of claim 1 wherein said topological configuration of network structures represents an ordering of resources connected within the network that process a workflow.

10. The method of claim 1 wherein said topological configuration of network structures is one of a feasible set of network topological configurations, wherein in response to determining a next iterate does not meet a pre-determined stopping criteria, said method further including:

adaptively pruning network structures of said feasible set to reduce a number of potential network structures for consideration of optimization.

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

a memory storage device;

a hardware 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 decomposed analytic models;

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

iteratively obtaining an approximate solution to the optimization problem by;

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

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

jointly optimizing the decomposed analytical models with the determined parameters to obtain a next iterate of the optimization variables of the capacities and network structures;

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

returning the current iterate as values for the capacities and network structures as an approximate solution if the next iterate meets the pre-determined stopping criteria;

or

setting new iterate values for optimization variables of the capacities and the network structures to be optimized as current iterate values and repeating the evaluating, jointly optimizing and stopping criteria determining at the current iterate values to determine the parameters of the functional form of each decomposed analytic model; and

determining the capacities and the topological configuration of network structures for the stochastic network based on the approximate solution.

12. The system according to claim 11, wherein said network evaluating comprises:

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

numerical solutions and simulations to obtain parameters for the function of each decomposed analytic model.

13. The system according to claim 11, wherein the determining the capacities and the topological configuration of the structures for the stochastic network further comprises:

converting an identified optimal value for the capacities and topological configuration of the network 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 said stochastic network is represented as nodes, said method further including:

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

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

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

a fixed investment budget, minimum required service guarantees.

18. The system according to claim 11, wherein the capacities and structures are determined over multiple time periods or over a continuum of time.

19. The system of claim 11 wherein said topological configuration of network structures represents an ordering of resources connected within the network that process a workflow.

20. The system of claim 11 wherein said topological configuration of network structures is one of a feasible set of network topological configurations, wherein in response to determining a next iterate does not meet a pre-determined stopping criteria, said method further including:

adaptively pruning network structures of said feasible set to reduce a number of potential network structures for consideration of optimization.

21. A computer program product for managing structures in stochastic networks, the computer program product comprising a storage medium, said storage medium not a propagating signal, said 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 decomposed analytic models;

generate an optimization problem based on capacities and a topological configuration of network structures in each of the one or more decomposed analytic models,

iteratively obtain an approximate solution to the optimization problem by configuring said processing circuit to;

specify an initial iterate value for the optimization variable of a capacity and a network structure to be optimized;

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

jointly optimize the decomposed analytical models with the determined parameters to obtain a next iterate of the optimization variables of the capacities and network structures;

determine whether the next iterate meets a pre-determined stopping criteria, and one of;

return the current iterate as values for the capacities and network structures as an approximate solution if the next iterate meets the pre-determined stopping criteria;

or

set new iterate values for optimization variables of the capacities and the network structures to be optimized as current iterate values and repeat the evaluating, jointly optimizing and stopping criteria determining at the current iterate values to determine the parameters of the functional form of each decomposed analytic model;

and

determine the capacities and the topological configuration of network structures for the stochastic network based on the approximate solution.

22. The computer program product according to claim 21, wherein to evaluate the network comprises:

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

numerical solutions and simulations to obtain parameters for the function of each decomposed analytic model.

23. The computer program product according to claim 21, wherein the determining the capacities and topological configuration of the structures for the stochastic network further comprises:

converting an identified optimal value for the capacities and topological configuration of the network structures of the general analytical model to a corresponding value for the original stochastic network.

24. The computer program product of claim 21 wherein said topological configuration of network structures is one of a feasible set of network topological configurations, wherein in response to determining a next iterate does not meet a pre-determined stopping criteria, said method further including:

adaptively pruning network structures of said feasible set to reduce a number of potential network structures for consideration of optimization.