טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentGuslitzer Elana
SubjectUncertainty-Immunized Solutions in Linear Programming
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Arkadi Nemirovski


Abstract

The data of real-world optimization problems typically are not known exactly. Robust Optimization methodology associates with an uncertain problem its Robust Counterpart (RC), which uncertainty-immunized solution must satisfy all realizations of the constraints associated with a given uncertainty set. This approach assumes that all the variables represent “decisions” that must be made before the true values of the data become known. However, in many problems some variables are “analysis variables” that can “tune” themselves to the true values of the data. Hence, constraints of RC are too conservative. Distinguishing between the decision and the analysis variables, we defined Extended RC (ERC), letting the analysis variables depend on the uncertain data. The ERC is more flexible than the RC, thus enabling wider feasible set and better optimal value, while still satisfying all the realizations of the constraints. In the cases when ERC is computationally intractable, we introduced Approximate ERC (AERC), and prove its computational tractability. Numerical examples demonstrate high applied potential of the proposed approach.