Probing-Enhanced Stochastic Programming: Theory, Insights, and Algorithms from Newsvendor to Lot-Sizing

We study how costly information acquisition can be integrated into stochastic programming to improve decisions under uncertainty. We consider a probing-enhanced framework in which a decision maker can selectively observe signals correlated with future demand before committing to operational decisions. This transforms the classical stochastic programming paradigm into a three-stage problem that jointly captures information acquisition, adaptive decision-making, and recourse. The analysis begins with the newsvendor problem, which offers a simple setting to examine the value of probing and to develop intuition about the interplay between information and decisions under uncertainty. The resulting insights help clarify the underlying mechanisms and provide a useful foundation for a more complex setting. We then consider a probing-enhanced multi-item capacitated lot-sizing problem, in which information acquisition must be coordinated with setup decisions, production quantities, and limited capacity. In contrast to the newsvendor setting, the challenge here stems not only from the decision-dependent information structure, but also from the intrinsic difficulty of the underlying mixed-integer problem. Their combination gives rise to a particularly demanding optimization model and motivates the search for more effective solution methods. To this end, the problem is formulated as a three-stage stochastic mixed-integer program, and new structural and algorithmic results are developed, including dominance rules for eliminating redundant probing decisions and enhanced solution approaches that significantly improve scalability on large instances.