摘要

本文介绍了一种结合强化学习概念的混合整数线性规划（MILP）新方法——折扣伪成本（Discounted Pseudocosts）。传统伪成本在分支定界过程中估计目标函数的变化，而本文提出的折扣伪成本通过引入前瞻性视角，更接近于强化学习中的“总奖励”或“折扣总奖励”概念。初步实验表明，这种方法能增强分支策略并加速解决复杂的MILP问题。

原理

折扣伪成本的核心在于将强化学习中的折扣总奖励概念应用于MILP的分支选择中。在强化学习中，代理在环境中通过选择动作来最大化总奖励，其中未来的奖励会乘以一个折扣因子（γ）。本文将这一概念应用于伪成本的更新中，通过引入一个折扣因子，使得未来的LP松弛边界改进也能被考虑在内。具体来说，折扣伪成本（DPS(x)）的计算公式为：DPS(x) = PS0(x) + γPS1(x) + γ^2PS2(x) + …，其中PS0(x)是传统的伪成本，PS1(x)、PS2(x)等是未来级别的伪成本，γ是折扣因子。这种方法的先进性在于它不仅考虑了即时的奖励，还考虑了未来可能的奖励，从而更全面地评估分支选择的影响。

流程

在MILP问题中，当选择一个变量进行分支时，传统的伪成本仅考虑该变量在当前分支的改进。而折扣伪成本则进一步考虑了在后续分支中可能的改进。具体流程如下：

1. 在当前节点，选择一个变量x进行分支。
2. 计算分支x ≤ ⌊x⌋后的LP松弛目标值Lx。
3. 更新传统伪成本PS0(x)为Lx - L。
4. 在后续分支中，假设选择变量y进行分支，并计算LP松弛目标值Ly。
5. 更新第一级折扣伪成本PS1(x)为Ly - Lx，并乘以折扣因子γ。
6. 重复上述过程，更高级别的伪成本也按同样方式更新，但折扣因子γ的幂次增加。 通过这种方式，折扣伪成本能够更全面地评估分支选择的影响，从而优化分支策略。

应用

折扣伪成本方法在MILP问题中具有广泛的应用前景。由于其不需要离线训练，可以适用于一般的MILP问题，特别是在需要快速解决复杂问题的场景中。此外，该方法还可以进一步扩展到使用伪成本的其他启发式算法中，如原始启发式算法，从而进一步提高解决效率。尽管目前的实验结果显示改进较小，但随着进一步的优化和调整，折扣伪成本有望在未来的MILP求解器中发挥更大的作用。