Theory of stochastic integer programming with applications

Abstract

In this thesis we shall present the theory of Integer Stochastic Programming. We shall start by giving a short summary on standard Stochastic Linear Programming theory since most of the theory is its continuation. Several properties of the second-stage value function shall be discussed. Most notably the hurdles encountered when integrality is introduced to the second-stage value function. Additionally, Simple Integer Recourse shall be discussed so that it can be used to solve problems with simple recourse. We shall also present an algorithm named Integer L-Shaped Method. Note that this algorithm is a continuation of the Standard L-Shaped method but contains stronger cuts by using the Branch and Cut technique, a technique specifically made for two-staged integer stochastic programs. After these theoretical results, we continue on with the application section of the thesis. The main purpose of this part is to use as much previously discussed theory as possible to solve stochastic mixed or pure integer problems. We are given two problems, the Farmer's Problem and the Kiosk Owner problem. The farmer's problem will be solved by using the Integer L-shaped algorithm while the Kiosk Owner problem shall be solved by using Simple Integer Recourse theory.