Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
12-2021
Abstract
Objective-space decomposition algorithms (ODAs) are widely studied for solvingmulti-objective integer programs. However, they often encounter difficulties inhandling scalarized problems, which could cause infeasibility or repetitive nondominatedpoints and thus induce redundant runtime. To mitigate the issue, we presenta graph neural network (GNN) based method to learn the reduction rule in the ODA.We formulate the algorithmic procedure of generic ODAs as a Markov decisionprocess, and parameterize the policy (reduction rule) with a novel two-stage GNNto fuse information from variables, constraints and especially objectives for betterstate representation. We train our model with imitation learning and deploy it ona state-of-the-art ODA. Results show that our method significantly improves thesolving efficiency of the ODA. The learned policy generalizes fairly well to largerproblems or more objectives, and the proposed GNN outperforms existing ones forinteger programming in terms of test and generalization accuracy.
Discipline
Software Engineering
Publication
Proceedings of the 36th Conference on Neural Information Processing Systems, NeurIPS 2022; New Orleans, USA, Nov 28- Dec 9
Volume
35
ISBN
9781713871088
Publisher
Neural information processing systems foundation
City or Country
California
Citation
WU, Yaoxin; SONG, Wen; CAO, Zhiguang; ZHANG, Jie; GUPTA, Abhishek; and LIN, Mingyan Simon.
Graph learning assisted multi-objective integer programming. (2021). Proceedings of the 36th Conference on Neural Information Processing Systems, NeurIPS 2022; New Orleans, USA, Nov 28- Dec 9. 35,.
Available at: https://ink.library.smu.edu.sg/sis_research/8138
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.