Problema de interdicción secuencial de camino más corto estocástico

Abstract

Esta tesis se enmarca en programación binivel, que corresponde a un problema de optimización que depende de las decisiones de dos partes, líder y seguidor y, por otro lado, se relaciona con el problema Multi-armed Bandit, donde el principal objetivo es escoger qué brazo jalar en una máquina con n opciones y recibir una recompensa aleatoria según la decisión. En el Bandit, el término Regret caracteriza la diferencia entre el brazo que se escoge y haber elegido el brazo óptimo, que en principio es desconocido. La linealidad del Regret (LaiRobbins) permite extrapolar dicho problema a una configuración de caminos, donde el costo de cada camino viene de una distribución de probabilidad. El objetivo principal en este caso es bloquear caminos (escoger un brazo) para encarecer la ruta de un evasor (recompensa). A esto se le denomina el problema de "Interdicción de camino más corto estocástico". Este tipo de configuración permite, por ejemplo, simular el bloqueo de caminos de contrabando, adoptando una estrategia para hacer menos atractivo el negocio desde los costos. En la configuración de Bandit clásico, surge la disyuntiva de exploración o explotación que trata de decidir si se exploran distintos brazos hasta encontrar el óptimo o si se explota algún brazo cuya ganancia ya se conoció en algún periodo. Este trade off entre exploración y explotación se extiende al problema de interdicción, motivando a descubrir una cota inferior de desempeño de políticas de decisión y estimar el costo de la exploración. En otras palabras, cuánto se debe explorar para asegurar la optimalidad de una política de interdicción que se traduce en términos de Regret. Se establece un límite fundamental para el desempeño asintótico de políticas de decisión admisibles y se comparan distintas políticas mediante simulaciones.