Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Warning The system is temporarily closed to updates for reporting purpose.

Noyan, Nilay and Ruszczynski, Andrzej (2008) Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints. Mathematical programming, 114 (2). pp. 249-275. ISSN 0025-5610 (Print) 1436-4646 (Online)

[thumbnail of stvkaf01937.pdf] PDF
stvkaf01937.pdf
Restricted to Repository staff only

Download (363kB) | Request a copy

Abstract

Stochastic dominance relations are well-studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance (SSD) constraints can be solved by linear programming (LP). However, problems involving first order stochastic dominance (FSD) constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 01 linear programming formulation of a discrete FSD-constrained optimization model and present an LP relaxation based on SSD constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional SSD-constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a portfolio optimization problem.
Item Type: Article
Uncontrolled Keywords: stochastic programming; stochastic dominance; valid inequalities; disjunctive cuts; conditional value at risk
Subjects: Q Science > Q Science (General)
T Technology > T Technology (General)
Q Science > QA Mathematics
Divisions: Faculty of Engineering and Natural Sciences
Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Depositing User: Nilay Noyan
Date Deposited: 17 Feb 2007 02:00
Last Modified: 26 Apr 2022 08:04
URI: https://research.sabanciuniv.edu/id/eprint/234

Actions (login required)

View Item
View Item