All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 34

Showing per page

Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem

Gerard Sierksma (1994)

Applicationes Mathematicae

The 3-Opt procedure deals with interchanging three edges of a tour with three edges not on that tour. For n≥6, the 3-Interchange Graph is a graph on 1/2(n-1)! vertices, corresponding to the hamiltonian tours in K_n; two vertices are adjacent iff the corresponding hamiltonian tours differ in an interchange of 3 edges; i.e. the tours differ in a single 3-Opt step. It is shown that the 3-Interchange Graph is a hamiltonian subgraph of the Symmetric Traveling Salesman Polytope. Upper bounds are derived...

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2004)

RAIRO - Operations Research - Recherche Opérationnelle

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large. The...

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2010)

RAIRO - Operations Research

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very large....

Heurística complementaria a enfoques duales para la planificación de la producción.

Sebastián Lozano, Juan Carlos Larrañeta, Luis Onieva (1992)

Qüestiió

Este trabajo presenta una heurística de varios pasos para la obtención de soluciones admisibles al problema de la planificación de la producción con limitaciones de capacidad, a partir de las soluciones aproximadas que presentan los métodos duales basados en la relajación del problema. La heurística es complementaria a la aplicación de dichos métodos, buscando soluciones admisibles derivadas de las proporcionadas por la solución a la relajación.

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

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 optimización...

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

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

Qüestiió

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

Heuristiques pour le Problème du Vendeur m-Péripatétique

Éric Duchenne, Gilbert Laporte, Frédéric Semet (2009)

RAIRO - Operations Research

Le Problème du Vendeur m-Péripatétique (m-PVP) est défini sur un graphe non orienté G=(V,E) où V = {1,...,n} est l'ensemble des sommets, E = {(i,j) : i,j ∈ V,i < j} est l'ensemble des arêtes et (cij) est une matrice de coûts définie sur E. Le m-PVP consiste à déterminer m cycles hamiltoniens sur G n'ayant aucune arête en commun et dont le coût total est minimal. Cet article décrit sept nouvelles heuristiques pour le m-PVP et les compare à celle qui a été proposée par Krarup en 1975.

Currently displaying 1 – 20 of 34

Page 1 Next