Robust Linear Programming
Taking an example of an optimization problem with two linear constraints, we se that they generally are of the form:
The optimal will be right at the edge of the feasible region. This gives us very little wiggle room and is generally not very flexible under uncertain scenarios.
So a solution is to define uncertainty regions:
Thus now the problem is maximizing the variables under an uncertain region. This can be thought of as minimaxing against an adversary.
However the solutions from this approach can be too conservative due to the adversary being unrestricted. To amend this we can impose a budget on the adversary:
This is a more appropriate outcome that is consistent with real-world scenarios. This is already implicitly accounted for in a lot of optimization models via the inclusion of regularization. However it is always good practice to include robustness parameters when designing your algorithm to account for unexpected uncertainty that no one could have seen coming.
Until next time.