Data-driven Inverse Linear Programming: Integrating Inverse Optimization and Machine Learning

dc.contributor.advisorLee, Taewoo
dc.contributor.committeeMemberLim, Gino J.
dc.contributor.committeeMemberLin, Ying
dc.contributor.committeeMemberMang, Andreas
dc.contributor.committeeMemberHuchette, Joey
dc.creatorShahmoradi, Zahed
dc.creator.orcid0000-0003-1419-681X 2021 2021
dc.description.abstractInverse linear programming (LP) has received increasing attention due to its potential to infer efficient optimization formulations that can closely replicate the behavior of a complex system. In this thesis, we integrate data-driven inverse optimization techniques with ideas from statistical machine learning to improve the stability and applicability of inverse optimization in settings that involve imperfect data and observations from decision makers with different preferences. In Chapter 1 of this thesis, we provide background information about inverse optimization and discuss its conceptual similarities with problems in machine learning. In Chapter 2, we review relevant literature on inverse optimization and then present the contribution of this thesis to the literature. In Chapter 3, we first discuss the sensitivity of the inversely inferred parameters and corresponding forward solutions from the existing inverse LP methods to noise, errors, and uncertainty in the input data, and present illustrative examples highlighting their limited applicability in data-driven settings. Then, we introduce the notion of inverse and forward stability in inverse LP and borrow ideas from quantile regression to propose a novel inverse LP method that determines a set of objective functions that are stable under data imperfection and generate forward solutions close to the relevant subset of the data. We formulate the inverse model as a tractable large-scale mixed-integer program (MIP), called mixed-integer quantile inverse optimization (MQIO), and apply it to diet survey data to recommend diets that are consistent with the individual's food preferences. In Chapter 4, we analyze the complexity of the large-scale MQIO formulation from Chapter 3 and elucidate its connection to biclique problems, which we exploit to develop an exact algorithm and heuristics that solve much smaller MIPs instead to construct a solution to the original problem. We then numerically evaluate the performance of the proposed algorithms on randomly generated instances. Lastly, we show that a modified version of the proposed heuristics can accommodate online settings and demonstrate them in the diet recommendation and transshipment applications. Finally, in Chapter 5 we integrate inverse optimization and clustering and propose a new clustering approach, called optimality-based clustering, which clusters the data points based on their encoded decision preferences. We assume that each data point is a decision made by a rational decision maker (i.e., by approximately solving an optimization problem), and cluster the data points by identifying a common objective function of the optimization problems for each cluster such that the worst-case optimality gap for the data points within each cluster is minimized. We propose three clustering models and present tractable MIP formulations that lead to lower and upper bound solutions. We demonstrate these clustering models using various-sized randomly generated instances.
dc.description.departmentIndustrial Engineering, Department of
dc.format.digitalOriginborn digital
dc.identifier.citationPortions of this document appear in: Shahmoradi, Zahed, and Taewoo Lee. "Quantile inverse optimization: Improving stability in inverse linear programming." Operations Research (2021); and in: Shahmoradi, Zahed, and Taewoo Lee. "Optimality-based clustering: An inverse optimization approach." Operations Research Letters 50, no. 2 (2022): 205-212.
dc.rightsThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. UH Libraries has secured permission to reproduce any and all previously published materials contained in the work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).
dc.subjectInverse optimization
dc.subjectDecision Making
dc.subjectMachine Learning
dc.titleData-driven Inverse Linear Programming: Integrating Inverse Optimization and Machine Learning
dcterms.accessRightsThe full text of this item is not available at this time because the student has placed this item under an embargo for a period of time. The Libraries are not authorized to provide a copy of this work during the embargo period.
local.embargo.terms2023-08-01 College of Engineering Engineering, Department of Engineering of Houston of Philosophy


Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
1.31 MB
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
4.43 KB
Plain Text
No Thumbnail Available
1.82 KB
Plain Text