Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization
<|reference_start|>Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization: Multi-objective combinatorial optimization (MOCO) problems are prevalent in various real-world applications. Most existing neural MOCO methods rely on problem decomposition to transform an MOCO problem into a series of singe-objective combinatorial optimization (SOCO) problems. However, these methods often approximate partial regions of the Pareto front and spend excessive time on diversity enhancement because of ambiguous decomposition and time-consuming precise hypervolume calculation. To address these limitations, we design a Geometry-Aware Pareto set Learning algorithm named GAPL, which provides a novel geometric perspective for neural MOCO via a Pareto attention model based on hypervolume expectation maximization. In addition, we propose a hypervolume residual update strategy to enable the Pareto attention model to capture both local and non-local information of the Pareto set/front. We also design a novel inference approach to further improve quality of the solution set and speed up hypervolume calculation. Experimental results on three classic MOCO problems demonstrate that our GAPL outperforms several state-of-the-art baselines via superior decomposition and efficient diversity enhancement.<|reference_end|>
@article{lu2024towards,
    title={Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective
  Combinatorial Optimization},
    author={Yongfan Lu, Zixiang Di, Bingdong Li, Shengcai Liu, Hong Qian, Peng
  Yang, Ke Tang, Aimin Zhou},
    journal={arXiv preprint arXiv:2405.08604},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.08604},
    primaryClass={cs.LG cs.AI}
}