Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics
type: Item
instance of: scholarly article
title: Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics
zbMATH Open document ID: 1394.90572
DOI: 10.1155/2015/713043
author: Oscar Montiel
author: Francisco Javier Díaz Delgadillo
published in: Mathematical Problems in Engineering
publication date: 2018-08-27T00:00:00Z
review text: Summary: Nowadays, solving optimally combinatorial problems is an open problem. Determining the best arrangement of elements proves being a very complex task that becomes critical when the problem size increases. Researchers have proposed various algorithms for solving Combinatorial Optimization Problems (COPs) that take into account the scalability; however, issues are still presented with larger COPs concerning hardware limitations such as memory and CPU speed. It has been shown that the Reduce-Optimize-Expand (ROE) method can solve COPs faster with the same resources; in this methodology, the reduction step is the most important procedure since inappropriate reductions, applied to the problem, will produce suboptimal results on the subsequent stages. In this work, an algorithm to improve the reduction step is proposed. It is based on a fuzzy inference system to classify portions of the problem and remove them, allowing COPs solving algorithms to utilize better the hardware resources by dealing with smaller problem sizes, and the use of metadata and adaptive heuristics. The Travelling Salesman Problem has been used as a case of study; instances that range from 343 to 3056 cities were used to prove that the fuzzy logic approach produces a higher percentage of successful reductions.
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 6927054
Wikidata QID: Q59119000
describes a project that uses: Concorde
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2015/713043
OpenAlex ID: W1606593177
cites work: 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
cites work: Q4198056
cites work: Q4461906
cites work: The traveling salesman problem: An overview of exact and approximate algorithms
cites work: Solution of a Large-Scale Traveling-Salesman Problem
cites work: Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
cites work: Q3425132
cites work: An Algorithm for the Traveling Salesman Problem
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: An Effective Heuristic Algorithm for the Traveling-Salesman Problem
cites work: Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem
cites work: Path planning on a cuboid using genetic algorithms
cites work: Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem
cites work: Evolutionary algorithm to traveling salesman problems
cites work: Q4217266
cites work: Q4435267
cites work: Computational Complexity
Recommended article: Q4307083
Recommended article: Using concepts of fuzzy mathematics for formalization and solution of combinatorial optimization problems
Recommended article: Bottleneck Combinatorial Optimization Problems with Fuzzy Scenarios
Recommended article: A fuzzy valuation-based local search framework for combinatorial problems
Recommended article: The use of fuzzy logic in various combinatorial optimization problems
Recommended article: Vector optimization problems with linear criteria over a fuzzy combinatorial set of alternatives
Recommended article: Q4452949
Recommended article: An adaptive membrane algorithm for solving combinatorial optimization problems
description: scientific article; zbMATH DE number 6927054