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.
翻译:这项工作针对的是反线性优化,目的是推断线性方案的未知成本矢量。 具体地说, 我们考虑由数据驱动的设置, 即现有数据是针对符合线性程序不同情况的最佳解决方案的杂音观测; 我们引入了一个新的问题公式, 与其他现有方法相比, 使得能够回收一套限制较少、一般更合适的成本估算; 可以看到, 反线性优化问题会产生数量有限的解决方案, 我们开发了精确的两阶段算法, 以确定所有这类解决方案。 此外, 我们建议了一种高效分解算法, 以解决大量的问题。 算法自然延伸到一个在线学习环境, 可以在新的数据随时可用时使用它来快速更新成本估算。 对于在线环境, 我们进一步制定有效的适应性抽样战略, 指导下一批样本的选择。 拟议方法的效力体现在涉及两种应用、 客户偏好学习 和 生产规划成本估算 的计算实验中。 计算结果显示, 计算和抽样工作显著减少 。