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
dc.date.accessioned2022-06-19T00:24:25Z
dc.date.createdAugust 2021
dc.date.issued2021-08
dc.date.submittedAugust 2021
dc.date.updated2022-06-19T00:24:26Z
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.format.mimetypeapplication/pdf
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.identifier.urihttps://hdl.handle.net/10657/9407
dc.language.isoeng
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.subjectRegression
dc.subjectClustering
dc.titleData-driven Inverse Linear Programming: Integrating Inverse Optimization and Machine Learning
dc.type.dcmiText
dc.type.genreThesis
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.lift2023-08-01
local.embargo.terms2023-08-01
thesis.degree.collegeCullen College of Engineering
thesis.degree.departmentIndustrial Engineering, Department of
thesis.degree.disciplineIndustrial Engineering
thesis.degree.grantorUniversity of Houston
thesis.degree.levelDoctoral
thesis.degree.nameDoctor of Philosophy

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
SHAHMORADI-DISSERTATION-2021.pdf
Size:
1.31 MB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 2 of 2
No Thumbnail Available
Name:
PROQUEST_LICENSE.txt
Size:
4.43 KB
Format:
Plain Text
Description:
No Thumbnail Available
Name:
LICENSE.txt
Size:
1.82 KB
Format:
Plain Text
Description: