Multi-Objectivizing Sum-of-the-Parts Combinatorial Optimization Problems by Random Objective Decomposition

Jialong Shi, Jianyong Sun, Qingfu ZhangarXiv 2019 · arXiv

Abstract

Combinatorial optimization problems often suffer from the "local optimum trap," where search algorithms become stuck in sub-optimal solutions. This paper presents a novel framework for "multi-objectivization" through Random Objective Decomposition. By splitting a single "sum-of-the-parts" objective into two correlated sub-objectives, the authors introduce two techniques: Non-dominance Search (NDS) and Non-dominance Exploitation (NDE). These methods allow metaheuristics to navigate local optima more effectively by identifying promising "non-dominated" neighbors in a multi-objective space. Experimental results on Traveling Salesman Problem (TSP) and Unconstrained Binary Quadratic Programming (UBQP) benchmarks demonstrate that this approach significantly improves search efficiency and solution quality compared to traditional single-objective metaheuristics.

Introduction

In the field of combinatorial optimization, the primary challenge is navigating complex fitness landscapes to find a global optimum. Standard metaheuristics, such as Iterated Local Search (ILS), typically employ a "perturbation" or "kick" to escape local optima—valleys in the landscape where no immediate neighbor offers a better solution. However, these perturbations are often random and uninformed, leading to inefficient searches that may fail to find the global minimum in high-dimensional spaces.

This research addresses the need for a more "informed" escape mechanism. The authors propose leveraging the principles of multi-objective optimization to solve single-objective problems. Specifically, they target "sum-of-the-parts" problems, where the total cost is the sum of individual components, such as edge weights in a graph or bit-pair costs in a binary problem.

Methodology: Random Objective Decomposition

The core of the proposed framework is Random Objective Decomposition. This process transforms a single-objective problem into a multi-objective one to provide better guidance for the search algorithm.

1. Decomposition Strategy

The original objective function $f(x)$ is decomposed into two sub-objectives, $f_1(x)$ and $f_2(x)$, such that: $$f(x) = f_1(x) + f_2(x)$$ This is achieved by randomly splitting the cost of every individual unit (e.g., every edge in a TSP graph) into two parts based on a specific probability distribution.

2. Correlation Control

The authors found that the relationship between $f_1$ and $f_2$ is critical. By adjusting the shape of the probability distribution (e.g., moving from a "bell-shaped" to a "valley-shaped" distribution), they can control the Pearson correlation ($\rho$) between the two new objectives. This correlation acts as a tuning knob for the search's exploratory behavior.

3. Search Enhancements

The paper introduces two primary algorithmic enhancements:

  • Non-dominance Search (NDS): Tailored for algorithms with fixed neighborhood structures. When a local optimum is reached, NDS identifies neighbors that are "non-dominated" in the $(f_1, f_2)$ space. These neighbors are hypothesized to be the most promising "gateways" to better regions of the search space.
  • Non-dominance Exploitation (NDE): Designed for algorithms with varying neighborhood structures, such as the Lin-Kernighan heuristic. It identifies local optima that are non-dominated relative to the current best solution and targets those regions for intensive exploitation.

These techniques were integrated into three enhanced metaheuristics: ILS+NDS, ITS+NDS (Iterated Tabu Search), and ILK+NDE (Iterated Lin-Kernighan).

Experimental Evaluation

The effectiveness of the decomposition framework was tested on two classic benchmark sets:

  1. TSPLIB: A standard library for the Traveling Salesman Problem, featuring instances ranging from 51 to over 18,000 cities.
  2. OR-Library: Used for Unconstrained Binary Quadratic Programming (UBQP) instances, with variables ranging from 1,000 to 5,000.

Key Results

The experimental data revealed several significant findings:

  • Performance Gains: The NDS and NDE-enhanced versions consistently outperformed their standard counterparts across nearly all test instances.
  • Convergence: In specific TSP instances like rat99 and rd100, the enhanced algorithms found the global optimum reliably, whereas standard ILS frequently stalled at higher cost values.
  • Search Efficiency: The authors quantified the "expected number of function evaluations" required to find an improvement. NDS was shown to reduce this metric by orders of magnitude compared to exhaustive neighborhood searches.

Discussion and Insights

The Neighborhood Non-dominance Hypothesis

A central insight of this work is that solutions which are non-dominated in the decomposed sub-objective space are statistically more likely to lead to global improvements. By viewing the problem through a multi-objective lens, the algorithm can identify lateral moves that are invisible to a single-objective search.

The "Goldilocks" Correlation

The search performance is highly sensitive to the correlation ($\rho$) between sub-objectives. If $\rho = 1$, the sub-objectives are identical to the original, and no new information is gained. If the correlation is negative, the search becomes too chaotic. A moderate positive correlation provides the "Goldilocks" zone—enough diversity to escape traps without losing the signal of the original objective.

Conclusion and Future Work

Random Objective Decomposition provides a powerful new tool for combinatorial optimization. By creating a "plateau" in the fitness landscape where there used to be a sharp peak, it allows algorithms to move laterally to find hidden paths toward the global optimum.

While the method introduces some computational overhead due to the calculation of non-dominance, the resulting search is significantly more intelligent. Future research will focus on applying this logic to non-linear objective functions where costs are not easily separable, as well as testing the framework on other complex problems like the Quadratic Assignment Problem (QAP) and the Vehicle Routing Problem (VRP).

Summary updated

Abstract

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.
BibTeX
@misc{shi2019multi,
  author = {Jialong Shi and Jianyong Sun and Qingfu Zhang},
  title = {{Multi-Objectivizing Sum-of-the-Parts Combinatorial Optimization Problems by Random Objective Decomposition}},
  year = {2019},
  eprint = {1911.04658},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.04658},
}
Figure