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

DOI10.1287/IJOC.2022.1259arXiv2112.07002OpenAlexW4313294474MaRDI QIDQ6203367FDOQ6203367

Authors:

Publication date: 28 February 2024

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

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 that can be seen as an extension of the integer L-shaped method for a highly nonlinear function, which includes the evaluation of the c.d.f and p.d.f 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 sub-optimal solutions approaches.

Full work available at URL: https://arxiv.org/abs/2112.07002

Recommendations

• scientific article; zbMATH DE number 3887440
• STOCHASTIC OPTIMIZATION OF MULTIPLICATIVE FUNCTIONS WITH NEGATIVE VALUE
• Optimality functions in stochastic programming
• A Gaussian upper bound for Gaussian multi-stage stochastic linear programs
• Bicriteria problem of stochastic optimization

zbMATH Keywords

schedulingBenders decompositionstochastic methodssports analytics

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

This page was built for publication: Optimizing the Expected Maximum of Two Linear Functions Defined on a Multivariate Gaussian Distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203367)