Using Fourier-Motzkin-Elimination to Derive Capacity Models of Container Vessels

Due to its high computational complexity, Fourier-Motzkin-Elimination (FME) is mainly known as a theoretical approach to determine feasibility of a linear program (LP). Current applications of FME in static program analysis and logic programming is based on the fact that it is a transformation corresponding to existential quantification in logic. Large-scale variable elimination, however, has to our knowledge not been attempted so far. In this report, we introduce a novel FME-based framework for massive variable elimination that takes advantage of the block structure found in many LP problems. Our objective is to simplify the LP by eliminating most of its variables. We show that this is possible for the key challenge in liner shipping of defining the capacity of container vessels as a function of the mixture of cargo they carry.