The Experts below are selected from a list of 61452 Experts worldwide ranked by ideXlab platform
Broderick Crawford - One of the best experts on this subject based on the ideXlab platform.
-
A binary monkey search algorithm variation for solving the set Covering Problem
Natural Computing, 2019Co-Authors: Broderick Crawford, Ricardo Soto, Fernando Paredes, Carlos Castro, Rodrigo Olivares, Wenceslao Palma, Gabriel Embry, Diego Flores, José-miguel RubioAbstract:In complexity theory, there is a widely studied grouping of optimization Problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set Covering Problem, known as one of Karp’s 21 $${\mathscr {NP}}$$ NP -complete Problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the Problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set Covering Problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains. We propose a new climbing process with a better exploratory capability and a new cooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the Beasley’s OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version.
-
an adaptive intelligent water drops algorithm for set Covering Problem
International Conference on Computational Science and Its Applications, 2019Co-Authors: Broderick Crawford, Ricardo Soto, Gino Astorga, Sanjay Misra, Jose Lemusromani, José-miguel RubioAbstract:Today, natural resources are more scarce than ever, so we must make good use of them. To achieve this goal, we can use metaheuristic optimization tools as an alternative to achieve good results in a reasonable amount of time. The present work focuses on the use of adaptive techniques to facilitate the use of this type of tool to obtain good functional parameters. We use a constructive metaheuristic algorithm called Intelligent Water Drops to solve the set Covering Problem. To demonstrate the efficiency of the proposed method, the obtained results were compared with the standard version using the same initial configuration for both algorithms. Additionally, the Kolmogorov-Smirnov-Lilliefors, Wilcoxon signed-rank and Violin chart tests were applied to statistically validate the results, which showed that metaheuristics with autonomous search have a better behavior than do standard algorithms.
-
constructive metaheuristics for the set Covering Problem
International Conference on Bioinspired Methods and Their Applications, 2018Co-Authors: Broderick Crawford, Ricardo Soto, Jose Garcia, Gino AstorgaAbstract:Different criteria exist for the classification of the metaheuristics. One important classification is: improvement metaheuristics and constructive. On the one hand improvement metaheuristics, begins with an initial solution and iteratively improves the quality of the solution using neighborhood search. On the other hand, constructive metaheuristics, are those in which a solution is built from the beginning, finding in each iteration a local optimum. In this article, we to compare two constructive metaheuristics, Ant Colony Optimization and Intelligent Water Drops, by solving a classical NP-hard Problem, such like the Set Covering Problem, which has many practical applications, including line balancing production, service installation and crew scheduling in railway, among others. The results reveal that Ant Colony Optimization has a better behavior than Intelligent Water Drops in relation to the Problem considered.
-
a binary grasshopper optimisation algorithm applied to the set Covering Problem
Computer Science On-line Conference, 2018Co-Authors: Broderick Crawford, Ricardo Soto, Alvaro Pena, Gino AstorgaAbstract:Many of the Problems addressed at the industrial level are of a combinatorial type and a sub-assembly not less than these are of the NP-hard type. The design of algorithms that solve combinatorial Problems based on the continuous metaheuristic of swarm intelligence is an area of interest at an industrial level. In this article, we explore a general binarization mechanism of continuous metaheuristics based on the percentile concept. In particular, we apply the percentile concept to the Grasshopper optimization algorithm in order to solve the set Covering Problem (SCP). The experiments are designed with the aim of demonstrating the usefulness of the percentile concept in binarization. Additionally, we verify the effectiveness of our algorithm through reference instances. The results indicate the binary grasshopper optimization algorithm (BGOA) obtains adequate results when evaluated with a combinatorial Problem such as the SCP.
-
Solving the non-unicost set Covering Problem by using cuckoo search and black hole optimization
Natural Computing, 2017Co-Authors: Ricardo Soto, Broderick Crawford, Fernando Paredes, Franklin Johnson, Rodrigo Olivares, Jorge Barraza, Ignacio Figueroa, Eduardo OlguínAbstract:The set Covering Problem is a classical optimization benchmark that finds application in several real-world domains, particularly in line balancing production, crew scheduling, and service installation. The Problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. In this paper, we present two new approaches for efficiently solving this Problem, the first one based on cuckoo search and the second one on black hole optimization. Both are relatively modern bio-inspired metaheuristics that have attracted much attention due to their rapid convergence, easy implementation, and encouraging obtained results. We integrate to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing is employed for filtering the values from domains leading to infeasible solutions, while transfers function and discretization methods are used for efficiently handling the binary nature of the Problem. We illustrate interesting experimental results where the two proposed approaches are able to obtain various global optimums for a set of well-known set Covering Problem instances, outperforming also several recently reported techniques.
Fernando Paredes - One of the best experts on this subject based on the ideXlab platform.
-
A binary monkey search algorithm variation for solving the set Covering Problem
Natural Computing, 2019Co-Authors: Broderick Crawford, Ricardo Soto, Fernando Paredes, Carlos Castro, Rodrigo Olivares, Wenceslao Palma, Gabriel Embry, Diego Flores, José-miguel RubioAbstract:In complexity theory, there is a widely studied grouping of optimization Problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set Covering Problem, known as one of Karp’s 21 $${\mathscr {NP}}$$ NP -complete Problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the Problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set Covering Problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains. We propose a new climbing process with a better exploratory capability and a new cooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the Beasley’s OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version.
-
Solving the non-unicost set Covering Problem by using cuckoo search and black hole optimization
Natural Computing, 2017Co-Authors: Ricardo Soto, Broderick Crawford, Fernando Paredes, Franklin Johnson, Rodrigo Olivares, Jorge Barraza, Ignacio Figueroa, Eduardo OlguínAbstract:The set Covering Problem is a classical optimization benchmark that finds application in several real-world domains, particularly in line balancing production, crew scheduling, and service installation. The Problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. In this paper, we present two new approaches for efficiently solving this Problem, the first one based on cuckoo search and the second one on black hole optimization. Both are relatively modern bio-inspired metaheuristics that have attracted much attention due to their rapid convergence, easy implementation, and encouraging obtained results. We integrate to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing is employed for filtering the values from domains leading to infeasible solutions, while transfers function and discretization methods are used for efficiently handling the binary nature of the Problem. We illustrate interesting experimental results where the two proposed approaches are able to obtain various global optimums for a set of well-known set Covering Problem instances, outperforming also several recently reported techniques.
-
solving the set Covering Problem with binary cat swarm optimization
International Conference on Swarm Intelligence, 2016Co-Authors: Broderick Crawford, Ricardo Soto, Natalia Berrios, Franklin Johnson, Fernando ParedesAbstract:The Set Covering Problem is a formal model for many practical optimization Problems. It consists in finding a subset of columns in a zero---one matrix such that they cover all the rows of the matrix at a minimum cost. To solve the Set Covering Problem we use a metaheuristic called Binary Cat Swarm Optimization. This metaheuristic is a binary version of Cat Swarm Optimization generated by observing cat behavior. Cats have two modes of behavior: seeking mode and tracing mode. We are the first ones to use this metaheuristic to solve the Set Covering Problem, for this the proposed algorithm has been tested on 65 benchmarks instances.
-
a binary cat swarm optimization algorithm for the non unicost set Covering Problem
Mathematical Problems in Engineering, 2015Co-Authors: Broderick Crawford, Ricardo Soto, Fernando Paredes, Natalia Berrios, Franklin Johnson, Carlos Castro, Enrique NoreroAbstract:The Set Covering Problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. To solve the Set Covering Problem we use a metaheuristic called Binary Cat Swarm Optimization. This metaheuristic is a recent swarm metaheuristic technique based on the cat behavior. Domestic cats show the ability to hunt and are curious about moving objects. Based on this, the cats have two modes of behavior: seeking mode and tracing mode. We are the first ones to use this metaheuristic to solve this Problem; our algorithm solves a set of 65 Set Covering Problem instances from OR-Library.
-
a binary fruit fly optimization algorithm to solve the set Covering Problem
International Conference on Computational Science and Its Applications, 2015Co-Authors: Broderick Crawford, Ricardo Soto, Franklin Johnson, Cristian Pena, Claudio Torresrojas, Marco Riquelmeleiva, Sanjay Misra, Fernando ParedesAbstract:The Set Covering Problem SCP is a well known $$\mathcal {N} \mathcal {P}$$NP-hard Problem with many practical applications. In this work binary fruit fly optimization algorithms bFFOA were used to solve this Problem using different binarization methods. The bFFOA is based on the food finding behavior of the fruit flies using osphresis and vision. The experimental results show the effectiveness of our algorithms producing competitive results when solve the benchmarks of SCP from the OR-Library.
Ricardo Soto - One of the best experts on this subject based on the ideXlab platform.
-
A binary monkey search algorithm variation for solving the set Covering Problem
Natural Computing, 2019Co-Authors: Broderick Crawford, Ricardo Soto, Fernando Paredes, Carlos Castro, Rodrigo Olivares, Wenceslao Palma, Gabriel Embry, Diego Flores, José-miguel RubioAbstract:In complexity theory, there is a widely studied grouping of optimization Problems that belongs to the non-deterministic polynomial-time hard set. One of them is the set Covering Problem, known as one of Karp’s 21 $${\mathscr {NP}}$$ NP -complete Problems, and it consists of finding a subset of decision variables for satisfying a set of constraints at the minimum feasible cost. However, due to the nature of the Problem, this cannot be solved using traditional complete algorithms for hard instances. In this work, we present an improved binary version of the monkey search algorithm for solving the set Covering Problem. Originally, this approximate method was naturally inspired by the cognitive behavior of monkeys for climbing mountains. We propose a new climbing process with a better exploratory capability and a new cooperation procedure to reduce the number of unfeasible solutions. For testing this approach, we present a detailed computational results section, where we illustrate how this variation of the monkey search algorithm is capable of reaching various global optimums for a well-known instance set from the Beasley’s OR-Library and how it outperforms many other heuristics and meta-heuristics addressed in the literature. Moreover, we add a complete statistical analysis to show the effectiveness of the proposed approach with respect to the original version.
-
an adaptive intelligent water drops algorithm for set Covering Problem
International Conference on Computational Science and Its Applications, 2019Co-Authors: Broderick Crawford, Ricardo Soto, Gino Astorga, Sanjay Misra, Jose Lemusromani, José-miguel RubioAbstract:Today, natural resources are more scarce than ever, so we must make good use of them. To achieve this goal, we can use metaheuristic optimization tools as an alternative to achieve good results in a reasonable amount of time. The present work focuses on the use of adaptive techniques to facilitate the use of this type of tool to obtain good functional parameters. We use a constructive metaheuristic algorithm called Intelligent Water Drops to solve the set Covering Problem. To demonstrate the efficiency of the proposed method, the obtained results were compared with the standard version using the same initial configuration for both algorithms. Additionally, the Kolmogorov-Smirnov-Lilliefors, Wilcoxon signed-rank and Violin chart tests were applied to statistically validate the results, which showed that metaheuristics with autonomous search have a better behavior than do standard algorithms.
-
constructive metaheuristics for the set Covering Problem
International Conference on Bioinspired Methods and Their Applications, 2018Co-Authors: Broderick Crawford, Ricardo Soto, Jose Garcia, Gino AstorgaAbstract:Different criteria exist for the classification of the metaheuristics. One important classification is: improvement metaheuristics and constructive. On the one hand improvement metaheuristics, begins with an initial solution and iteratively improves the quality of the solution using neighborhood search. On the other hand, constructive metaheuristics, are those in which a solution is built from the beginning, finding in each iteration a local optimum. In this article, we to compare two constructive metaheuristics, Ant Colony Optimization and Intelligent Water Drops, by solving a classical NP-hard Problem, such like the Set Covering Problem, which has many practical applications, including line balancing production, service installation and crew scheduling in railway, among others. The results reveal that Ant Colony Optimization has a better behavior than Intelligent Water Drops in relation to the Problem considered.
-
a binary grasshopper optimisation algorithm applied to the set Covering Problem
Computer Science On-line Conference, 2018Co-Authors: Broderick Crawford, Ricardo Soto, Alvaro Pena, Gino AstorgaAbstract:Many of the Problems addressed at the industrial level are of a combinatorial type and a sub-assembly not less than these are of the NP-hard type. The design of algorithms that solve combinatorial Problems based on the continuous metaheuristic of swarm intelligence is an area of interest at an industrial level. In this article, we explore a general binarization mechanism of continuous metaheuristics based on the percentile concept. In particular, we apply the percentile concept to the Grasshopper optimization algorithm in order to solve the set Covering Problem (SCP). The experiments are designed with the aim of demonstrating the usefulness of the percentile concept in binarization. Additionally, we verify the effectiveness of our algorithm through reference instances. The results indicate the binary grasshopper optimization algorithm (BGOA) obtains adequate results when evaluated with a combinatorial Problem such as the SCP.
-
Solving the non-unicost set Covering Problem by using cuckoo search and black hole optimization
Natural Computing, 2017Co-Authors: Ricardo Soto, Broderick Crawford, Fernando Paredes, Franklin Johnson, Rodrigo Olivares, Jorge Barraza, Ignacio Figueroa, Eduardo OlguínAbstract:The set Covering Problem is a classical optimization benchmark that finds application in several real-world domains, particularly in line balancing production, crew scheduling, and service installation. The Problem consists in finding a subset of columns in a zero-one matrix such that they cover all the rows of the matrix at a minimum cost. In this paper, we present two new approaches for efficiently solving this Problem, the first one based on cuckoo search and the second one on black hole optimization. Both are relatively modern bio-inspired metaheuristics that have attracted much attention due to their rapid convergence, easy implementation, and encouraging obtained results. We integrate to the core of both metaheuristics an effective pre-processing phase as well as multiple transfer functions and discretization methods. Pre-processing is employed for filtering the values from domains leading to infeasible solutions, while transfers function and discretization methods are used for efficiently handling the binary nature of the Problem. We illustrate interesting experimental results where the two proposed approaches are able to obtain various global optimums for a set of well-known set Covering Problem instances, outperforming also several recently reported techniques.
Paolo Toth - One of the best experts on this subject based on the ideXlab platform.
-
an electromagnetism metaheuristic for the unicost set Covering Problem
European Journal of Operational Research, 2010Co-Authors: Zahra Najiazimi, Paolo Toth, Laura GalliAbstract:In this paper we propose a new heuristic algorithm to solve the unicost version of the well-known set Covering Problem. The method is based on the electromagnetism metaheuristic approach which, after generating a pool of solutions to create the initial population, applies a fixed number of local search and movement iterations based on the "electromagnetism" theory. In addition to some random aspects, used in the construction and local search phases, we also apply mutation in order to further escape from local optima. The proposed algorithm has been tested over 80 instances of the literature. On the classical benchmark instances, where the number of columns is larger than the number of rows, the algorithm, by using a fixed set of parameters, always found the best known solution, and for 12 instances it was able to improve the current best solution. By using different parameter settings the algorithm improved 4 additional best known solutions. Moreover, we proved the effectiveness of the electromagnetism metaheuristic approach for the unicost set Covering Problem by embedding the procedures of the proposed algorithm in a genetic algorithm scheme. The worse results obtained by the genetic algorithm show the impact of the electromagnetism metaheuristic approach in conducting the search of the solution space by applying the movements based on the electromagnetism theory. Finally, we report the results obtained by modifying the proposed electromagnetism metaheuristic algorithm for solving the non-unicost set Covering Problem.
-
algorithms for the set Covering Problem
Annals of Operations Research, 2000Co-Authors: Alberto Caprara, Paolo Toth, Matteo FischettiAbstract:The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.
-
a heuristic method for the set Covering Problem
Operations Research, 1999Co-Authors: Alberto Caprara, Matteo Fischetti, Paolo TothAbstract:We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows an...
-
a heuristic algorithm for the set Covering Problem
Integer Programming and Combinatorial Optimization, 1996Co-Authors: Alberto Caprara, Matteo Fischetti, Paolo TothAbstract:We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The main characteristics of the algorithm we propose are (1) a dynamic pricing scheme for the variables, akin to that used for solving large-scale LP's, to be coupled with subgradient optimization and greedy algorithms, and (2) the systematic use of column fixing to obtain improved solutions. Moreover, we propose a number of improvements on the standard way of defining the step-size and the ascent direction within the subgradient optimization procedure, and the scores within the greedy algorithms. Finally, an effective refining procedure is proposed. Extensive computational results show the effectiveness of the approach.
Alberto Caprara - One of the best experts on this subject based on the ideXlab platform.
-
algorithms for the set Covering Problem
Annals of Operations Research, 2000Co-Authors: Alberto Caprara, Paolo Toth, Matteo FischettiAbstract:The Set Covering Problem (SCP) is a main model for several important applications, including crew scheduling in railway and mass-transit companies. In this survey, we focus our attention on the most recent and effective algorithms for SCP, considering both heuristic and exact approaches, outlining their main characteristics and presenting an experimental comparison on the test-bed instances of Beasley's OR Library.
-
a heuristic method for the set Covering Problem
Operations Research, 1999Co-Authors: Alberto Caprara, Matteo Fischetti, Paolo TothAbstract:We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The algorithm was initially designed for solving very large scale SCP instances, involving up to 5,000 rows an...
-
a heuristic algorithm for the set Covering Problem
Integer Programming and Combinatorial Optimization, 1996Co-Authors: Alberto Caprara, Matteo Fischetti, Paolo TothAbstract:We present a Lagrangian-based heuristic for the well-known Set Covering Problem (SCP). The main characteristics of the algorithm we propose are (1) a dynamic pricing scheme for the variables, akin to that used for solving large-scale LP's, to be coupled with subgradient optimization and greedy algorithms, and (2) the systematic use of column fixing to obtain improved solutions. Moreover, we propose a number of improvements on the standard way of defining the step-size and the ascent direction within the subgradient optimization procedure, and the scores within the greedy algorithms. Finally, an effective refining procedure is proposed. Extensive computational results show the effectiveness of the approach.
