Graph Learning Assisted Multi-Objective Integer Programming

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. * Corresponding Author. 36th Conference on Neural Information Processing Systems (NeurIPS 2022). 𝑓 2 𝑓 1 Local upper bounds 𝑼(𝑵) Points 𝑵 Search region 𝑺(𝑵) Search zone to explore 𝒛(𝒖) 𝑓 2 𝑓 1 New point by solving IP Dominated region 𝑓 2 𝑓 1 𝑓 2 𝑓 1 (1) Selection of IP (3) IP computation (4) Update by dominance (5) Update by reduction rule Discard or not Yes No (2) Reduction rule