Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/48670
Title: Regret Models and Preprocessing Techniques for Combinatorial Optimization under Uncertainty
Authors: SHI DONGJIAN
Keywords: regret, worst-case CVaR, mixed integer program, polynomial time algorithm, preprocessing technique, quadratic uncontraint binary optimization
Issue Date: 11-Jul-2013
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/48670
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

OPEN

NoneView/Download

Page view(s)

133
checked on Dec 11, 2017

Download(s)

296
checked on Dec 11, 2017

Google ScholarTM

Check


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