Stochastic Activity Network

See the simopt.models.san module for API details.

Model: Stochastic Activity Network (SAN)

Description

Consider a stochastic activity network (SAN) where each arc \(i\) is associated with a task with random duration \(X_i\). Task durations are independent. SANs are also known as PERT networks and are used in planning large-scale projects.

An example SAN with 13 arcs is given in the following figure:

Sources of Randomness

Task durations are exponentially distributed with mean \(\theta_i\).

Model Factors

num_nodes: Number of nodes.
- Default: 9
arcs: List of arcs.
- Default: [(1, 2), (1, 3), (2, 3), (2, 4), (2, 6), (3, 6), (4, 5),
  (4, 7), (5, 6), (5, 8), (6, 9), (7, 8), (8, 9)]
arc_means: Mean task durations for each arc.
- Default: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Responses

longest_path_length: Length/duration of the longest path.

References

This model is adapted from Avramidis, A.N., Wilson, J.R. (1996). Integrated variance reduction strategies for simulation. Operations Research 44, 327-346. (https://pubsonline.informs.org/doi/abs/10.1287/opre.44.2.327)

Optimization Problem: Minimize Longest Path Plus Penalty (SAN-1)

Decision Variables

arc_means

Objectives

Suppose that we can select \(\theta_i > 0\) for each \(i\), but there is an associated cost. In particular, we want to minimize \(ET(\theta) + f(\theta)\), where \(T(\theta)\) is the (random) duration of the longest path from \(a\) to \(i\) and \(f(\theta) = \sum_{i=1}^{n}\theta_i^{-1}\) where \(n\) is the number of arcs.

The objective function is convex in \(\theta\). An IPA estimator of the gradient is also given in the code.

Constraints

We require that \(theta_i > 0\) for each \(i\).

Problem Factors

budget: Max # of replications for a solver to take.
- Default: 10000
arc_costs: Cost associated to each arc.
- Default: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

Fixed Model Factors

N/A

Starting Solution

initial_solution: (8,) * 13

Random Solutions

Sample each arc mean uniformly from a lognormal distribution with 2.5- and 97.5-percentiles at 0.1 and 10 respectively.

Optimal Solution

Unknown

Optimal Objective Function Value

Unknown

Optimization Problem: Minimize Longest Path Plus Penalty with Stochastic Constraints (SAN-2)

Decision Variables

arc_means

Objectives

Suppose that we can select \(\theta_i > 0\) for each \(i\), but there is an associated cost. In particular, we want to minimize:

\[\mathbb{E}[T(\theta)] + f(\theta),\]

where \(T(\theta)\) is the (random) duration of the longest path from node \(a\) to node \(i\), and

\[f(\theta) = \sum_{i=1}^{n} \theta_i^{-1},\]

where \(n\) is the number of arcs.

The objective function is convex in \(\theta\).