论文标题
数据驱动的逆线性优化的分解和自适应抽样
Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization
论文作者
论文摘要
这项工作解决了逆线性优化，目标是推断线性程序的未知成本向量。具体而言，我们考虑了数据驱动的设置，其中可用数据是与线性程序不同实例相对应的最佳解决方案的嘈杂观察。我们介绍了一个新的问题，与其他现有方法相比，该问题允许恢复较低的限制性且通常更合适的可允许的成本估算集。可以表明，此反优化问题会产生有限数量的解决方案，并且我们开发了一种精确的两相算法来确定所有此类溶液。此外，我们提出了一种有效的分解算法来解决大量问题的实例。该算法自然扩展到在线学习环境中，随着新数据随着时间的流逝，可以使用它来提供成本估算的快速更新。对于在线环境，我们进一步制定了一种有效的自适应抽样策略，可以指导下一个样本的选择。在涉及两种应用，客户偏好学习和生产计划的成本估算的计算实验中证明了所提出方法的功效。结果显示计算和采样工作的大幅减少。
This work addresses inverse linear optimization where the goal is to infer the unknown cost vector of a linear program. Specifically, we consider the data-driven setting in which the available data are noisy observations of optimal solutions that correspond to different instances of the linear program. We introduce a new formulation of the problem that, compared to other existing methods, allows the recovery of a less restrictive and generally more appropriate admissible set of cost estimates. It can be shown that this inverse optimization problem yields a finite number of solutions, and we develop an exact two-phase algorithm to determine all such solutions. Moreover, we propose an efficient decomposition algorithm to solve large instances of the problem. The algorithm extends naturally to an online learning environment where it can be used to provide quick updates of the cost estimate as new data becomes available over time. For the online setting, we further develop an effective adaptive sampling strategy that guides the selection of the next samples. The efficacy of the proposed methods is demonstrated in computational experiments involving two applications, customer preference learning and cost estimation for production planning. The results show significant reductions in computation and sampling efforts.
