0000000000465161
AUTHOR
Carlos García-martínez
A genetic algorithm for the minimum generating set problem
Graphical abstractDisplay Omitted HighlightsWe propose a novel formulation for the MGS problem based on multiple knapsack.The so-conceived MGS problem is solved by a novel GA.The GA embeds an intelligent construction method and specialized crossover operators.We perform a thorough comparison with regards to state-of-the-art algorithms.The proposal proves to be very competitive, specially for large and hard instances. Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinat…
GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem
In this work, we tackle multidimensional two-way number partitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridisation is limited to the variant known as interior PR. Here, we couple GRASP with the "exterior form" of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. …
Tabu search with strategic oscillation for the quadratic minimum spanning tree
The quadratic minimum spanning tree problem consists of determining a spanning tree that minimizes the sum of costs of the edges and pairs of edges in the tree. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated metaheuristics. This article presents a simple Tabu Search (TS) for this problem that incorporates Strategic Oscillation (SO) by alternating between constructive and destructive phases. The commonalties shared by this strategy and the more recently introduced methodology called iterated greedy search are shown and implications of their differences regarding the use of memory structures are identified. Extensive …