Timezone: »

 
Poster
Graph Learning Assisted Multi-Objective Integer Programming
Yaoxin Wu · Wen Song · Zhiguang Cao · Jie Zhang · Abhishek Gupta · Mingyan Lin

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #128
in Poster Session 4 »

Objective-space decomposition algorithms (ODAs) are widely studied for solving multi-objective integer programs. However, they often encounter difficulties in handling scalarized problems, which could cause infeasibility or repetitive nondominated points and thus induce redundant runtime. To mitigate the issue, we present a 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 decision process, and parameterize the policy (reduction rule) with a novel two-stage GNN to fuse information from variables, constraints and especially objectives for better state representation. We train our model with imitation learning and deploy it on a state-of-the-art ODA. Results show that our method significantly improves the solving efficiency of the ODA. The learned policy generalizes fairly well to larger problems or more objectives, and the proposed GNN outperforms existing ones for integer programming in terms of test and generalization accuracy.

Keywords: Graph learning · Objective-space decomposition · Multi-objective integer programs · Attention
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Yaoxin Wu (Nanyang Technological University)
Wen Song (Institute of Marine Scinece and Technology, Shandong University)
Zhiguang Cao (Singapore Institute of Manufacturing Technology)
Jie Zhang (Nanyang Technological University)
Abhishek Gupta (Agency for Science, Technology and Research)

Abhishek Gupta is a Scientist in A*STAR’s Singapore Institute of Manufacturing Technology (SIMTech). He holds a PhD in Engineering Science from the University of Auckland, New Zealand. His current research is on developing algorithms at the intersection of optimization and machine learning, with particular application to the engineering sciences, manufacturing and cyber-physical production systems.

Mingyan Lin (Singapore Institute of Manufacturing Technology)

More from the Same Authors