Abstract
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 with 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 become 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.
Original language | English (US) |
---|---|
Pages (from-to) | 2720-2735 |
Number of pages | 16 |
Journal | INFORMS Journal on Computing |
Volume | 34 |
Issue number | 5 |
DOIs | |
State | Published - Sep 2022 |
Bibliographical note
Funding Information:Funding: The authors gratefully acknowledge the financial support from the National Science Founda-tion [Grant 2044077]. R. Gupta acknowledges financial support from a departmental fellowship sponsored by 3M.
Funding Information:
The authors gratefully acknowledge the financial support from the National Science Foundation [Grant 2044077]. R. Gupta acknowledges financial support from a departmental fellowship sponsored by 3M. The authors gratefully acknowledge the Minnesota Supercomputing Institute at the University of Minnesota for providing resources that contributed to the research results reported in this paper.
Publisher Copyright:
© 2022 INFORMS.
Keywords
- adaptive sampling
- inverse optimization
- online learning