Stochastic problems where the uncertainty lies purely in the linear objective function are easy if all we want is to optimize expected performance. But what if the uncertainty affects the constraints?
Assume we can choose to work on ten different tasks. Each task has a fixed profit but an uncertain demand on the work hours involved. We are allowed to have overtime and work more than the available 267 regular hours. However, if we have overtime, no matter how little, we pay $100, and another $100 for every hour of overtime (or fractions thereof).
The actual work hours for each task we choose to take on are Gamma distributed as shown below (the two parameters (1,1) give shape and scale of the Gamma distribution).
What tasks 0 - 9 should we accept to maximize our expected profit?
For extra credit, consider the conditional value at risk 0.1% (i.e., the average performance of the 0.1% worst outcomes for your solution).
In this example, you could of course assess all 1024 possible selections of items. In general, however, you will require a solver that can search over uncertain outcomes. And that solver better be able to run hundreds of thousands of scenarios to assess the tail risk of 0.1%.
env = skr.Env("license.sio", runID=uID, processID=pID, stochastic=True) env.set_stochastic_parameters(int(1e5), 0) x = [env.ordinal(0,1) for i in range(n)] stoch_weights = [ w * (10 + env.gamma(1,1,100)) / 11 for w in weights] profits = env.convert(profits) W = env.scalar_product(x, stoch_weights) P = env.scalar_product(x, profits) profit = P - ((W>C) + env.max_0(W-C)) * 100 exp_profit = env.aggregate_mean(profit) cvar = env.aggregate_cvar(profit, 0.001, False) env.maximize(exp_profit, 1)
This small program quickly reveals the optimal choice for maximizing the mean profit is
Solution: [1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0]
Mean Profit: 282.83
CVaR-0.001: -1168.34
Optimizing for both CVaR and mean performance, we get
Solution: [0.0, 1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 1.0, 0.0, 0.0]
Mean Profit: 264.53
CVaR-0.001: -205.09
As always in life: with the right tool, tasks get much easier. Maybe it is time to augment your optimization toolbox?