Applications for optimization with uncertain data in practice often feature a possibility to reduce the uncertainty at a given query cost, e.g., by conducting measurements, surveys, or paying a third party in advance to limit the deviations. To model this type of applications we introduce the concept of optimization problems under controllable uncertainty (OCU). For an OCU we assume the uncertain cost parameters to lie in bounded, closed intervals. The optimizer can shrink each of these intervals around a certain value (hedging point) possibly reducing it to a single point. Depending on whether the hedging points are known in advance or not, different types of OCU arise. Moreover, the models may differ with respect to when the narrowing down, the underlying optimization, and the revelation of true data take place.
We study two different problem settings – one with known and one with unknown hedging points – in more detail, where we handle the remaining uncertainty by the paradigm of robust optimization. For both settings, we provide bounds on the optimal objective value and a single-level non-linear reformulation. Furthermore, we state assumptions under which the three- respectively four-level problem can be solved as a single-level mixed-integer linear program. We also show that in robust OCU an optimizer might query a parameter solely to reduce the uncertainty for other parameters (budget deflection). We give sufficient conditions to avoid this phenomenon.