Mixed integer linear programming can effectively model many practical problems, but complexity of solving time is non-polynomial. Combining guiding the solver to activate/deactivate separators and select cutting planes can effectively reduce solving time. First, instance information and solver status are represented as a graph. A graph neural network predicts the scores for each separator activating/deactivating configuration, and selection probabilities for these configurations are subsequently sampled. Then graph neural network is used to replace the lookahead strategy to score candidate cutting planes, and the cutting plane with the highest score is added to the relaxed linear programming. In the process of obtaining graph embedding representation, by assigning random features to graph nodes, the model’s ability to distinguish different instances is improved; introducing graph attention mechanism, the model pays attention to more effective separators and cutting planes, which improves performance and interoperability of the model. Experimental results on the four most commonly used instance sets showed that our method can effectively reduce the solving time and has good generalization ability, especially the MIPLIB 2017 instance set, on which the average solving time is reduced by 37.166% compared with solver under the default settings.

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

Improved Cutting Plane Algorithm Combining Generation and Selection Decision Process

  • Hongjun Heng,
  • Zheng Hu

摘要

Mixed integer linear programming can effectively model many practical problems, but complexity of solving time is non-polynomial. Combining guiding the solver to activate/deactivate separators and select cutting planes can effectively reduce solving time. First, instance information and solver status are represented as a graph. A graph neural network predicts the scores for each separator activating/deactivating configuration, and selection probabilities for these configurations are subsequently sampled. Then graph neural network is used to replace the lookahead strategy to score candidate cutting planes, and the cutting plane with the highest score is added to the relaxed linear programming. In the process of obtaining graph embedding representation, by assigning random features to graph nodes, the model’s ability to distinguish different instances is improved; introducing graph attention mechanism, the model pays attention to more effective separators and cutting planes, which improves performance and interoperability of the model. Experimental results on the four most commonly used instance sets showed that our method can effectively reduce the solving time and has good generalization ability, especially the MIPLIB 2017 instance set, on which the average solving time is reduced by 37.166% compared with solver under the default settings.