摘要
在许多现实生活中的分析应用程序中，解决优化问题是决策的关键。然而，优化问题的系数通常是不确定的，并且取决于外部因素，例如未来的需求或能源或股票价格。机器学习 (ML) 模型，尤其是神经网络，越来越多地用于以数据驱动的方式估计这些系数。因此，考虑预测值解决优化问题的有效性的端到端预测和优化方法受到越来越多的关注。在整数线性规划问题的情况下，克服其不可微性的一种流行方法是在连续松弛中添加二次惩罚项，以便可以使用对二次程序进行微分的结果。相反，我们研究了更原则性的对数障碍项的使用，它广泛用于线性规划的内点求解器。具体来说，我们不区分 KKT 条件，而是考虑 LP 的齐次自对偶公式，并展示了内部点步长方向与学习所需的相应梯度之间的关系。最后，我们的实证实验表明，我们的方法与 Wilder 等人的最先进的 QPTL（二次编程任务损失）公式一样好。 [29] 以及 Elmachtoub 和 Grigas [12] 的 SPO 方法。
引言
最近，人们对数据驱动的决策越来越感兴趣。在许多分析应用程序中，组合优化用于决策，目的是最大化预定义的目标。然而，在许多现实世界的问题中，目标函数的系数存在不确定性，必须使用机器学习 (ML) 模型从历史数据中预测它们，例如用于投资组合优化的股票价格预测 [5]。在这项工作中，我们提出了一种新方法，将 ML 和优化集成到此类应用程序的深度学习架构中。
我们考虑可以表述为混合整数线性规划 (MILP) 的组合优化问题。MILP 已被用于解决许多组合优化问题，例如，高效微电网调度 [20]、促销计划 [8] 等。具体来说，我们想训练一个神经网络模型来预测 MILP 的系数，通过最小化任务损失来确定神经网络的参数，这考虑了预测系数对 MILP 输出的影响. 鉴于 MILP 是离散的并且线性规划 (LP) 松弛不是二次可微的，因此主要挑战是如何从基于 MILP 的任务损失计算梯度。
为此，怀尔德等人。[29] 提出通过区分 MILP 连续松弛的 KKT 条件来计算梯度。但是，要执行此操作，他们必须向目标添加二次正则化项。我们通过区分松弛 LP 的同构自对偶嵌入来克服这个问题。总之，我们将线性规划 (LP) 作为标准神经网络架构之上的最后一层，这使我们能够对 MILP 优化问题进行端到端的训练。
相关工作 有几种方法侧重于区分 argmin 优化问题以使其适合神经网络层。对于凸优化问题，KKT 条件将系数映射到解集。因此，可以使用隐函数定理对 KKT 条件进行微分，以进行 argmin 微分。按照这个想法，Amos 和 Kolter [3] 开发了一个 PyTorch 兼容的可微层，用于二次规划 (QP) 优化。以类似的方式 Agrawal 等人。[2] 使用 LSQR 21 为凸锥程序引入了一个可微层。
阿格拉瓦尔等人。[1] 提出在将其转换为凸锥程序后，将该框架用于凸优化问题。
唐蒂等人。[11] 研究了凸 QP 优化的端到端训练。Wilder 等人已经提出了子模块优化问题、零和游戏和 SAT 问题的端到端训练。[29]，凌等人。[17]，王等人。[28] 分别。虽然怀德等。[29]为LP问题研究梯度之前，他们提出了一个二次正则化项添加到使得阿莫斯和科特勒[3]的QP框架可以用来在LP。对于MILP，Ferber的等人的情况下。[13]意识到MILP转换为LP之前，所述LP制剂可以通过加入MILP切割面将其加强。
Elmachtoub 和 Grigas [12] 提出了一种不同但有效的方法，他们导出了一种基于凸代理损失的 MILP 次梯度方法，该方法不需要对优化问题进行微分。曼迪等人。[18]表明，即使在 MILP 的情况下，使用 LP 松弛的次梯度也足够且更有效。近日，Poganci C等。′ [25] 建议考虑argmin 算子的“隐式插值”来计算梯度。从概念上讲，他们的方法与 [12] 不同，但计算出的梯度与其密切相关。
贡献 与上述相反，我们建议在 LP 松弛中添加一个对数障碍项，这也使其具有两次可微性，并且是使用内点方法时 LP 求解的标准做法。此外，从这些方法如何计算它们的搜索方向中汲取灵感，我们建议区分 LP 的同质自双嵌入，而不是区分 KKT 条件。我们还解决了实际挑战，例如提前停止内点求解以避免数值问题和使用阻尼来避免病态矩阵。我们与现有技术的比较评估表明，这种方法产生了等同于更好的结果，同时是 LP 求解和 LP 任务损失梯度之间的方法学上更紧密的整合。
2问题描述
让我们考虑标准形式 [22] 中的混合整数线性规划 (MILP) 问题：
(1)
变量 x 和系数 c ∈ R k , A ∈ R p × k , b ∈ R p 。请注意，通过添加辅助松弛变量 [22] ，任何不等式约束 Cx ≤ d 都可以直接转换为该范式。我们用 x ? (c; A, b)表示方程 (1) 的最优解。
作为一个激励示例，请考虑 0-1 背包问题，该问题由一组具有已知值和重量的物品组成。目标是填充背包，从物品（例如 c）中获得尽可能多的价值，而不会超出背包的容量（在转换为标准形式后通过 A 和 b 表示）。
两阶段方法
我们考虑一个预测和优化设置，其中优化问题的系数 c papapmeter 是未知的。此外，我们假设训练实例{滋，CI} NI = 1是在我们的处置，并因此可用于训练的ML模型克（Z; θ ），由模型参数θ ，来预测? （ θ ）（用于记法简明，我们将c写在C代替（ θ ））。在这种情况下的简单的方法是将训练ML模型克（，θ ），以最小化ML损耗L（C，C），如均方误差，在不考虑下游优化任务。然后在测试情况下，首先将ML模型被用于预测?并且此后预测?被使用的值 由于这里分别执行预测和优化，这是一个两阶段的方法 [9]。
后悔
两阶段方法的缺点是没有考虑对优化任务的影响。就决策问题而言，不能保证最小化 ML 损失的训练能提供更好的性能 [15, 18]。训练WRT一个任务损耗L的模型参数（C，C; A，B），它考虑到下游优化任务，将允许端至端的替代方案。
对于（MI）LP问题，使用预测c中的成本，而不是地面实况C由遗憾测量（C，C ; A，B）= C> X * （C; A，B）- X ? (c; A, b) ; 即，在最优化的值差时，预测?而不是实际的数值℃。请注意，一个可同样使用C> X * （C; A，B），在所述预测优化时的实际值，为c> X * （C; A，B）是用于给定的C恒定。
由于这些损失考虑了预测对优化任务的影响；它们是有效的任务损失。
直接最小化遗憾的挑战在于在反向传播中通过网络反向传播它。为此，必须计算遗憾相对于模型参数的梯度，这涉及对优化问题的 argmin 进行微分。具体来说，为了根据任务损失 L( θ )更新模型参数 ( θ )，我们必须计算? L ?θ以执行梯度下降。通过使用链式法则，这可以分解如下[29]：
公式（2 ）
第一项是相对于该变量的任务损失的梯度，在遗憾用于（MI）LP情况下，这是简单地?大号? X * （C; A，B）= C。第三项是预测相对于模型参数的梯度，由现代深度学习框架自动处理。挑战在于计算中间项，我们将在下一节中对其进行扩展。算法 1 描述了高级端到端学习方法，其目标是最小化放松 MILP 问题的任务损失。
3 内点法端到端预测优化
对于离散MILP问题，argmin为c的分段恒定函数作为改变?将改变解x * （;仅在一些转变点[10] c ^ A，B）。因此，对于解空间中的每个点，梯度要么是 0，要么是未定义的。为了解决这个问题，首先，我们考虑方程 1 中 MILP 的连续松弛。结果是线性规划 (LP)，分别具有以下原始和对偶 [6]：
公式(4)
x 和 c、A、b 同前；和双变量 y 与松弛变量 t。我们的目标是计算梯度? X * （C; A，B）? ?由该LP的溶液相对于所述预测的?区分。
3.1 区分 KKT 条件
出于显而易见的原因，我们将方程 3 中 LP 的目标函数写为 f(c, x)。使用对应于对偶变量的拉格朗日乘数 y，方程 3 的拉格朗日松弛可以写为
公式(5)
通过求解 x ? (c; A, b ) 获得的最优原始对偶 (x, y)必须遵守 Karush-KuhnTucker (KKT) 条件，通过将方程 5 的偏导数设置为关于 x 和 y 获得0. 令 fx .= ? f ? x , fxx .= ? 2 f ? x2 , fcx .= ? 2 f ? c ? x ，我们得到：
公式(6) 、（7 ）
如果 f(c, x) 是二次可微的，我们可以求解方程 7，以获得? x ? c；但是对于 LP 问题 f(c, x) = c >x 因此 fx(c, x) = c 和 fxx(c, x) = 0 因此二阶导数总是 0。
平方正则项项 获得非零二阶导数的一种方法是添加二次正则项项λ kxk 2，其中λ是用户定义的加权超参数。这是由 [29] 提出的，然后他们使用技术来区分二次规划。另一种方法是添加这个平方项 f(c, x) := c >x + λ kxk 2 这会改变拉格朗日松弛并使方程 (7) 可微分两次。
对数障碍项 相反，我们建议添加对数障碍函数[7] λ Pk i=1 ln(xi)，它被原始-对偶内点求解器广泛使用[30]。此外，它包含约束 x ≥ 0，对于λ → 0，并且该约束是 LP 约束（方程（3））的一部分，但在使用拉格朗日松弛（方程（5）中的前一项）时它不存在）。
目标转换为 f(c, x) := c >x ? λ Pk i=1 ln(xi) 因此 fx(c, x) = c ? λ X ? 1 e 和 fxx(c, x) = λ X ? 2 e（其中 X 代表 diag(x)）。表示 t .= λ X ? 1 e 我们通过代入方程得到以下方程组。(6):
公式(8)
注意，方程 8 的第一个方程与方程 (3) 和方程 (4) 中原始对偶约束的约束相同。这说明了为什么对数障碍项是 LP 问题中最自然的工具，对数障碍函数的 KKT 条件定义了原始约束和对偶约束。另请注意，t .= λ X ? 1 e 意味着 x >t = k λ （其中 k = dim(x)）。
将方程 8 与 c 微分，我们得到了一个类似于方程 7 的方程组，其中 fxx 非零，求解这个方程得到? x ? (c;A,b) ? c 。请注意，这两种方法都涉及求解 LP 以找到最优解 (x, y)，然后围绕它计算? x ? c。
3.2 λ的选择和提前停止
由λ (>0)参数化的点序列 (x λ , y λ , t λ )定义了中心路径。当λ → 0 时，它收敛到 LP 的原始对偶解。基本上，中心路径提供了可以遵循以到达最佳点的路径。这就是为什么在内点求解器中，方程 8 是针对λ的递减序列求解的。请注意 x >t ( =k λ ) 是对偶间隙 [30] 并且λ → 0 表示在最佳 (x, y) 时对偶间隙为零。
现在，之前提出的方法遇到了一个警告。正如我们所展示的 fxx(c, x) = λ X ? 2 e，因此λ → 0 意味着 fxx → 0。
为了避免这种情况，我们建议在λ变得小于给定的λ截止值时立即停止内点求解器；那是在λ变得太小并且相应的小 fxx 导致数值不稳定之前。这种方法有两个优点：1) 由于λ不太接近 0，我们有更好的数值稳定性；2) 通过提前停止，内点法需要进行更少的迭代，因此计算时间更少。
我们注意到，在平方正则化项的情况下，必须指定一个固定的λ ；而在我们的例子中，内点求解器将系统地减小λ ，并且必须指定一个截止值以防止λ变得太小。
3.3 同质自对偶配方
已知原始–基于求解方程 (8) 的对偶内点求解器不能很好地处理不可行的解决方案，这会使找到初始可行点变得困难 [30]。相反，内点求解器通常使用齐次自对偶公式 [31]。这个公式总是有一个可行的解决方案，并且已知会生成中心良好的点 [24]。由于这个优势，当迭代更新内点时，解决以下更大的公式（HSD公式）而不是（8）。这个公式总是有一个解，其中 (x, τ ) 和 (t, κ ) 是严格互补的：
公式(9)
3.3,1 前向传播
在前向传递中，我们使用现有的齐次内点算法 [4] 来搜索 LP 解决方案。它从一个内部点 (x, y, t, τ , κ ) 开始，其中 (x, t, τ , κ ) > 0，并通过牛顿法迭代更新这个点以获得λ的递减序列。基于方程。(9)，在每一步中，求解以下牛顿方程系统，以找到更新内点的方向 dx, dy, dt, d τ , d κ ：
公式（10 ）、（11 ）
3.3.2 计算反向传播的梯度
较大的 HSD 公式包含比方程 8 中关于 LP 解的 KKT 条件更多的信息，因为添加了τ和κ ，其中κ / τ表示对偶间隙。因此，为了计算反向传播的梯度，我们建议不区分方程 8，而是区分方程 9 中的 HSD 公式 wrtc 我们按照补充文件中附录 A.2 中解释的程序进行。这使我们能够编写以下方程组 (T = diag(t))：
公式（12 ）
注意在前向传递中求解的方程 11 之间的相似性，以获得搜索方向 dx，以在给定固定系数 c 的情况下改进 x，而在我们的反向传递中求解方程 12 以获得梯度? x ? c之间的相似性，用于在给定固定 x 的情况下如何改进 c！
此外，因为它们仅在右手边不同，所以我们可以使用与附录 A.1 中解释的相同的程序来计算这组方程中所需的? x ? c。
实现考虑 在附录 A.1 的过程中，我们必须求解形式为 Mv = r 的系统，其中 M = AT ? 1XA>。尽管对于全行秩 A，M 应该是正定 (PD) 矩阵，但在实际实现中，我们经常观察到 M 不是 PD 矩阵。
为了避免这种情况，我们用其 Tikhonov 阻尼[19]形式Mˉ := M + α I替换 M ，其中α > 0 是阻尼因子。
4 实验
我们在三个预测和优化问题上评估我们的基于内部点的方法 (IntOpt)。我们将其与两阶段方法、QPTL（二次编程任务损失）[29] 方法和 SPO 方法 [12、18] 进行比较。训练是在松弛问题上进行的，但我们通过将离散 MILP 求解为最优来评估测试数据的目标和遗憾。我们将学习率、时期和权重衰减视为超参数，通过初始随机搜索选择，然后在验证集上进行网格搜索。对于建议的 IntOpt 方法，阻尼因子的值和λ截止值由网格搜索选择。
神经网络和 MILP 模型已分别使用 PyTorch 1.5.0 [23] 和 Gurobipy 9.0 [14] 实现。同类算法实现基于 SciPy 1.4.1 Optimize 模块之一。所有实验均在配备 8 × Intel? Core ? i7-8550U CPU @ 1.80GHz 和 16 Gb RAM的笔记本电脑上执行。1
房地产投资的背包公式。在我们的第一个实验中，我们将房地产投资者的决策制定为 0-1 背包问题。预测问题是在房屋开工前估计房屋的销售价格。房地产机构将使用该预测来决定在预算约束限制下进行哪些项目。我们假设每个项目的建设成本为该机构所知。我们使用 Rafiei 和 Adeli [26] 的数据集，它包含两组特征：a) 房屋的物理和财务特性；b) 衡量房地产市场状况的经济变量。经济变量最多可在建设开始前的五个时期内使用。
我们在 5 个时期的经济变量中使用 LSTM 模型，然后将它们与物理和财务特征连接起来，然后将它们传递到一个全连接层进行预测。
在 372 个实例中，310 个用于训练和交叉验证，62 个用于测试模型性能。
在表 1 中，我们展示了预测的 MSE 损失和使用预测获得的遗憾。显然，两阶段方法的 MSE 损失最低，它优化了训练集的 MSE。请注意，对于线性目标，预测值相对于目标是尺度不变的，因此较高的 MSE 并不表示优化结果较差。
SPO 能够使用其次梯度方法在最终目标方面超越两阶段方法的性能。直观地，次梯度指示应该保留哪些项目以及哪些项目应该删除，这可能会为这个优化问题提供更强的学习信号。发现我们的方法和 QPTL 的性能都比两阶段方法差，IntOpt 略好于 QPTL。另请注意，两阶段模型实现了非常低的 MSE，这意味着可以传播到优化问题中的错误相对较少。
能源成本意识调度这是一个资源受限的日前作业调度问题，以最小化总能源成本 [参见 27]。任务必须分配给给定数量的机器，其中每个任务都有持续时间、最早开始时间、最晚结束时间、资源需求和电力使用情况，并且每台机器都有资源容量限制。另外，任务一旦开始就不能中断，也不能迁移到另一台机器上，必须在午夜之前完成。时间在 48 个时隙中离散化。由于日前能源价格是未知的，因此必须首先针对每个时间段对其进行预测。
能源价格数据取自爱尔兰单一电力市场运营商 (SEMO) [15]。它包含 2011-2013 年每 30 分钟间隔的历史能源价格数据。在可用的 789 天中，552 天用于训练，60 天用于验证，177 天用于测试。每个时间段实例都有日历属性；天气特征的日前估计；SEMO 日前预测的能源负荷、风能生产和价格；和实际风速、温度、二氧化碳强度和价格。在实际属性中，我们只保留实际价格，并将其用作预测目标。
我们使用两种神经网络，一种没有隐藏层（0 层），一种只有一个隐藏层（1 层）。不同方法的比较如表 2 所示。我们可以看到，对于所有方法，多层网络（1 层）略微过度拟合并且性能比 0 层差。
0 层模型在遗憾和预测准确性方面都表现最好。我们的 IntOpt 方法能够产生最低的遗憾，其次是带有 QPTL 的 SPO
公式的选择和λ截止值我们更深入地研究了区分公式的选择差异，以及λ或λ截止值的选择。结果在表 3 中，表明 HSD 配方表现最佳。该实验还表明，使用λ阈值停止前向传递是有效的，但阈值较低的结果更差（我们观察到数值问题）。尽管0.1的λ -cut-off 似乎是最佳选择，但我们建议将其视为超参数。
最短路径问题该实验涉及解决网格上的最短路径问题，类似于 [12]。我们使用由 231 个节点和 2861 条边组成的推特自我网络作为网络结构，而不是完全合成的小规模数据[16]。为了解决这个子图中的最短路径问题，我们创建了 115 个问题实例，每个实例具有不同的源和目标对。这是一个预测和优化问题，在解决最短路径问题之前，首先必须根据节点和边缘特征预测边缘强度。
用户在观察期间使用的一组主题标签和提及是相应节点的特征变量。为了生成与特征相关的边权重，我们使用了一种受 [29] 启发的随机网络方法：我们构建了一个随机的 3 层网络，该网络接收其边的节点特征和随机数的串联作为输入。我们将一些额外的高斯噪声添加到结果输出中，并将其设置为边缘权重。所有边都使用相同的网络。
作为预测模型，我们使用两种神经网络，即具有 1 个和 2 个隐藏层。在 115 个实例中，我们使用 80 个进行训练，15 个用于模型验证和超参数选择，20 个用于模型测试。
图 1：Groundtruth 与预测表 4 显示了在测试实例上获得的平均 MSE 损失和遗憾。IntOpt 在遗憾方面表现最好，尽管略有下降。QPTL 和 IntOpt 的 MSE 值明显很高，但我们重申，从优化的角度来看，给定线性目标，预测是尺度不变的。
我们可以在图 1 中清楚地看到这种效果，其中 IntOpt 和两阶段模型的预测是根据真实情况绘制的。在这里我们解释一下为什么IntOpt的MSE高而遗憾低。我们观察到，由于线性目标的尺度不变性，IntOpt 预测通常会从真实值偏移几个数量级。
但除此之外，很容易发现两组预测之间关系的相似性。如果仔细观察，确实可以看出 IntOpt 错误地预测了极端情况，我们只能假设这对优化问题影响不大，因为 IntOpt 获得较低的遗憾。这验证了 IntOpt 方法能够仅从优化问题的间接监督中学习预测器和特征变量之间的关系。
讨论在考虑的三个实验设置中，对于第一个实验，预测和优化任务都相当简单，而其他两个实验的优化任务具有挑战性。看起来，与 SPO 相比，我们的方法在解决更简单的问题时表现不佳，但对具有挑战性的问题产生了更好的结果。
我们想指出的是，SPO 方法可以利用任何黑盒求解器作为优化预言机，而 QPTL 和 IntOpt 都使用内点算法来解决优化问题。因此，SPO 在第一个问题上的卓越性能的另一个原因可能是这些问题实例更适合于除内点之外的算法，并且 SPO 可能受益于它使用 Gurobi 作为黑盒求解器的事实。在其他背包实例（见附录 A.4）的情况下，IntOpt 和 QPTL 的性能优于 SPO。
5 结论
我们考虑了区分神经网络内部端到端预测和优化的 LP 优化问题的问题。我们开发了 IntOpt，这是一种有充分根据的基于内点的方法，它通过使用对数屏障区分齐次自对偶公式 LP 来计算梯度。该模型使用 MILP 优化问题进行评估，并在求解和区分优化问题之前执行连续松弛。在三组实验中，我们的框架与最先进的技术相当或更好。
通过为 LP 提出一个内点公式，而不是添加二次项并使用 QP 的结果，我们使用来自 LP 和 MILP 的最先进内点方法的见解开辟了进一步改进和更紧密集成的道路。收紧 LP 松弛的技术（例如 [13]）可能会进一步使我们的方法受益。
运行时间是一个潜在的瓶颈，因为在复杂的能源成本调度问题中，一个 epoch 可能需要长达 15 分钟。我们确实注意到我们使用了同构算法的普通实现，而不是像 Gurobi 和 CPlex 这样的行业级优化求解器。此外，由于前向传递中的方向计算和后向传递中的梯度计算相似，因此在改进方程系统求解以及跨时期缓存和重用结果方面有更大的潜力。
|