Smooth Transition Instance Chains in Combinatorial Optimization Problems

In this work, by using an adiabatic principle and the Maximum Cut Problem, we investigate the evolution of problem instances from a given initial instance to a given final instance. The path followed goes from one instance to the next by using a statistical concept of distance such that the transition is smooth in the sense that this distance is short. In other words, the process takes place in the instance space by following a trajectory of minimal change. During the process we study the evolution of the similarity between consecutive instances and the movement of the global optima. In particular, we investigated whether a smooth path in the instance space always exists between the initial and the final instance. This allow us to discuss a number of statistical results that are of general interest for the understanding of the instance space of difficult combinatorial optimization problems.