Timezone: »
We propose a deep reinforcement learning (RL) method to learn large neighborhood search (LNS) policy for integer programming (IP). The RL policy is trained as the destroy operator to select a subset of variables at each step, which is reoptimized by an IP solver as the repair operator. However, the combinatorial number of variable subsets prevents direct application of typical RL algorithms. To tackle this challenge, we represent all subsets by factorizing them into binary decisions on each variable. We then design a neural network to learn policies for each variable in parallel, trained by a customized actor-critic algorithm. We evaluate the proposed method on four representative IP problems. Results show that it can find better solutions than SCIP in much less time, and significantly outperform other LNS baselines with the same runtime. Moreover, these advantages notably persist when the policies generalize to larger problems. Further experiments with Gurobi also reveal that our method can outperform this state-of-the-art commercial solver within the same time limit.
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)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Learning Large Neighborhood Search Policy for Integer Programming »
Dates n/a. Room
More from the Same Authors
-
2022 Poster: Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation »
Jieyi Bi · Yining Ma · Jiahai Wang · Zhiguang Cao · Jinbiao Chen · Yuan Sun · Yeow Meng Chee -
2023 Poster: Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt »
Yining Ma · Zhiguang Cao · Yeow Meng Chee -
2023 Poster: DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization »
Haoran Ye · Jiarui Wang · Zhiguang Cao · Helan Liang · Yong Li -
2023 Poster: Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement »
Jinbiao Chen · Zizhen Zhang · Zhiguang Cao · Yaoxin Wu · Yining Ma · Te Ye · Jiahai Wang -
2023 Poster: Ensemble-based Deep Reinforcement Learning for Vehicle Routing Problems under Distribution Shift »
Yuan Jiang · Zhiguang Cao · Yaoxin Wu · Wen Song · Jie Zhang -
2023 Poster: Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimization »
Jinbiao Chen · Zizhen Zhang · Te Ye · Zhiguang Cao · Siyuan Chen · Jiahai Wang -
2023 Poster: MetaBox: A Benchmark Platform for Meta-Black-Box Optimization with Reinforcement Learning »
Zeyuan Ma · Hongshu Guo · Jiacheng Chen · Zhenrui Li · Guojun Peng · Yue-Jiao Gong · Yining Ma · Zhiguang Cao -
2023 Oral: MetaBox: A Benchmark Platform for Meta-Black-Box Optimization with Reinforcement Learning »
Zeyuan Ma · Hongshu Guo · Jiacheng Chen · Zhenrui Li · Guojun Peng · Yue-Jiao Gong · Yining Ma · Zhiguang Cao -
2022 Spotlight: Lightning Talks 5B-3 »
Yanze Wu · Jie Xiao · Nianzu Yang · Jieyi Bi · Jian Yao · Yiting Chen · Qizhou Wang · Yangru Huang · Yongqiang Chen · Peixi Peng · Yuxin Hong · Xintao Wang · Feng Liu · Yining Ma · Qibing Ren · Xueyang Fu · Yonggang Zhang · Kaipeng Zeng · Jiahai Wang · GEN LI · Yonggang Zhang · Qitian Wu · Yifan Zhao · Chiyu Wang · Junchi Yan · Feng Wu · Yatao Bian · Xiaosong Jia · Ying Shan · Zhiguang Cao · Zheng-Jun Zha · Guangyao Chen · Tianjun Xiao · Han Yang · Jing Zhang · Jinbiao Chen · MA Kaili · Yonghong Tian · Junchi Yan · Chen Gong · Tong He · Binghui Xie · Yuan Sun · Francesco Locatello · Tongliang Liu · Yeow Meng Chee · David P Wipf · Tongliang Liu · Bo Han · Bo Han · Yanwei Fu · James Cheng · Zheng Zhang -
2022 Spotlight: Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation »
Jieyi Bi · Yining Ma · Jiahai Wang · Zhiguang Cao · Jinbiao Chen · Yuan Sun · Yeow Meng Chee -
2022 Poster: Graph Learning Assisted Multi-Objective Integer Programming »
Yaoxin Wu · Wen Song · Zhiguang Cao · Jie Zhang · Abhishek Gupta · Mingyan Lin -
2021 Poster: NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem »
Liang Xin · Wen Song · Zhiguang Cao · Jie Zhang -
2021 Poster: Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer »
Yining Ma · Jingwen Li · Zhiguang Cao · Wen Song · Le Zhang · Zhenghua Chen · Jing Tang -
2020 Poster: Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning »
Cong Zhang · Wen Song · Zhiguang Cao · Jie Zhang · Puay Siew Tan · Xu Chi -
2018 Poster: Inference Aided Reinforcement Learning for Incentive Mechanism Design in Crowdsourcing »
Zehong Hu · Yitao Liang · Jie Zhang · Zhao Li · Yang Liu