Phase Transitions in Combinatorial Optimization Problems

The goal of this chapter, which is based on reference [63], is to better characterize the nature of the search space of particular problems where the number of optimal solutions, and the difficulty of finding them, varies as a function of a parameter that can be modified at will. According to the value of the parameter, the system goes from a situation in which there are many solutions to the problem to a situation in which, suddenly, there are no solutions at all. This type of behavior is typical of phase transitions in physics and the term has been adopted in the computational field by analogy with the physical world