Automatic generation of algorithms

There is a variety of combinatorial optimization problems for which any efficient algorithm capable of ccurately resolve any input data of the problem, has been found so far. Such problems are associated with the decision making in large part of the production and services processes and are studied in the field of management science, computer science and operations research. Typical cases arise in the optimal use of raw material, the optimal use of time; the optimal scheduling of human resources, etc. Situations like these have been extensively studied in the literature, giving rise to a particular class of problems known as NP-complete, which in turn, is the origin of the famous conjecture of NP-completeness. Despite a relentless search for the last 40 years, an efficient algorithm for any of the problems of the family has not been found yet, in fact, one algorithm would be sufficient to activate a complex network of knowledge that interconnects all problems, triggering a specific and efficient algorithm for each problem belonging to the class. Knowing that the computational power of processors has increased enormously since the NP-completeness was detected, one wonders if the task of finding efficient algorithms could be performed by machines. We argue that the creation of an algorithm for solving an optimization problem can also be seen as an optimization problem. In this case, the feasible solutions of the optimization problem are the different algorithms that solve the problem, while the objective function corresponds to the characteristics of the algorithms that we are looking for. In this project, using a suitable search method, several algorithms are automatically produced for various combinatorial optimization problems.

 

Contributions

  • Automatically generated algorithms for the Vertex Coloring Problem. PLoS ONE, 2013.(Contreras, C., Gatica, G., Parada, V. ).

 

 

 

 

 

 

 

 

 
Banner
Banner
Banner
Banner
Banner