Optimization through Iterative Smooth Morphological Transformations

In this paper, we introduce SMorph, a new methodology for combinatorial optimization that works in the instance space of the problem at hand. Indeed, given the problem instance to solve, SMorph builds a simplified instance whose optimum is easy to locate, then it iteratively evolves this instance towards the target one by alternating two steps: optimization and smooth transformation of the current instance. The knowledge acquired in each iteration is transferred to next one, while the entire process is designed with the aim of improving the last optimization step. Although the abstract search scheme of SMorph is general enough to be instantiated for a variety of combinatorial optimization problems, here we present an implementation for the well-known Linear Optimization Problem (LOP). Experiments have been conducted on a set of commonly adopted benchmark instances of the LOP, and the results validate the proposed approach.