Monte Carlo Simulation

Monte Carlo simulation is a powerful statistical technique used to model uncertainty and variability in complex systems.

Image by bobstanke

Introduction

It has broad applications in operations research (OR), where decision-making under uncertainty is a fundamental challenge. This article explores the significance of Monte Carlo simulation and its role in OR, accompanied by a breakdown of key code implementations and real-world applications.

What is Monte Carlo Simulation?

Monte Carlo simulation uses random sampling to approximate numerical results. It is particularly useful for evaluating integrals, optimizing systems, and assessing risk. The technique is based on running multiple iterations with different random inputs to estimate probabilities and expected values.

The name “Monte Carlo” originates from the famous casino in Monaco, emphasizing the role of randomness in the method. This approach is widely applied in physics, engineering, finance, and operations research to solve problems that are difficult or impossible to compute deterministically.

Monte Carlo Simulation in Operations Research

Operations research involves optimizing processes in logistics, supply chain management, finance, and other fields. Monte Carlo simulation aids in:

• Risk Analysis: Evaluating uncertain outcomes in supply chain networks by simulating different demand, lead time, and inventory scenarios.
• Decision-Making: Providing probabilistic insights for inventory management and scheduling, helping companies prepare for best- and worst-case scenarios.
• Optimization: Enhancing efficiency in stochastic environments where deterministic models fail, particularly in resource allocation and transportation planning.

Monte Carlo methods allow OR practitioners to analyze systems with high uncertainty and make more informed decisions based on simulated results.

Code Explanation: Monte Carlo Integration

Monte Carlo integration is a fundamental technique for estimating functions where direct calculation is impractical. The following C++ code demonstrates the application of Monte Carlo integration.

#include <iostream>
#include <cstdlib>
#include <cmath>

double myFunction(double x);
void monteCarloEstimateSTD(double lowBound, double upBound, int iterations, double mcStats[]);

int main() {
    double lowerBound = 1, upperBound = 5;
    int iterations;
    double mcStats[2];

    for (int i = 1; i < 6; i++) {
        iterations = 2 * pow(4, i);
        monteCarloEstimateSTD(lowerBound, upperBound, iterations, mcStats);
        printf("Estimate for %.1f -> %.1f is %.3f, STD = %.4f, (%i iterations)\n", lowerBound, upperBound, mcStats[0], mcStats[1], iterations);
    }
    return 0;
}

double myFunction(double x) {
    return pow(x, 4) * exp(-x);
}

void monteCarloEstimateSTD(double lowBound, double upBound, int iterations, double statsArray[]) {
    double totalSum = 0, totalSumSquared = 0;
    int iter = 0;

    while (iter < iterations - 1) {
        double randNum = lowBound + (float(rand()) / RAND_MAX) * (upBound - lowBound);
        double functionVal = myFunction(randNum);
        totalSum += functionVal;
        totalSumSquared += pow(functionVal, 2);
        iter++;
    }
    double estimate = (upBound - lowBound) * totalSum / iterations;
    double expected = totalSum / iterations;
    double expectedSquare = totalSumSquared / iterations;
    double std = (upBound - lowBound) * pow((expectedSquare - pow(expected, 2)) / (iterations - 1), 0.5);

    statsArray[0] = estimate;
    statsArray[1] = std;
}

This code integrates a given function using Monte Carlo methods by:

1. Generating random numbers within the integration bounds.
2. Evaluating the function at these random points.
3. Estimating the integral as the average function value multiplied by the range.
4. Computing the standard deviation to measure uncertainty.

Importance Sampling

Another method, importance sampling, enhances efficiency by focusing on more probable outcomes. The following function applies importance sampling in Monte Carlo integration:

void monteCarloEstimateImportance(double lowBound, double upBound, int iterations, double statsArray[]) {
    std::default_random_engine generator;
    std::normal_distribution<double> distribution(3, 1.0);
    double totalSum = 0, totalSumSquared = 0;
    int iter = 0;
    double randNum, functionVal, weight;

    while (iter < iterations - 1) {
        randNum = distribution(generator);
        weight = (1 / (upBound - lowBound)) / myPDF(randNum);
        functionVal = myFunction(randNum) * weight;
        totalSum += functionVal;
        totalSumSquared += pow(functionVal, 2);
        iter++;
    }
    double estimate = (upBound - lowBound) * totalSum / iterations;
    double expected = totalSum / iterations;
    double expectedSquare = totalSumSquared / iterations;
    double std = (upBound - lowBound) * pow((expectedSquare - pow(expected, 2)) / (iterations - 1), 0.5);
    statsArray[0] = estimate;
    statsArray[1] = std;
}

Real-World Applications of Monte Carlo in OR

Monte Carlo methods are widely used in real-world OR applications, including:

• Supply Chain Management: Simulating demand variability and production lead times to optimize inventory levels.
• Project Management: Estimating project completion times under uncertainty using Monte Carlo-based PERT analysis.
• Finance: Pricing complex financial derivatives by simulating future market conditions.
• Healthcare Operations: Predicting patient flow and resource allocation in hospitals.

NivedRajeev on Wikimedia

Conclusion

Monte Carlo simulation is invaluable in operations research for dealing with uncertainty, optimizing processes, and improving decision-making. It allows businesses and researchers to model complex stochastic systems with high variability, making it a vital tool for industries such as logistics, finance, healthcare, and engineering. By incorporating Monte Carlo techniques, OR practitioners can make better data-driven decisions, ultimately leading to more efficient and robust solutions.

References

1. Bellman, R. (1957). Dynamic programming. Princeton University Press.
2. Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization. Athena Scientific.
3. Filar, J. A., & Vrieze, K. (1997). Competitive Markov decision processes. Springer.
4. Hillier, F. S., & Lieberman, G. J. (2021). Introduction to operations research (11th ed.). McGraw-Hill Education.
5. Jensen, P. A., & Bard, J. F. (2003). Operations research: Models and methods. John Wiley & Sons.
6. Kemeny, J. G., & Snell, J. L. (1976). Finite Markov chains. Springer.
7. Luenberger, D. G., & Ye, Y. (2015). Linear and nonlinear programming (4th ed.). Springer.
8. Puterman, M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons.
9. Ross, S. M. (2014). Introduction to probability models (11th ed.). Academic Press.