TY - THES A1 - Borndörfer, Ralf T1 - Mathematical Optimization and Public Transportation N2 - This cumulative thesis collects the following six papers for obtaining the habilitation at the Technische Universität Berlin, Fakultät II – Mathematik und Naturwissenschaften: (1) Set packing relaxations of some integer programs. (2) Combinatorial packing problems. (3) Decomposing matrices into blocks. (4) A bundle method for integrated multi-depot vehicle and duty scheduling in public transit. (5) Models for railway track allocation. (6) A column-generation approach to line planning in public transport. Some changes were made to the papers compared to the published versions. These pertain to layout unifications, i.e., common numbering, figure, table, and chapter head layout. There were no changes with respect to notation or symbols, but some typos have been eliminated, references updated, and some links and an index was added. The mathematical content is identical. The papers are about the optimization of public transportation systems, i.e., bus networks, railways, and airlines, and its mathematical foundations, i.e., the theory of packing problems. The papers discuss mathematical models, theoretical analyses, algorithmic approaches, and computational aspects of and to problems in this area. Papers 1, 2, and 3 are theoretical. They aim at establishing a theory of packing problems as a general framework that can be used to study traffic optimization problems. Indeed, traffic optimization problems can often be modelled as path packing, partitioning, or covering problems, which lead directly to set packing, partitioning, and covering models. Such models are used in papers 4, 5, and 6 to study a variety of problems concerning the planning of line systems, buses, trains, and crews. The common aim is always to exploit as many degrees of freedom as possible, both at the level of the individual problems by using large-scale integer programming techniques, as well as on a higher level by integrating hitherto separate steps in the planning process. KW - set packing KW - set partitioning KW - set covering KW - polyhedral combinatorics KW - public transport KW - railways Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13613 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering N2 - We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib. T3 - ZIB-Report - 09-40 KW - MINLP KW - MIQCP KW - Primalheuristik KW - Nachbarschaftssuche KW - Mengenüberdeckung KW - mixed-integer nonlinear programming KW - MIQCP KW - primal heuristic KW - large neighborhood search KW - set covering Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11632 SN - 1438-0064 ER -