  Gamma uncertainty sets have been introduced for adjusting the degree of
conservatism of robust counterparts of (discrete) linear programs. The
contribution of this paper is a generalization of this approach to (mixed
integer) nonlinear optimization programs. We focus on the cases in which the
uncertainty is linear or concave but also derive formulations for the general
case. By applying reformulation techniques that have been established for
nonlinear inequalities under uncertainty, we derive equivalent formulations of
the robust counterpart that are not subject to uncertainty. The computational
tractability depends on the structure of the functions under uncertainty and
the geometry of its uncertainty set. We present cases where the robust
counterpart of a nonlinear combinatorial program is solvable with a polynomial
number of oracle calls for the underlying nominal program. Furthermore, we
present robust counterparts for practical examples, namely for (discrete)
linear, quadratic and piecewise linear settings. Keywords: Budget Uncertainty,
Discrete Optimization, Combinatorial Optimization,
