A. Elorza, L. Hernando, J. A. Lozano
El problema del orden lineal se puede descomponer en dos componentes, una de las cuales es P, mientras que la otra es NP-dura. Más específicamente, en este artículo, demostramos que una función objetivo asociada a dicho problema puede ser expresada como la suma de otras dos funciones, de las cuales una está asociada a un problema P (se propone un algoritmo exacto para resolverlo) y la otra a un problema NP-duro. Estudiamos de qué manera diferentes algoritmos constructivos que se basan principalmente en información de orden uno varían su comportamiento dependiendo de la contribución de cada una de las componentes P y NP-dura. Se realizan un número de experimentos para dimensiones reducidas, en los que el óptimo global se conoce, asignando diferentes pesos a la componente NP-dura, mientras que el peso de la componente P se mantiene fijo. Se observa cómo el comportamiento de los algoritmos constructivos evoluciona a medida que el peso dado a la componente NP-dura varía.
Keywords: optimización combinatoria; permutaciones; problema del orden lineal; NP-duro; complejidad computacional
Scheduled
Integer and Combinatorial Optimization
June 10, 2022 4:00 PM
Grade Hall
