<p>Global solvers for mixed-integer nonlinear programming problems widely apply probing to enhance domain reduction, identify implications, and detect conflicts. The probing technique tentatively restricts variable bounds and derives valuable insights through performing bound propagations or by solving subproblems. However, due to its high complexity, solvers design specific rules to limit probing and apply various conditions when selecting probing variables and ranges. In this work, we propose representing a general mixed-integer nonlinear programming problem with a tripartite graph, which generates features to capture the neighborhood structure around variables, constraints, and nonlinear expressions. Equipped with properties like variable bounds and integrality conditions, a graph convolutional network is trained to decide whether to deactivate probing. Compared to classical binary classification models based on structural statistics, our computational experiments on benchmark libraries demonstrate that the graph-based policy provides greater robustness, reduces solution times, and exhibits promising generalization capabilities for broader learning tasks.</p>

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

Learning to deactivate probing with graph convolutional network for mixed-integer nonlinear programming

  • Yi Zhang,
  • Nikolaos V. Sahinidis

摘要

Global solvers for mixed-integer nonlinear programming problems widely apply probing to enhance domain reduction, identify implications, and detect conflicts. The probing technique tentatively restricts variable bounds and derives valuable insights through performing bound propagations or by solving subproblems. However, due to its high complexity, solvers design specific rules to limit probing and apply various conditions when selecting probing variables and ranges. In this work, we propose representing a general mixed-integer nonlinear programming problem with a tripartite graph, which generates features to capture the neighborhood structure around variables, constraints, and nonlinear expressions. Equipped with properties like variable bounds and integrality conditions, a graph convolutional network is trained to decide whether to deactivate probing. Compared to classical binary classification models based on structural statistics, our computational experiments on benchmark libraries demonstrate that the graph-based policy provides greater robustness, reduces solution times, and exhibits promising generalization capabilities for broader learning tasks.