Solving Hierarchical Stochastic Programs: Application to the Maritime Fleet Renewal Problem

This paper presents a solution scheme for a class of multistage stochastic programs (possibly mixed-integer at all stages) in which a hierarchy of decisions emerges. A special structure, common to many strategic problems affected by uncertainty, allows decomposing the problem into a master problem and many independent linear programming subproblems, facilitating the isolation and reduction of the complicating mixed-integer component of the problem. Specialized (possibly heuristic) procedures can be used for solving the master problem while subproblems can be efficiently solved to optimality. We adapt and test the decomposition scheme for a case of the maritime fleet renewal problem, whose real life instances cannot be solved by means of commercial off-the-shelf solvers.