Algorithms for Stochastic Integer Programs Using Fenchel Cutting Planes

Abstract

This dissertation develops theory and methodology based on Fenchel cutting planes for solving stochastic integer programs (SIPs) with binary or general integer variables in the second-stage. The methodology is applied to auto-carrier loading problem under uncertainty. The motivation is that many applications can be modeled as SIPs, but this class of problems is hard to solve. In this dissertation, the underlying parameter distributions are assumed to be discrete so that the original problem can be formulated as a deterministic equivalent mixed-integer program. The developed methods are evaluated based on computational experiments using both real and randomly generated instances from the literature. We begin with studying a methodology using Fenchel cutting planes for SIPs with binary variables and implement an algorithm to improve runtime performance.

We then introduce the stochastic auto-carrier loading problem where we present a mathematical model for tactical decision making regarding the number and types of auto-carriers needed based on the uncertainty of availability of vehicles. This involves the auto-carrier loading problem for which actual dimensions of the vehicles, regulations on total height of the auto-carriers and maximum weight of the axles, and safety requirements are considered. The problem is modeled as a two-stage SIP, and computational experiments are performed using test instances based on real data. Next, we develop theory and a methodology for Fenchel cutting planes for mixed integer programs with special structure. Integer programs have to be solved to generate a Fenchel cutting plane and this poses a challenge. Therefore, we propose a new methodology for constructing a reduced set of integer points so that the generation of Fenchel cutting planes is computationally favorable. We then present the computational results based on randomly generated instances from the literature and discuss the limitations of the methodology. We finally extend the methodology to SIPs with general integer variables in the second-stage with special structure, and study different normalizations for Fenchel cut generation and report their computational performance.