Mixed Integer Linear Programming (MILP) is a type of NP-hard problem that is widely used in industries but challenging to solve. Recently, there has been increasing interest in using Deep Learning (DL) to accelerate solving MILPs, particularly through learning to branch. However, the validity of DL models is based on the assumption that the test set and the training set are drawn from the same distribution, while in MILPs, the distribution shift often appears. To improve the generalization of the branching policy, we introduce the domain generalization method and propose an Adaptive Policy Switching (APS) framework. The experiments demonstrate that APS outperforms the previous state-of-the-art (SOTA) method, reducing the number of nodes by 18% on completely unseen MILPs.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

APS: An Adaptive Policy Switching Framework to Improve the Generalization of Branching Policy

  • Ce Zhang,
  • Dapeng Li,
  • Lin Lin,
  • Xinyue Lu,
  • Guoliang Fan

摘要

Mixed Integer Linear Programming (MILP) is a type of NP-hard problem that is widely used in industries but challenging to solve. Recently, there has been increasing interest in using Deep Learning (DL) to accelerate solving MILPs, particularly through learning to branch. However, the validity of DL models is based on the assumption that the test set and the training set are drawn from the same distribution, while in MILPs, the distribution shift often appears. To improve the generalization of the branching policy, we introduce the domain generalization method and propose an Adaptive Policy Switching (APS) framework. The experiments demonstrate that APS outperforms the previous state-of-the-art (SOTA) method, reducing the number of nodes by 18% on completely unseen MILPs.