A fast algorithm to minimize prediction loss of the optimal solution in inverse optimization problem of MILP

本文解决了最优整数线性规划（MILP）的预测损失最小化问题，该问题是逆优化问题之一。虽然现有方法可以近似地解决这个问题，但在高维情况下，由于它们在减少权重的预测损失方面效率低下，因此最小化预测损失的实现计算成本很高。我们提出了一种快速算法来最小化MILP的预测损失。为了证明这个性质，我们将最小化预测损失的问题归因于最小化次优损失（SL）的问题，该问题是凸的。如果预测损失不为零，我们可以将SL适应为具有正下界的估计损失（SPO损失），从而使我们能够评估权重的预测损失。因此，我们证明了所提出的算法可以有效地减少权重的预测损失并实现最小的预测损失值。我们的数值实验表明，我们的算法成功地实现了最小的预测损失。与现有方法相比，我们的算法表现出更小的维度效应，并在不到1/7的迭代次数内最小化了预测损失。特别是在高维情况下，我们的算法相对于现有算法将预测损失显著提高了两个数量级。

本论文旨在解决最小化给定数据下MILP最优解（PLS）的预测损失，这是一种反向优化问题。现有方法可以近似解决此问题，但在高维情况下实现最小化PLS是计算上昂贵的，因为它们在减少权重的预测损失（PLW）方面效率低下。

本论文提出了一种快速算法来最小化MILP的PLS。为了证明这一属性，我们将最小化PLS的问题归因于最小化次优性损失（SL）的问题，该问题是凸的。如果PLS不消失，我们可以适应SL以具有估计损失（SPO损失）和正下界，这使我们能够评估PLW。因此，我们证明了所提出的算法可以有效地减少PLW并实现最小值PLS。

本文的亮点是成功通过实验证明算法可以成功地实现最小化PLS。与现有方法相比，本算法展现出更小的维度效应，并且在不到1/7的迭代次数内最小化了PLS。特别是在高维度情况下，与现有算法相比，本算法将PLS显着提高了两个数量级。

近期在这个领域中的相关研究包括：Inverse optimization for MILP via suboptimality minimization；Robust mixed integer programming with data-driven objective and constraint uncertainty；Solving mixed integer optimization problems under distributional uncertainty via robust optimization；Approximate robust mixed integer optimization with distributionally robust constraints。