Self-Paced Learning Based Graph Convolutional Neural Network for Mixed Integer Programming (Student Abstract)

Graph convolutional neural network (GCN) based methods have achieved noticeable performance in solving mixed integer programming problems (MIPs). However, the generalization of existing work is limited due to the problem structure. This paper proposes a self-paced learning (SPL) based GCN network (SPGCN) with curriculum learning (CL) to make the utmost of samples. SPGCN employs a GCN model to imitate the branching variable selection during the branch and bound process, while the training process is conducted in a self-paced fashion. Specifically, SPGCN contains a loss-based automatic difficulty measurer, where the training loss of the sample represents the difficulty level. In each iteration, a dynamic training dataset is constructed according to the difficulty level for GCN model training. Experiments on four NP-hard datasets verify that CL can lead to generalization improvement and convergence speedup in solving MIPs, where SPL performs better than predefined CL methods.

Authors

• Li Chen Hong Kong Baptist University
• Hua Xu Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China Beijing National Research Center for Information Science and Technology (BNRist), Beijing 100084, China
• Ziteng Wang State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
• Chengming Wang Meituan Inc., Block F&G, Wangjing International R&D Park, No.6 Wang Jing East Rd, Chaoyang District, Beijing, 100102, China
• Yu Jiang Meituan Inc., Block F&G, Wangjing International R&D Park, No.6 Wang Jing East Rd, Chaoyang District, Beijing, 100102, China

Keywords

• Curriculum Learning
• Graph Convolutional Neural Network
• Mixed Integer Programming Problems