TL;DR
This paper revisits Parallel Pareto Local Search (PPLS), a method for finding optimal trade-offs in multi-objective optimization problems. The authors identify and address two key issues in the original PPLS: load imbalance across parallel processes and poor scalability. They propose simple modifications to improve both efficiency and the quality of the solutions found, demonstrating significant speedups and comparable solution quality on benchmark problems.
What Problem Does This Paper Address?
Multi-objective optimization problems (MOPs) involve finding a set of solutions that represent the best possible compromises between conflicting objectives. This set is known as the Pareto optimal set. Pareto Local Search (PLS) is a popular algorithm for finding these solutions, but it can be computationally expensive, especially for large problems with many objectives.
To speed up PLS, researchers have explored parallelization, leading to Parallel Pareto Local Search (PPLS). PPLS divides the objective space into regions and assigns independent PLS processes to each region. However, the original PPLS design suffers from two main drawbacks:
- Load Imbalance: The way the objective space is divided can lead to some parallel processes having much more work than others, especially when the shape of the Pareto front is unknown or irregular. This is because the "size" of the Pareto front within a given region can vary significantly.
- Scalability Issues: As more parallel processes are added, the search regions become smaller and more constrained. This can cause individual processes to get stuck in local optima or waste time searching outside their assigned regions, leading to a drop in solution quality and inefficient use of resources.
This paper aims to address these limitations by proposing and evaluating modifications to the PPLS algorithm.
Methods
The authors propose two main modifications to the PPLS algorithm:
- Estimating Pareto Front Boundaries for Load Balancing: To mitigate load imbalance caused by an unknown Pareto front shape, the authors suggest a pre-processing step. This involves running two simple single-objective local search processes (one for each objective) to estimate the extreme points of the Pareto front. A reference point is then derived from these extreme points, which is used to define the boundaries of the decomposed sub-regions. This aims to create more balanced workloads for the parallel processes.
- Overlapping Search Regions for Scalability: To address the scalability issue, the authors propose allowing the search regions to overlap. Instead of strictly partitioning the objective space, each sub-region is "enlarged" by a small opening angle ($\theta$). This overlap allows neighboring parallel processes to explore slightly beyond their strict boundaries, helping them to progress more easily and avoid getting trapped in local optima when the number of parallel processes increases. When $\theta = 0$, the method reverts to the original PPLS decomposition.
The paper evaluates these modifications using a bi-objective Unconstrained Binary Quadratic Programming (bUBQP) problem, a standard benchmark for multi-objective optimization.
Datasets
The paper uses standard bi-objective Unconstrained Binary Quadratic Programming (bUBQP) instances from a previous work [5]. These instances are characterized by their size ($n$) and objective correlation ($\rho$), which influences the shape of the Pareto front. No new datasets were introduced.
Key Insights and Ideas
- Pareto Front Shape is Crucial: The shape and scale of the Pareto front significantly impact the performance of decomposition-based parallel algorithms like PPLS. An unknown or irregular Pareto front can lead to uneven workloads and reduced efficiency.
- Overlapping Regions are Key to Scalability: Allowing search regions to overlap, even slightly, dramatically improves the scalability of PPLS. This prevents individual processes from getting stuck and allows them to better explore the search space as more parallel resources are added.
- A Simple Pre-processing Step Can Make a Big Difference: Estimating Pareto front boundaries before starting the parallel search is a low-cost way to significantly improve load balancing.
- Trade-off Between Quality and Speed: The proposed modifications introduce a trade-off. Increasing the overlap angle ($\theta$) can improve solution quality but also increase runtime. The authors aim to find an optimal balance.
Key Results
- Load Balancing: The proposed method for estimating Pareto front boundaries led to a significant reduction in runtime, with the revised PPLS being, on average, 4 times faster than the original PPLS. The quality of the solutions (measured by hypervolume) remained comparable, achieving about 99% of the original PPLS's hypervolume.
- Scalability: When using overlapping search regions, the revised PPLS showed improved performance in terms of both solution quality and runtime as the number of parallel processes increased. The paper demonstrates that with an appropriate opening angle ($\theta$), it's possible to achieve better or comparable hypervolume values in less time compared to the original PPLS, especially when scaling up the number of parallel resources. For instance, with $N=48$ processes, the revised PPLS achieved better hypervolume values with a small opening angle compared to the original PPLS with $N=24$ processes.
Limitations and Future Work
- Limitations:
- The experimental study was limited to bi-objective UBQP instances. The authors acknowledge that extending these findings to problems with more objectives or from different domains is necessary.
- The current approach requires setting the opening angle ($\theta$) manually. The authors note that this parameter can introduce a trade-off between quality and convergence time.
- The paper mentions that a more fine-grained setting of parameters for a larger number of CPU cores raises further issues that need separate consideration.
- Future Work:
- Develop an automatic technique for setting the opening angle ($\theta$) that is independent of the specific problem instance and the number of parallel resources.
- Explore introducing communication between parallel PLS processes to further enhance scalability and cooperation.
- Extend the investigation to problems with more than two objectives and to instances from other problem domains.
Summary updated