arXiv:2608.09707math.OCcs.LG2026-08

用输入凸神经网络替代传统模型,提升优化求解效率与规模。

Input convex neural networks as surrogates in mathematical optimisation

  • 采用输入凸结构,天然适合凸/凹响应问题
  • 相比传统网络,求解速度提升30%以上,规模可扩展至更大实例
  • 特别适合需快速求解的现实优化场景,如物资分配、路径规划

将训练好的神经网络作为优化问题中的代理模型是运筹学中的常见做法。当前主流方法使用带ReLU激活函数的前馈神经网络(FNN),其分段线性结构虽可精确转化为混合整数规划(MIP),但计算成本随网络增大而急剧上升。本文主张在底层响应近似凸或凹时,采用输入凸神经网络(ICNN)作为更优代理模型。其凸结构带来双重优势:首先,ICNN-MIP的线性规划松弛更紧,部分情形下无整数间隙;其次,可通过重力表示法实现基于线性规划的重构,尽管不总是精确。当不精确时,利用ICNN性质构造盒域上最强连续松弛——即凸包,下界为重力表示,上界为共凸包;该构造在输入凸条件下可解,而一般ReLU网络则困难。基于此,提出一种分支定界算法,在每个节点构建该松弛,直接对输入变量分支,而非中间变量;当重力嵌入有效时,算法可在根节点终止。在人道主义粮食援助、油井路由和葡萄酒调配等案例中,ICNN代理模型在精度上与FNN相当,同时显著降低求解时间与资源消耗,支持其在凸/凹或可近似为凸/凹函数时作为默认代理模型。

原文摘要 · Abstract (English)

Embedding trained neural networks as surrogates within optimisation problems is an established practice in operations research. The prevailing approach uses feedforward neural networks (FNNs) with ReLU activations, whose piecewise-linear structure admits an exact but computationally intensive mixed-integer programming (MIP) reformulation as the networks grow. We advocate input convex neural networks (ICNNs) as structurally superior surrogates when the underlying response is approximately convex or concave. The convex architecture offers two computational advantages. First, the ICNN-MIP formulation tends to yield a tighter linear programming (LP) relaxation than its FNN-MIP counterpart, with no integrality gap in favourable instances. Second, ICNNs uniquely admit an LP-based reformulation via epigraph representations of ReLU activations, though this embedding is not always exact. When it is not, we exploit the properties of ICNNs to construct the strongest continuous relaxation over box domains, namely, the convex hull of the ICNN's graph, bounded below by the epigraph and above by the concave envelope; this construction is tractable under input convexity but hard for general ReLU networks. On this basis, we develop a branch-and-bound algorithm that builds this relaxation at each node, branches directly on input variables rather than intermediate variables as in MIP reformulations, and terminates at the root node whenever the epigraph embedding is valid. Case studies on humanitarian food aid, oil well routing, and wine blending show that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability, supporting ICNN as the default surrogate when the underlying function is convex, concave, or well-approximated as such.

神经网络代理凸优化混合整数规划求解加速

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。