Jesco,

I do not really know why your approach using Piecewise is not working. But you could try with interpolated functions instead:

alpha = Quiet@FunctionInterpolation[\[Alpha][w], {w0}, InterpolationOrder -> 0];
beta = FunctionInterpolation[\[Beta][w, x], {w, 0, 500}, {x, 0, 500}, InterpolationOrder -> 0];
gamma = FunctionInterpolation[\[Gamma][w, x, y], {w, 0, 500}, {x, 0, 500}, {y, 0, 500}, InterpolationOrder -> 0];

And then:

NMinimize[{w + x + y + z, 
  w + alpha[w] x + beta[w, x] y + gamma[w, x, y] z >= 1/3 && 
   w \[Element] PositiveIntegers && x \[Element] PositiveIntegers && 
   y \[Elet] PositiveIntegers && 
   z \[Element] PositiveIntegers}, {w, x, y, z}]

(*   Out:    {4.`,{w\[Rule]1,x\[Rule]1,y\[Rule]1,z\[Rule]1}}   *)

Given your definitions this result is not really surprising - well, at least it seems to be correct.

Does that help? Regards -- Henrik