Graph learning assisted multi-objective integer programming

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 t...

Full description

Saved in:
Bibliographic Details
Main Authors: WU, Yaoxin, SONG, Wen, CAO, Zhiguang, ZHANG, Jie, GUPTA, Abhishek, LIN, Mingyan Simon
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2021
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/8138
https://ink.library.smu.edu.sg/context/sis_research/article/9141/viewcontent/Learning_Generalizable_Models_for_Vehicle_Routing_Problems_via_Knowledge_Distillation__2_.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-9141
record_format dspace
spelling sg-smu-ink.sis_research-91412023-09-14T08:21:31Z Graph learning assisted multi-objective integer programming WU, Yaoxin SONG, Wen CAO, Zhiguang ZHANG, Jie GUPTA, Abhishek LIN, Mingyan Simon 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. 2021-12-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/8138 https://ink.library.smu.edu.sg/context/sis_research/article/9141/viewcontent/Learning_Generalizable_Models_for_Vehicle_Routing_Problems_via_Knowledge_Distillation__2_.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Software Engineering
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Software Engineering
spellingShingle Software Engineering
WU, Yaoxin
SONG, Wen
CAO, Zhiguang
ZHANG, Jie
GUPTA, Abhishek
LIN, Mingyan Simon
Graph learning assisted multi-objective integer programming
description 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.
format text
author WU, Yaoxin
SONG, Wen
CAO, Zhiguang
ZHANG, Jie
GUPTA, Abhishek
LIN, Mingyan Simon
author_facet WU, Yaoxin
SONG, Wen
CAO, Zhiguang
ZHANG, Jie
GUPTA, Abhishek
LIN, Mingyan Simon
author_sort WU, Yaoxin
title Graph learning assisted multi-objective integer programming
title_short Graph learning assisted multi-objective integer programming
title_full Graph learning assisted multi-objective integer programming
title_fullStr Graph learning assisted multi-objective integer programming
title_full_unstemmed Graph learning assisted multi-objective integer programming
title_sort graph learning assisted multi-objective integer programming
publisher Institutional Knowledge at Singapore Management University
publishDate 2021
url https://ink.library.smu.edu.sg/sis_research/8138
https://ink.library.smu.edu.sg/context/sis_research/article/9141/viewcontent/Learning_Generalizable_Models_for_Vehicle_Routing_Problems_via_Knowledge_Distillation__2_.pdf
_version_ 1779157178395918336