Problemas robustos de optimización combinatoria bajo incertidumbre de intervención presupuestada

Resumen En la optimización combinatoria robusta, queremos encontrar una solución que funcione bien bajo todas las realizaciones de un conjunto de incertidumbre de posibles valores de parámetros. La forma en que modelamos este conjunto de incertidumbre tiene una influencia decisiva en la complejidad del problema robusto correspondiente. Por esta razón, los conjuntos de incertidumbre con presupuesto se estudian a menudo, ya que nos permiten descomponer el problema robusto en subproblemas más fáciles. Proponemos una variante de incertidumbre presupuestada discreta para restricciones u objetivos basados en cardinalidad, donde se aplica un vector de peso a la restricción presupuestaria. Mostramos que, si bien el problema adversarial se puede resolver en tiempo lineal, el problema robusto se vuelve NP-duro y no aproximable. Discutimos diferentes posibilidades para modelar el problema robusto y mostramos experimentalmente que, a pesar del resultado de dureza, algunos modelos escalan relativamente bien en el tamaño del problema.