Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization
Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization
复制标题
DOI：
10.1287/ijoc.2022.1162
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Rishabh Gupta-;Qi Zhang
中科院分区：
文献类型：
--
作者：
Rishabh Gupta-;Qi Zhang
这项工作解决逆线性优化的目标是推断未知的成本向量的线性规划。具体来说，我们考虑数据驱动的设置，其中可用的数据是对应于线性规划的不同实例的最优解的噪声观测。我们引入了一个新的配方的问题，相比其他现有的方法，允许恢复的限制性较小，一般更适当的容许成本估计。可以证明，这个逆优化问题产生有限个解，并且我们开发了一个精确的两阶段算法来确定所有此类解。此外，我们提出了一个有效的分解算法来解决大的问题。该算法自然扩展到在线学习环境，当新数据随着时间的推移变得可用时，它可用于快速更新成本估算。对于在线设置，我们进一步开发了一个有效的自适应采样策略，指导下一个样本的选择。所提出的方法的有效性证明在计算实验中涉及两个应用程序，客户偏好学习和生产计划的成本估计。结果表明，显着减少计算和采样的努力。
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.