Presentación | Participantes | Bibliografía (DML-E) | Bibliografía adicional | Enlaces de interés | Otros proyectos DML | Ayuda  
INICIO | 15 de abril de 2024
  

Experiencias computacionales con procedimientos de identificación de restricciones para algunos tipos de programas enteros.

Título inglés Computational experiences with procedures for constraint identification for some types of integer programs.
Título español Experiencias computacionales con procedimientos de identificación de restricciones para algunos tipos de programas enteros.
Autor/es Barceló, Jaime
Organización Dep. Estad. Invest. Oper. Fac. Informàt. Univ. Politèc. Catalunya, Barcelona, España
Revista 0210-8054
Publicación 1985, 9 (2): 121-146, 28 Ref.
Tipo de documento articulo
Idioma Español
Resumen español Desde los primeros trabajos de Padberg, Grötschel y otros, los procedimientos de identificación de restricciones han demostrado su utilidad en la resolución de clases especiales de problemas enteros de estructura combinatoria, tales como el del viajante de comercio, los de apareamientos en grafos, el de la mochila, etc., entre otros.
Por otra parte, muchos otros tipos de problemas enteros incluyen en su estructura aspectos combinatorios, como es el caso, por ejemplo, de los problemas de localización de plantas con restricciones de capacidad y los de particionamiento de conjuntos.
Este trabajo tiene una doble intención: por una parte, dar una breve panorámica de los procedimientos de identificación de restricciones y su utilización algorítmica general, y por otra parte estudiar su aplicación a otros problemas particulares, explorando algunos aspectos de su estructura combinatoria.
Los problemas de localización de plantas con restricciones de capacidad admiten formulaciones alternativas, algunas de las cuales incluyen restricciones de tipo knapsack, especialmente si se añaden las aparentemente redundantes restricciones knapsack surrogadas sobre las capacidades de las plantas. Este trabajo analiza computacionalmente el impacto que tales formulaciones y las restricciones complementarias generadas por un procedimiento de identificación de restricciones, tienen en la resolución de dichos problemas.
Los problemas de partición de conjuntos pueden ser resueltos mediante algoritmos que utilicen los cortes disyuntivos que su estructura permite generar. Balas y Padberg proponen además otras familias de cortes derivados de subproblemas planteados en el grafo de intersección fuerte asociado. En este trabajo se estudian computacionalmente los resultados de incorporar, según un procedimiento de tipo identificación de restricciones, planos secantes derivados de desigualdades de clique en el grafo asociado.
Clasificación UNESCO 120707
Palabras clave español Programación entera ; Problema del viajante ; Algoritmos
Código MathReviews MR0840183
Icono pdf Acceso al artículo completo
Equipo DML-E
Instituto de Ciencias Matemáticas (ICMAT - CSIC)
rmm()icmat.es