Problem-based scenario generation in stochastic programming with binary distributions - Case study in Air Traffic Flow Management

Scenario generation is about selecting which outcomes of the future are worth considering when solving a stochastic optimization problem, and to remove redundancies in the full representation of the stochastic phenomenon to be able to solve a decision problem. This thesis finds that analysing a collection of output-distributions resulting from a restricted and relevant set of first-stage decisions is sufficient to find the problem structure which makes the formulation unstable and that these can be compensated against by constructing appropriate scenario sets based on empirically analysing such a collection of output-distributions. These insights are applied to make a new scenario generation method for the particular case of binary distributions. This problem type is exceptionally well suited for problem-based scenario generation due to the high impact of changes in the stochastic variables, and the lack of alternative scenario generation methods for such problems makes this a valuable contribution. Three different clustering methods suited for binary domains are suggested and compared to guide how to choose one based on the specific problem. The motivation for developing better scenario generation procedures is to solve large-scale, often combinatorial, stochastic models which otherwise cannot be solved. The proposed scenario generation method is therefore applied to a large-scale, combinatorial two-stage model in Air Traffic Flow Management specified by a binary distribution function. The model integrates strategic decision making across entire air traffic networks and integration between the strategic and tactical planning stages. It was shown that the suggested scenario generation procedure gave better and more reliable solutions than all other alternatives considered. Thus, the proposed scenario generation procedure creates a more accurate and reliable representation of the output-distribution to solve the given problem