Please use this identifier to cite or link to this item:
Title: Regret Models and Preprocessing Techniques for Combinatorial Optimization under Uncertainty
Keywords: regret, worst-case CVaR, mixed integer program, polynomial time algorithm, preprocessing technique, quadratic uncontraint binary optimization
Issue Date: 11-Jul-2013
Citation: SHI DONGJIAN (2013-07-11). Regret Models and Preprocessing Techniques for Combinatorial Optimization under Uncertainty. ScholarBank@NUS Repository.
Abstract: We propose some probabilistic models for combinatorial optimization with uncertainty. The first model is to minimize the worst-case condition value-at-risk (WCVaR) of cost for a linear combinatorial optimization problem. We show that under the marginal distribution and marginal moment models, the proposed random model can be solved as a deterministic optimization problem. The second model is to minimize the WCVaR of regret for the same random combinatorial optimization. For the class of combinatorial optimization problems with a compact convex hull representation, some polynomial sized mixed integer linear program (MILP) and mixed integer second order cone program (MISOCP) are formulated. For the subset selection problem, the probabilistic regret model is shown to be solvable in polynomial time. Finally, we extend the Quadratic Convex Reformulation (QCR) method to solve quadratic unconstrained binary optimization problems where the linear part of the objective is random and belongs to a Frechet class of distributions.
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
PhD_Thesis_SDJ(version7_final).pdf925.9 kBAdobe PDF



Page view(s)

checked on Mar 31, 2019


checked on Mar 31, 2019

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.