Classical budget uncertainty is widely used in robust optimization. It bounds the aggregate absolute deviation of uncertain parameters from nominal values and yields tractable robust counterparts. In many applications, however, information concerns aggregate signed deviations. We therefore study signed budget uncertainty, in which bounds are imposed on signed aggregates rather than absolute deviations. For robust mixed-integer optimization problems with binary uncertainty-affected variables, we derive a compact robust counterpart requiring only two additional variables and two additional constraints per uncertainty-affected constraint, independently of the number of uncertain coefficients. This contrasts sharply with the standard robust counterpart, whose size grows linearly with the number of uncertain parameters. We further study laminar signed budget uncertainty to capture hierarchical structures arising from geographical, organizational, or categorical information. We derive a compact robust counterpart whose size scales with the number of aggregate sets rather than the number of uncertain coefficients. For problems with a single uncertainty-affected constraint, we show that the robust problem can alternatively be solved through \(2^K\) nominal problems, where \(K\) is the number of aggregate sets. Experiments demonstrate the computational advantages and show that signed budget uncertainty can produce solutions not obtainable by adjusting the classical budget parameter.
Signed Budget Uncertainty for Robust Mixed-Integer Optimization
\(\)