Optimización bajo incertidumbre. Enfoques estocásticos y robustos aplicados al problema de la mochila

Abstract

La incertidumbre es inherente a los problemas reales y su adecuada incorporación en la optimización permite diseñar soluciones más sólidas y aplicables. No obstante, su tratamiento no es una tarea trivial, ya que, en general, no existe una formulación determinista única y tratable sin hipótesis adicionales. En este trabajo se analizan dos marcos fundamentales que reformulan o aproximan problemas con incertidumbre como problemas de optimización lineales (LP), cuyas soluciones óptimas son acordes a las características de la incertidumbre y a la actitud del decisor: la Programación Estocástica y la Optimización Robusta El Capítulo 1 introduce los enfoques estocásticos, desde el modelo clásico de una etapa hasta formulaciones multietapa. Se definen los árboles de escenarios así como dos vías estándar para hacer el problema estocástico tratable: la formulación determinista equivalente (para incertidumbre discreta y finita) y la aproximación por medias muestrales (SAA) (aplicable de forma general). Todos estos enfoques se aplican a un ejemplo ilustrativo común que actúa como hilo conductor y permite comparar cómo varía el valor objetivo al aumentar el número de etapas. Además, se discuten las principales ventajas y limitaciones de estos enfoques. El Capítulo 2 aborda la optimización robusta (RO). Se introduce el concepto de conjunto de incertidumbre y se estudian dos familias de especial relevancia: los conjuntos poliédricos (con énfasis en los conjuntos tipo caja como caso particular) y los conjuntos de tipo presupuesto. Se muestra su reformulación lineal y se aplica el marco al ejemplo ilustrativo para facilitar la comprensión y la comparación directa con los enfoques estocásticos...

Uncertainty is intrinsic to most practical problems due to the stochastic nature of real phenomena. Incorporating it into optimization models leads to solutions that are more realistic and perform better under unobserved scenarios. However, solving optimization problems under uncertainty is nontrivial, as there is generally no unique, tractable deterministic formulation without additional assumptions. This work presents, in a rigorous yet accessible manner, tools that reformulate or approximate uncertain problems as linear optimization problems (LP), whose optimal solutions align with both the characteristics of the uncertainty and the decision-maker’s risk attitude. Chapter 1 introduces stochastic approaches, from the classical one-stage model to multi-stage formulations. We define scenario trees and present two standard routes to tractability: (i) the deterministic equivalent formulation for finite discrete uncertainty, and (ii) sample average approximation (SAA), applicable more broadly. All approaches are applied to a common illustrative example that serves as a running thread and enables a direct comparison of how the objective value evolves as the number of stages increases. We also discuss the main advantages and limitations of these approaches. Chapter 2 addresses robust optimization (RO). We introduce the notion of an uncertainty set and study two particularly relevant families: polyhedral sets (emphasizing box sets as a special case) and budgeted sets. We show their linear reformulations and apply the framework to the illustrative example to facilitate understanding and enable a direct comparison with the stochastic approaches...