Displaying similar documents to “Métodos duales y algoritmos híbridos para problemas de 'set partitioning'.”

Heurísticas, planos secantes y optimización subgradiente para problemas de Set Partitioning.

Jaume Barceló, E. Fernández (1988)

Qüestiió

Similarity:

En este artículo se estudian los problemas de Set Partitioning (SP) desde una perspectiva algorítmica. El diseño de un procedimiento heurístico permite no sólo disponer de soluciones posibles para los mismos, sino también obtener desigualdades válidas que sean violadas por las soluciones posibles a partir de las que se obtienen. La incorporación a los problemas originales de las desigualdades válidas obtenidas proporcionan unos problemas ampliados (SPA) para los que también se propone...

Problemas de Knapsack 0-1 con una restricción adicional.

Jaume Barceló, E. Fernández (1988)

Qüestiió

Similarity:

En este artículo se estudian los problemas de Knapsack con una restricción adicional. Este estudio viene motivado por la aparición de problemas con esta estructura en la formulación de distintas relajaciones lagrangianas asociadas a problemas enteros. Hemos considerado dos tipos de problemas: unos tienen las dos restricciones del mismo sentido, mientras que los otros las tienen de distinto sentido. Para ambos tipos de problemas presentamos algoritmos de enumeración implícita para su...

Cotas inferiores para el problema de secuenciación con restricciones sobre los recursos.

Ramón Alvarez Valdés, José Manuel Tamarit Goerlich (1984)

Qüestiió

Similarity:

El trabajo explora dos vías de obtención de cotas inferiores para el problema de secuenciación de actividades con restricciones sobre los recursos, a partir de una formulación entera del problema. Una primera cota se obtiene de la relajación lineal y la aplicación sucesiva de planos de corte. El segundo método utiliza la relajación lagrangiana. El problema relajado se descompone en dos subproblemas para los que se proponen algoritmos de resolución. Se incluyen resultados computacionales...

Un algoritmo de subgradiente y un filtro adicional para la resolución del subproblema entero en la partición de Benders.

Jaume Barceló, L. Olivella (1981)

Qüestiió

Similarity:

El método de partición de Benders es particularmente útil para resolver modelos matemáticos del tipo de "multicommodity flows" o modelos econométricos del tipo de planificación descentralizada, sin embargo, en algunos casos, el subproblema entero generado por la descomposición dual es resuelto deficientemente por los procedimientos habituales de enumeración debido a su estructura matemática, carente de función objetivo e incluyendo una variable no restringida. En nuestro...

Cotas inferiores para el QAP-árbol.

Enrique Benavent López (1985)

Trabajos de Estadística e Investigación Operativa

Similarity:

El QAP-Arbol es un caso especial del problema de asignación cuadrática en que los flujos distintos de cero forman un árbol. No se requiere ninguna condición para la matriz de distancias. En este artículo presentamos una formulación del QAP-Arbol como un problema de programación lineal entera. Basándonos en esta formulación hemos construido cuatro relajaciones lagrangianas distintas que nos permiten obtener una serie de cotas inferiores para este problema. Para resolver una de estas relajaciones,...

Un nuevo algoritmo en programación signomial.

Ana Allueva, Antonio Pérez (1992)

Trabajos de Investigación Operativa

Similarity:

La técnica de Programación Geométrica resuelve problemas no lineales en los que tanto la función objetivo como las restricciones son expresiones polinomiales con coeficientes positivos. La teoría de Programación Signomial es similar para el caso en que los coeficientes sean reales arbitrarios. En este trabajo describimos un procedimiento de solución para problemas signomiales que pueden transformarse en problemas geométricos inversos. Este procedimiento incluye la formulación de un problema...

Heurísticas de descomposición lagrangiana para algunos problemas de localización discreta.

Alfredo Marín Pérez, Blas Pelegrín Pelegrín (1992)

Trabajos de Investigación Operativa

Similarity:

En este trabajo se considera el Problema de Localización de Plantas Simple y el Problema de la p-Mediana Generalizado. Se construyen dos algoritmos heurísticos, uno para cada problema, basados en una técnica de descomposición lagrangiana para problemas binarios. Los algoritmos son implementados en un microordenador y ejecutados sobre una serie de problemas generados aleatoriamente. Los resultados computacionales son comparados con los de otros dos algoritmos heurísticos basados en la...

Un algoritmo heurístico lagrangiano para el problema de localización de plantas con capacidades.

Jaume Barceló, Josep Casanovas (1982)

Qüestiió

Similarity:

Las técnicas lagrangianas se han aplicado con frecuencia al problema de localización de plantas cuando no intervienen las capacidades, y en algunos casos han demostrado su utilidad incluso cuando se tienen en cuenta restricciones adicionales. Nuestro trabajo estudia la aplicación de estas técnicas al problema de localización de plantas cuando intervienen las capacidades, en el caso particular en que el modelo considerado es entero puro. Se han tenido en cuenta varias descomposiciones...

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

Jaime Barceló (1985)

Qüestiió

Similarity:

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...

Un algoritmo de enumeración para el problema Knapsack.

Francisco Ruiz de Francisco, Juan Carlos Larrañeta (1981)

Qüestiió

Similarity:

En este trabajo se presenta un algoritmo de resolución del problema de Knapsack basado en el análisis de una secuencia de problemas, derivados del original, desarrollando un criterio que relaciona la admisibilidad entre ellos. Este algoritmo es de enumeración implícita; examinando sucesivamente soluciones lexicográficamente ordenadas con criterios de dominancia y optimalidad. Mediante experiencias computacionales se comparan los resultados de este algoritmo con otros bien conocidos. ...