Aircraft management and diagram visualization: Exact optimization algorithms

In this thesis, we apply a cutting plane approach to two practical combinatorial optimization problems: an aircraft management problem and a diagram visualization problem. The basic method we follow is to formulate the problem under consideration either explicitly or implicitly as a (mixed-) integer linear program and then to produce a tailored algorithm for solving the problem to proven optimality, incorporating the structure of the problem.;The aircraft management problem we consider involves the planning of maintenance checks and the investment decision of retaining or returning previously leased planes of an airline fleet in order to comply with marketing goals and hangar capacity. This problem deals with the question of how many aircraft an airline will have available for flying passengers over the next few months.;We model the problem as a mixed-integer program. In order to tighten the resulting LP-relaxation, we introduce additional problem-specific cutting planes, which are incorporated within a cutting plane algorithm. We give computational results for three test-sets of problems derived from a real-world problem provided by a major US carrier.;Secondly, we study the multi-layer crossing minimization problem from a polyhedral point of view. This problem asks for the minimum number of edge-crossings in a multi-layered graph. After the introduction of a mixed-integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope.;We use additional cutting planes within a branch-and-bound framework and compare computational results of a branch-and-cut and a cut-and-branch algorithm with computational results of a pure branch-and-bound algorithm for 2- and 3-layer instances.