How do you incorporate uncertainty and randomness in linear programming models?

To incorporate uncertainty and randomness in linear programming models, you can use the following approaches: Stochastic Programming: Model uncertainties explicitly by including random variables in the constraints and objective function, typically using scenario-based approaches. Robust Optimization: Formulate the problem to be feasible under a range of possible scenarios, ensuring solutions remain optimal or near-optimal despite uncertainty. Chance-Constrained Programming: Introduce probabilistic constraints that must be satisfied with a certain probability, allowing for controlled risk levels.

As others noted, stochastic programming is the right answer for most of the cases but it is less developed and more computationally demanding compared to classical LP. A less standard approach can be of using LP, solved for multiple instances such that each instance is sampled in a stochastic manner. After solving the LP multiple times, one will have a distribution of the solutions. Importantly, this distribution does not promise a sample out of it is optimal in the LP sense so one should make post-analysis in this approach

1. Handling Uncertainty: Robust optimization aims to find solutions that perform well across various scenarios of uncertain parameters. 2. Min-Max Formulation: These models are often formulated as min-max or min-max regret problems, minimizing the worst-case outcome or the regret of the objective function over different scenarios. 3. Trade-offs: While robust optimization ensures reliability under uncertainty, it can lead to overly conservative and costly solutions that may not be practical.

Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR) Optimisation risk measures are incorporated into stochastic programming to manage the risk of extreme losses in financial applications. VaR specifies the maximum loss over a given time for a given confidence level, while CVaR provides the expected loss exceeding the VaR. In a project focused on portfolio risk management, we utilised CVaR optimisation within a stochastic programming framework to construct investment portfolios that minimised the expected loss in the worst-case scenarios, providing a more risk-averse strategy compared to focusing solely on expected returns.

When leveraging LP relaxation for randomized rounding, you might want to consider following up with simulated annealing instead. While handling the parameter tuning associated with this kind of technique will take a significant amount of work, the implementation can handle a wide variety of these kinds of problems and will help you avoid local optima. The iterative refining of the solution space through exploration optimization provides a more controlled approach to these problems at the potential cost of computational time complexity. Overall, this is just a potential hybrid approach to consider.

In dual stochastic programming, uncertainty is incorporated into the dual variables rather than the primal variables, which can be particularly effective when combined with column generation. This approach involves adjusting the dual prices in response to randomness in the constraints. In a resource allocation model I worked on, dual stochastic column generation allowed for the dynamic adjustment of resource prices based on fluctuating availability, ensuring efficient allocation under uncertain supply conditions. Parameterized Column Generation technique involves parameterizing columns generated during the optimization process to account for uncertainty.