Introducción a la optimización robusta

Abstract

Sometimes, we may found a decision problem, different situations in which we have different options and we must decide. The treatment we must give to the problem must take into account the frequency with which the decision maker is in that situation. Sometimes, it may be appropriate to use expected values whereas other times it may not be a good choice. If we speak of decisions that must be made in concrete situations that will not be repeated, at least under the same probabilistic conditions, such as evacuations, emergency services assistance, etc, the decision criterion should not be to select the least expected cost. In this way, the stochastic programming may not be able to satisfy the requirements of decision making in decision environments characterized by significant uncertainty since it requires assigning probability distributions to the scenarios considered. This is not a trivial exercise for many decision makers because in many cases it can be difficult to calculate the probability of a future scenario occurring when the related factors refer to the behavior of companies, agencies or governments for which we do not have information. In other cases, changes in the attitudes and priorities of potential clients related to the decision problem may have to be considered. The approach followed in this work, unlike that used in stochastic programming, has the objective of protecting the decision maker without using a probability model on the performance of the system. In the framework of robustness, what the decision maker wants is not the optimal long-term or optimal for a single scenario (although it is the most likely scenario), but a decision that works well in all cases. So a robust decision will be one that is characterized by significant uncertainty, works well in all cases and is protected against the worst possible scenarios. The robust discrete optimization problems are in general more difficult to solve than their deterministic counterparts. The major source of complexity comes from the extra degree of freedom - the scenario set. For many polynomially solvable classical optimization problems such as assignment, minimum spanning tree, shortest path, resource allocation, single machine scheduling with sum of flow times criterion, their corresponding robust versions are weakly or strongly NP-hard. The problems we will see have a high complexity, so we will see a numerical method of resolution that can be stopped before reaching the optimum that will lead us to a ε−optimal solution. With this approach we can obtain a method that is computationally more efficient in order to compute good solutions in real life problems.