A cutting-surface method for uncertain linear programs with polyhedral stochastic dominance constraints

Tito Homem-De-mello*, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1250-1273
Number of pages24
JournalSIAM Journal on Optimization
Volume20
Issue number3
DOIs
StatePublished - 2009

Keywords

  • Convex programming
  • Cutting plane algorithms
  • Linear programming
  • Stochastic dominance
  • Stochastic ordering
  • Utility functions

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'A cutting-surface method for uncertain linear programs with polyhedral stochastic dominance constraints'. Together they form a unique fingerprint.

Cite this