Paper Info
Title
A Cutting-Surface Method for Uncertain Linear Programs with Polyhedral Stochastic Dominance Constraints
Abstract
In this paper we study linear optimization problems with a newly introduced concept of multidimensional polyhedral linear second-order stochastic dominance constraints. By using the polyhedral properties of this dominance condition, we present a cutting-surface algorithm and show its finite convergence. The cut generation problem is a difference of convex functions (DC) optimization problem. We exploit the polyhedral structure of this problem to present a novel branch-and-cut algorithm that incorporates concepts from concave minimization and binary integer programming. A linear programming problem is formulated for generating concavity cuts in our case, where the polyhedra are unbounded. We also present duality results for this problem relating the dual multipliers to utility functions, without the need to impose constraint qualifications, which again is possible because of the polyhedral nature of the problem. Numerical examples are presented showing the nature of solutions of our model. (A corrected PDF has been appended to the original.)
Year
DOI
Venue
2009
10.1137/08074009X
SIAM Journal on Optimization
Keywords
Field
DocType
polyhedral nature,multidimensional polyhedral linear second-order,present duality result,binary integer programming,linear programming problem,polyhedral property,polyhedral stochastic dominance constraints,optimization problem,uncertain linear programs,polyhedral structure,cut generation problem,linear optimization problem,cutting-surface method,linear program,branch and cut,convex function,stochastic dominance,second order,stochastic ordering,stochastic order,convex programming,linear optimization,linear programming
Discrete mathematics,Mathematical optimization,Polyhedron,Stochastic dominance,Frameworks supporting the polyhedral model,Convex function,Duality (optimization),Linear programming,Optimization problem,Convex optimization,Mathematics
Journal
Volume
Issue
ISSN
20
3
1052-6234
Citations 
PageRank 
References 
22
0.85
13
Authors
2
Name
Order
Citations
PageRank
Tito Homem-de-Mello185867.26
Sanjay Mehrotra252177.18