Learning to deactivate probing with graph convolutional network for mixed-integer nonlinear programming
摘要
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.