We consider a class of min-max robust problems in which the functions that need to be robustified can be decomposed as the sum of arbitrary functions. This class of problems includes many practical problems such as the lot-sizing problem under demand uncertainty. By considering a Lagrangian relaxation of the uncertainty set we derive a tractable approximation that we relate with the classical dualization approach introduced by Bertsimas and Sim (2004) and also with the exact min-max approach. Moreover we show that the dual Lagrangian approach coincides with the affine approximation of the uncertainty set.

The dual Lagrangian approach is applied to a lot-sizing problem, which motivated our work, where demands are assumed to be uncertain and to belong to the uncertainty set with a budget constraint for each time period introduced by Bertsimas and Sim (2003, 2004). This approach is also related to two classical robust approaches for this problem, the exact min-max approach introduced by Bienstock and Özbay (2008) and the dualization approach from Bertsimas and Thiele (2006).

Using the insights provided by the interpretation of the Lagrangian multipliers in the proposed dual model as penalties, two heuristic strategies, a new Guided Iterated Local Search heuristic and a Subgradient Optimization method, are designed to solve more complex lot-sizing problems where additional practical aspects, such as setup costs, are considered. Computational results show the efficiency of the proposed heuristics which provide a good compromise between the quality of the robust solutions and the running time.