Enforcing non-anticipativity in a two-stage stochastic program for scheduling with endogenous uncertainties

Abstract: Most of the research in two-stage stochastic programs has focused on the case of exogenous uncertainties, that is, uncertainties that are not influenced by any decision that the stochastic program takes. In this talk I will present work on a scheduling problem arising in the analytical services sector, for which the uncertainty is endogenous. In particular, the time of realization of uncertainty is defined by the decisions taken by the stochastic program. In such a context, enforcing non-anticipativity becomes a challenging proposition, since one does not know a priori when uncertainty is realized.

The typical approach for these types of problems has been to introduce binary variables that indicate when exactly uncertainty gets realized. While these binary variables are useful to more easily enforce non-anticipativity constraints, they greatly complicate the solution to such models and much of the research focus has been to develop better algorithms to handle such binary variables and decompose such problem.

In this work, we present a model for scheduling services in the analytical services sector, where the uncertainty is in the analysis results. The developed model is based on a flow formulation of a time discretized version of the problem. Due to this particular structure, a careful choice of parameters allows us to develop a two-stage model that enforces non-anticipativity without the addition of any new binary variables. We will discuss advantages and drawbacks of such approach and potential future directions of research.

This is based on joint work with Kavitha Menon and Luis Ricardez-Sandoval.

optimization and control

Audience: researchers in the topic

---

Discrete Optimization Talks

Series comments: DOTs are virtual discrete optimization talks, organized by Aleksandr M. Kazachkov and Elias B. Khalil. To receive updates about upcoming DOTs, please join our mailing list. Topics of interest include theoretical, computational, and applied aspects of integer and combinatorial optimization.

The format is two thirty-minute talks and time for questions. Currently (January-April 2021), the seminars are scheduled on end-of-the-month Fridays at 1:00 p.m. ET. A special feature of DOTs is a social component. After a usual talk, you might grab a tea/coffee and chat with other attendees. Why not here too? Join us for some informal discussion after each DOT and throughout the week on our Discord channel.

---