Page 1 Next

Displaying 1 – 20 of 27

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

High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems

Roman Dębski (2014)

International Journal of Applied Mathematics and Computer Science

Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine ski racing (the presented solution is probably the most general one published so far). The key idea behind these algorithms is to use a grid-based discretization scheme to transform the continuous optimization problem into a search problem over a specially constructed finite graph, and then to apply dynamic programming to find an approximation...

Currently displaying 1 – 20 of 27

Page 1 Next