  In this work we study binary two-stage robust optimization problems with
objective uncertainty. We present an algorithm to calculate efficiently lower
bounds for the binary two-stage robust problem by solving alternately the
underlying deterministic problem and an adversarial problem. For the
deterministic problem any oracle can be used which returns an optimal solution
for every possible scenario. We show that the latter lower bound can be
implemented in a branch & bound procedure, where the branching is performed
only over the first-stage decision variables. All results even hold for
non-linear objective functions which are concave in the uncertain parameters.
As an alternative solution method we apply a column-and-constraint generation
algorithm to the binary two-stage robust problem with objective uncertainty.
  We test both algorithms on benchmark instances of the uncapacitated
single-allocation hub-location problem and of the capital budgeting problem.
Our results show that the branch & bound procedure outperforms the
column-and-constraint generation algorithm.
