TY - JOUR A1 - Dür, Mirjam A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Schabel, Samuel A1 - Schönberger, Christine A1 - Villforth, Klaus T1 - Verfahren zum Einstellen und/oder Optimieren einer einen Gutstoff von einem Schlechtstoff trennenden Sortieranlage und Sortieranlage JF - Deutsches Patent Y1 - 2008 VL - DE 10 2008 013 034 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - Verfahren und Vorrichtung zur automatischen Optimierung von Schulanfangszeiten und des öffentlichen Personenverkehrs und entsprechendes Computerprogramm JF - Deutsche Patentanmeldung Y1 - 2004 VL - DE 10 2004 020 786.0 ER - TY - JOUR A1 - Dür, Mirjam A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Ulbrich, Stefan T1 - Verfahren und Vorrichtung zum Auswuchten von wellenelastischen Rotoren JF - Deutsche Patentanmeldung Y1 - 2006 VL - DE 10 2006 060 583.7 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Göttlich, Simone A1 - Kirchner, Claus A1 - Herty, Michael A1 - Martin, Alexander T1 - Efficient Reformulation and Solution of a Nonlinear PDE-Controlled Flow Network Model JF - Computing Y1 - 2009 VL - 85 IS - 3 SP - 245 EP - 265 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Homfeld, Henning A1 - Huck, Andreas A1 - Martin, Alexander A1 - Yuan, Zhi T1 - Scheduling Locomotives and Car Transfers in Freight Transport JF - Transportation Science Y1 - 2008 VL - 42 IS - 4 SP - 1 EP - 14 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - A Multicriterial Approach for Optimizing Bus Schedules and School Starting Times JF - Annals of Operations Research Y1 - 2006 VL - 147 IS - 1 SP - 199 EP - 216 ER - TY - JOUR A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Fledderus, E. A1 - Geerdes, Hans-Florian A1 - Heideck, B. A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Kürner, T. A1 - Martin, Alexander ED - Martin, Alexander T1 - Mathematical Methods for Automatic Optimization of UMTS Radio Networks Y1 - 2003 UR - http://momentum.zib.de/paper/momentum-d43.pdf IS - D4.3 PB - IST-2000-28088 MOMENTUM ER - TY - JOUR A1 - Eisenblätter, Andreas A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Kürner, T. A1 - Martin, Alexander T1 - Final Report on Automatic Planning and Optimisation Y1 - 2003 UR - http://momentum.zib.de/paper/momentum-d47.pdf IS - D4.7 PB - IST-2000-28088 MOMENTUM ER - TY - GEN A1 - Dittel, Agnes A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - Polyhedral Aspects of Self-Avoiding Walks N2 - In this paper, we study self-avoiding walks of a given length on a graph. We consider a formulation of this problem as a binary linear program. We analyze the polyhedral structure of the underlying polytope and describe valid inequalities. Proofs for their facial properties for certain special cases are given. In a variation of this problem one is interested in optimal configurations, where an energy function measures the benefit if certain path elements are placed on adjacent vertices of the graph. The most prominent application of this problem is the protein folding problem in biochemistry. On a set of selected instances, we demonstrate the computational merits of our approach. T3 - ZIB-Report - 11-11 KW - Polyhedral Combinatorics KW - Integer Programming KW - Self-Avoiding Path KW - Protein Folding Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-12576 ER - TY - THES A1 - Martin, Alexander T1 - Integer Programs with Block Structure N2 - In this thesis we study and solve integer programs with block structure, i.\,e., problems that after the removal of certain rows (or columns) of the constraint matrix decompose into independent subproblems. The matrices associated with each subproblem are called blocks and the rows (columns) to be removed linking constraints (columns). Integer programs with block structure come up in a natural way in many real-world applications. The methods that are widely used to tackle integer programs with block structure are decomposition methods. The idea is to decouple the linking constraints (variables) from the problem and treat them at a superordinate level, often called master problem. The resulting residual subordinate problem then decomposes into independent subproblems that often can be solved more efficiently. Decomposition methods now work alternately on the master and subordinate problem and iteratively exchange information to solve the original problem to optimality. In Part I we follow a different approach. We treat the integer programming problem as a whole and keep the linking constraints in the formulation. We consider the associated polyhedra and investigate the polyhedral consequences of the involved linking constraints. The variety and complexity of the new inequalities that come into play is illustrated on three different types of real-world problems. The applications arise in the design of electronic circuits, in telecommunication and production planning. We develop a branch-and-cut algorithm for each of these problems, and our computational results show the benefits and limits of the polyhedral approach to solve these real-world models with block structure. Part II of the thesis deals with general mixed integer programming problems, that is integer programs with no apparent structure in the constraint matrix. We will discuss in Chapter 5 the main ingredients of an LP based branch-and-bound algorithm for the solution of general integer programs. Chapter 6 then asks the question whether general integer programs decompose into certain block structures and investigate whether it is possible to recognize such a structure. The remaining two chapters exploit information about the block structure of an integer program. In Chapter 7 we parallelize parts of the dual simplex algorithm, the method that is commonly used for the solution of the underlying linear programs within a branch-and-cut algorithm. In Chapter 8 we try to detect small blocks in the constraint matrix and to derive new cutting planes that strengthen the integer programming formulation. These inequalities may be associated with the intersection of several knapsack problems. We will see that they significantly improve the quality of the general integer programming solver introduced in Chapter 5. T3 - ZIB-Report - SC-99-03 KW - integer programming KW - cutting planes KW - block structure Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3911 ER - TY - GEN A1 - Gamrath, Gerald A1 - Gleixner, Ambros A1 - Koch, Thorsten A1 - Miltenberger, Matthias A1 - Kniasew, Dimitri A1 - Schlögel, Dominik A1 - Martin, Alexander A1 - Weninger, Dieter T1 - Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming N2 - SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice. T3 - ZIB-Report - 16-45 KW - supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61107 SN - 1438-0064 ER - TY - CHAP A1 - Schewe, Lars A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Pfetsch, Marc T1 - Mathematical optimization for evaluating gas network capacities T2 - Evaluating Gas Network Capacities Y1 - 2015 SN - 9781611973686 SP - 87 EP - 102 PB - Society for Industrial and Applied Mathematics ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Homfeld, Henning A1 - Martin, Alexander T1 - Leitwegeplanung T2 - Mathematik für Innovationen in Industrie und Dienstleistungen Y1 - 2007 ER - TY - GEN A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Pfetsch, Marc ED - Jünger, Michael ED - Reinelt, Gerhard T1 - Progress in Academic Computational Integer Programming T2 - Facets of Combinatorial Optimization Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38189-8_19 SP - 483 EP - 506 PB - Springer ER - TY - JOUR A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in presolving for mixed integer programming JF - Mathematical Programming Computation N2 - This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 % on affected instances while not degrading the performance on the remaining problems. Y1 - 2015 U6 - https://doi.org/10.1007/s12532-015-0083-5 VL - 7 IS - 4 SP - 367 EP - 398 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - Decomposing Matrices into Blocks N2 - In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs. T3 - ZIB-Report - SC-97-15 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2849 ER -