《EURO Journal on Computational Optimization》：ICNN-enhanced 2SP: Leveraging input convex neural networks for solving two-stage stochastic programming
编辑推荐：
输入凸神经网络（ICNN）作为两阶段随机规划（2SP）中凸补偿函数的可靠替代模型。通过线性规划（LP）实现精确嵌入，无需引入昂贵的整数变量。相较于基于混合整数规划（MIP）的方法，速度优势随问题规模增大而增强。在多个基准测试中保持高求解质量。两阶段随机规划（2
输入凸神经网络（ICNN）作为两阶段随机规划（2SP）中凸补偿函数的可靠替代模型。通过线性规划（LP）实现精确嵌入，无需引入昂贵的整数变量。相较于基于混合整数规划（MIP）的方法，速度优势随问题规模增大而增强。在多个基准测试中保持高求解质量。两阶段随机规划（2SP）是不确定性下决策制定的基础建模框架，能够在面对不可预测的未来事件时实现最优资源配置。在此框架中，初始（第一阶段）决策在不确定性解决之前做出，随后在随机变量显现后进行调整（补偿，或第二阶段）决策。电力行业和石化行业依赖2SP在其优化建模中纳入不确定性，并将其作为规划活动的标准工具。样本平均逼近（SAA）是2SP的基础技术，其中第二阶段问题的期望值被有限场景近似所替代。尽管算法上易于实现，SAA面临根本性权衡：场景不足可能无法准确表征随机现象，而更大的样本则增加计算需求。为缓解此限制，常采用场景缩减技术，但这些技术可能遗漏关键场景，损害解的鲁棒性。这些缺陷促使采用专门的分解方法，包括基于Benders和基于拉格朗日分解的方法，这些方法将问题分解为更小、更易处理的子问题。通过利用问题结构（如可分性和对偶性），这些方法缓解了SAA的可扩展性挑战，并减少了对场景采样的依赖。然而，其有效性仍取决于问题特定性质（如线性或凸性），且通常需要精细的算法调优。尽管分解方法有所发展，这些局限性仍然存在，推动了对利用机器学习（ML）的替代方法的探索。近期基于学习的2SP方法进展探索了替代模型以逼近复杂值函数。多项研究提出了基于神经网络（NN）的方法来学习线性规划（LP）值函数，旨在高效求解两阶段和多阶段随机规划问题。其他工作集中于基于学习的场景缩减以创建更小的代表性场景集。另一研究方向通过深度强化学习将2SP分解为在采样场景上训练的多智能体结构，训练阶段成为主要计算瓶颈。虽然这些方法展示了替代建模的优势，但其通用性相对较低，受限于特定问题组件或依赖定制架构。相比之下，Neur2SP通过采用神经网络逼近期望补偿函数，提出了通用框架，其动机源于训练后神经网络替代模型的嵌入。Kronqvist等人通过动态采样和重训练进一步改进了Neur2SP，以在感兴趣区域精炼替代模型，这一原则也体现在Liu和Oliveira的自适应替代优化框架中。然而，Neur2SP的通用性是有代价的：将具有修正线性单元（ReLU）激活函数的神经网络嵌入优化模型需要混合整数规划（MIP）公式，其规模随网络大小增长，导致更深或更宽架构的计算不可行性。这种通用性与效率之间的张力凸显了对能够平衡表达力与可处理性的架构的需求。输入凸神经网络（ICNN）因其拟合一般凸函数的能力同时保留神经网络的灵活性和表达力，已成为替代建模的有前景的替代方案。与典型的前馈网络不同，ICNN在架构上受约束以确保相对于输入具有凸性，从而能够通过LP公式实现精确推理。这一特性使其在嵌入大规模优化框架时特别有利。尽管ICNN无法建模非凸补偿函数（与ReLU神经网络相比是局限性），但库存管理、能源调度和投资组合优化中的许多现实2SP问题固有地表现出凸结构。尽管前景广阔，先前研究主要集中于将ICNN应用于函数逼近和系统建模，如学习最优潮流（OPF）值函数或在最优控制中表示系统动力学。然而，其在基于替代的优化中的潜力，特别是用于逼近2SP中的凸补偿函数，仍未得到充分探索。具体而言，凸神经架构已被用于建模具有连续补偿的两阶段MIP中的LP值函数，但这些研究依赖于针对LP结构性质定制的专门神经架构和紧凑启发式重构，而非通用、易于部署的ICNN。因此，本研究通过利用ICNN的固有凸性和LP的计算可处理性，弥合了这一差距，为2SP解锁高效可扩展的解决方案。具体而言，研究在基于替代的优化框架内提出了多项相互关联的贡献，将ICNN集成到2SP范式中。首先，利用ICNN的LP可表示性消除了传统基于MIP嵌入所固有的整数变量。其次，提出了ICNN在2SP中的首次集成，训练其逼近期望值函数同时保持凸性。第三，广泛的数值实验表明，所提方法在降低计算时间的同时实现了与Neur2SP相当的求解质量，特别是在大规模实例中，使其能够应用于时间关键的决策问题。
论文解读：ICNN增强的两阶段随机规划方法研究
一、研究背景与问题
两阶段随机规划（Two-Stage Stochastic Programming, 2SP）是处理不确定性条件下决策问题的核心建模框架，广泛应用于电力调度、石化生产规划等领域。该框架中，决策者需在随机变量实现前做出第一阶段决策，随后根据随机变量的实际实现调整第二阶段补偿决策。样本平均逼近（Sample Average Approximation, SAA）作为2SP的基础求解技术，通过有限场景近似替代期望值计算，但面临根本性权衡：场景数量不足难以准确表征随机现象，而场景过多则导致计算负担急剧增加。场景缩减技术虽可缓解此问题，但存在遗漏关键场景、损害解鲁棒性的风险。分解方法（如Benders分解、拉格朗日分解）通过利用问题结构缓解可扩展性挑战，但其有效性依赖问题特定性质，且需要精细的算法调优。近年来，基于机器学习（Machine Learning, ML）的替代建模方法受到关注，其中Neur2SP通过神经网络（Neural Network, NN）逼近期望补偿函数，提供了通用框架。然而，Neur2SP将具有修正线性单元（Rectified Linear Unit, ReLU）激活函数的神经网络嵌入优化模型时，需要混合整数规划（Mixed-Integer Programming, MIP）公式，其规模随网络大小增长，导致深层或宽层架构的计算不可行性。输入凸神经网络（Input Convex Neural Network, ICNN）因其架构上保证输出相对于输入的凸性，可通过线性规划（Linear Programming, LP）实现精确推理，为嵌入大规模优化框架提供了新途径。尽管ICNN已在最优潮流值函数学习、最优控制系统建模等领域得到应用，但其在2SP补偿函数替代建模中的潜力尚未被充分探索。该研究旨在弥合这一差距，利用ICNN的固有凸性和LP可处理性，为2SP提供高效可扩展的求解方案。
二、研究内容与结论
研究人员提出了ICNN增强的2SP求解框架，核心贡献包括三个方面：其一，利用ICNN的LP可表示性，消除了传统MIP嵌入所必需的整数变量，显著缩减了数学规划公式的规模；其二，首次将ICNN集成到2SP中，训练其逼近期望值函数同时保持凸性，保留了Neur2SP处理任意场景集的能力；其三，通过大量数值实验验证了所提方法在求解质量和计算效率上的优势。研究在CFLP（容量设施选址问题）、SSLP（随机服务器选址问题）和INVP（投资问题）三类基准问题上进行了系统评估。结果表明，ICNN增强方法在80%的实例中求解质量达到或超过Neur2SP，计算时间优势随问题规模增大而更加显著。在CFLP_50_50实例中，求解速度提升高达100倍；在SSLP_10_50实例中实现3倍加速且求解质量相当；在INVP实例中，虽然绝对求解时间差异较小，但ICNN方法在多数实例中提供了更优的求解质量。训练阶段仅需约10%的额外时间开销，但这一前期投入通过LP驱动的公式化在优化阶段实现了显著的加速收益。该研究发表在《EURO Journal on Computational Optimization》。
三、关键技术方法
研究人员采用的主要技术方法包括：ICNN架构设计，通过非负权重约束和凸非递减激活函数（ReLU）保证网络输出相对于输入的凸性，并利用跳跃连接（skip connections）缓解非负约束的限制性影响；基于LP的精确嵌入方法，利用ICNN的epigraph表示将ReLU非线性转换为不等式约束，实现无需整数变量的精确网络嵌入；监督式训练范式，生成5000个第一阶段可行解并求解其第二阶段问题构建训练数据，以均方误差（Mean Squared Error, MSE）为损失函数联合训练场景编码器和决策映射网络；与Neur2SP一致的场景编码架构，通过共享网络处理各场景生成潜在特征向量，经均值聚合后输入决策映射网络。
四、研究结果
4.1 训练性能分析
ICNN方法与Neur2SP的训练时间处于同一数量级，ICNN因凸性约束仅需略长的训练时间。在10个问题实例中，ICNN在7个实例上取得了更低或相当的验证平均绝对误差（Mean Absolute Error, MAE），表明凸性约束并未显著损害网络表达力，且补偿函数在这些基准问题中可被凸函数良好逼近。
4.2 优化求解结果
CFLP结果：ICNN方法在CFLP_25_25和CFLP_50_50实例中显著优于Neur2SP，最优性差距从3.37%降至2.19%，从18.17%降至3.36%。在CFLP_50_50_500和CFLP_50_50_1000实例中，ICNN方法分别实现-9.82%和-12.82%的负差距，表明其找到了优于EF在时限内所得解的高质量解。求解时间方面，ICNN方法在CFLP_50_50实例中比Neur2SP快约100倍。
SSLP结果：ICNN方法在SSLP_5_25实例中实现2倍加速且最优性差距相同；在SSLP_15_45实例中，最优性差距从18.09%-18.72%大幅降至2.11%-2.65%，同时实现1.1-1.2倍加速；在SSLP_10_50实例中实现3倍加速且求解质量相当。在SSLP_10_50_2000实例中，EF在3小时时限内仅找到-172.74的目标值，而ICNN和Neur2SP均达到-350.07，但ICNN求解时间仅为0.29秒。
INVP结果：ICNN方法在多数实例中提供更优的求解质量，特别是在INVP_I_E系列实例中，最优性差距从Neur2SP的3.22%-17.32%降至0.11%-4.78%。在INVP_I_H_1681实例中，ICNN实现-0.41%的负差距。求解时间差异较小，但ICNN方法在几乎所有实例中均快于Neur2SP。
4.3 目标值分析
真实目标值（将替代方法所得第一阶段解代入原始2SP评估）和近似目标值（直接来自替代重构）的分析确认了ICNN方法的性能模式。标准偏差相对于均值较小，表明观察到的性能模式在实例间具有一致性。
五、讨论与结论
研究讨论部分指出，ICNN增强方法的主要局限性在于其凸性要求，因此该方法与Neur2SP形成互补关系：ICNN方法在凸或可凸化场景中表现优异，而基于ReLU的MIP公式仍是处理非凸补偿问题的合适选择。研究结论部分强调，该工作解决了2SP中的核心计算瓶颈，证明对于广泛且实际相关的凸补偿问题类别，ICNN可作为精确嵌入LP的可靠替代模型，其架构凸性约束被战略性利用而非视为限制。跨多样问题类别的实验表明，ICNN增强的2SP优于现有基于MIP的方法，计算优势随问题规模增大而更加显著，使其适用于需要频繁重求解的时间关键型决策应用（如实时电力调度和生产排程），而基于MIP的替代方案在此类场景中代价过高。此外，虽然实验聚焦于线性和混合整数补偿，ICNN的理论基础表明其对非线性凸设置具有更广泛的适用性，这是未来研究的有前景方向。研究同时指出，2SP领域缺乏标准化、具有挑战性的基准问题，现有实例往往缺乏现代工业问题的规模和复杂性，在新兴应用上验证ICNN增强方法将是评估其实用价值的关键。
