Optimizing the Expected Maximum of Two Linear Functions Defined on a Multivariate Gaussian Distribution

David Bergman (), Carlos Cardonha (), Jason Imbrogno () and Leonardo Lozano ()
Additional contact information
David Bergman: Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06268
Carlos Cardonha: Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06268
Jason Imbrogno: Department of Finance, Economics, and Data Analytics, University of North Alabama, Florence, Alabama 35632
Leonardo Lozano: Department of Operations, Business Analytics, and Information Systems, University of Cincinnati, Cincinnati, Ohio 45221

INFORMS Journal on Computing, 2023, vol. 35, issue 2, 304-317

Abstract: We study stochastic optimization problems with objective function given by the expectation of the maximum of two linear functions defined on the component random variables of a multivariate Gaussian distribution. We consider random variables that are arbitrarily correlated, and we show that the problem is NP-hard even if the space of feasible solutions is unconstrained. We exploit a closed-form expression for the objective function from the literature to construct a cutting-plane algorithm for a highly nonlinear function, which includes the evaluation of the cumulative distribution function and probability density function of a standard normal random variable with decision variables as part of the arguments. To exhibit the model’s applicability, we consider two featured applications. The first is daily fantasy sports, where the algorithm identifies entries with positive returns during the 2018–2019 National Football League season. The second is a special case of makespan minimization for two parallel machines and jobs with uncertain processing times; for the special case where the jobs are uncorrelated, we prove the equivalence between its deterministic and stochastic versions and show that our algorithm can deliver a constant-factor approximation guarantee for the problem. The results of our computational evaluation involving synthetic and real-world data suggest that our discretization and upper bounding techniques lead to significant computational improvements and that the proposed algorithm outperforms suboptimal solutions approaches.

Keywords: Benders decomposition; scheduling; stochastic methods; sports analytics (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1259 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:2:p:304-317

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().