  Multi-objectivization is a term used to describe strategies developed for
optimizing single-objective problems by multi-objective algorithms. This paper
focuses on multi-objectivizing the sum-of-the-parts combinatorial optimization
problems, which include the traveling salesman problem, the unconstrained
binary quadratic programming and other well-known combinatorial optimization
problem. For a sum-of-the-parts combinatorial optimization problem, we propose
to decompose its original objective into two sub-objectives with controllable
correlation. Based on the decomposition method, two new multi-objectivization
inspired single-objective optimization techniques called non-dominance search
and non-dominance exploitation are developed, respectively. Non-dominance
search is combined with two metaheuristics, namely iterated local search and
iterated tabu search, while non-dominance exploitation is embedded within the
iterated Lin-Kernighan metaheuristic. The resultant metaheuristics are called
ILS+NDS, ITS+NDS and ILK+NDE, respectively. Empirical studies on some TSP and
UBQP instances show that with appropriate correlation between the
sub-objectives, there are more chances to escape from local optima when new
starting solution is selected from the non-dominated solutions defined by the
decomposed sub-objectives. Experimental results also show that ILS+NDS, ITS+NDS
and ILK+NDE all significantly outperform their counterparts on most of the test
instances.
