TY - GEN A1 - Martin, Alexander A1 - Geißler, Björn A1 - Hayn, Christine A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Morsi, Antonio A1 - Pfetsch, Marc A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Optimierung Technischer Kapazitäten in Gasnetzen N2 - Die mittel- und längerfristige Planung für den Gastransport hat sich durch Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert. Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel diskutiert die hieraus resultierenden mathematischen Planungsprobleme, welche als Validierung von Nominierungen und Buchungen, Bestimmung der technischen Kapazität und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze skizziert. T3 - ZIB-Report - 11-56 KW - Gasnetzplanung KW - Technische Kapazitäten KW - Nominierungsvalidierung KW - Buchungsvalidierung KW - Topologieplanung Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15121 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Stable-Set and Other Techniques for Frequency Assignment Problems T2 - Anais da I Oficina Nacional em Problemas de Corte & Empacotamento Y1 - 1996 SP - 17 EP - 21 PB - Universidade de São Paulo, Instituto de Matemática e Estatística ER - TY - GEN A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Gollmer, Ralf A1 - Hayn, Christine A1 - Henrion, Rene A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Mirkov, Radoslava A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Mathematical Optimization for Challenging Network Planning Problems in Unbundled Liberalized Gas Markets N2 - The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor where united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We show that these new paradigms lead to new and challenging mathematical optimization problems. In order to solve them and to provide meaningful results for practice, all aspects of the underlying problems, such as combinatorics, stochasticity, uncertainty, and nonlinearity, have to be addressed. With such special-tailored solvers, free network capacities and topological network extensions can, for instance, be determined. T3 - ZIB-Report - 13-13 KW - Gas Market Liberalization KW - Entry-Exit Model KW - Gas Network Access Regulation KW - Mixed-Integer Nonlinear Nonconvex Stochastic Optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17821 SN - 1438-0064 ER - TY - GEN A1 - Pfetsch, Marc A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Geißler, Nina A1 - Gollmer, Ralf A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Vigerske, Stefan A1 - Willert, Bernhard T1 - Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions N2 - In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously. T3 - ZIB-Report - 12-41 Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16531 SN - 1438-0064 ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - MIPLIB 2003 N2 - This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances. T3 - ZIB-Report - 05-28 KW - Mathematical Programming KW - Mixed Integer Programming KW - IP KW - MIP KW - Optimization KW - Instances Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8625 ER - TY - JOUR A1 - Martin, Alexander A1 - Müller, J. A1 - Pokutta, Sebastian T1 - Strict linear prices in non-convex European day-ahead electricity markets JF - Optimization Methods and Software Y1 - 2014 UR - http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1660528 N1 - Additional Note: 10.1080/10556788.2013.823544 N1 - URL of the PDF: http://dx.doi.org/10.1080/10556788.2013.823544 VL - 29 IS - 1 SP - 189 EP - 221 ER - TY - BOOK A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - Geometric Algorithms and Combinatorial Optimization T3 - Algorithms and Combinatorics Y1 - 1988 SN - 3-540-13624-X, 0-387-13624-X (U.S.) VL - 2 PB - Springer ER - TY - CHAP A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander ED - Pulleyblank, William T1 - Geometric Methods in Combinatorial Optimization T2 - Progress in Combinatorial Optimization, (Conference Waterloo/Ontario 1982) Y1 - 1984 SP - 167 EP - 183 PB - Academic Press ER - TY - CHAP A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander ED - Berge, Claude ED - Chvátal, Vašek T1 - Polynomial algorithms for perfect graphs T2 - Topics on perfect graphs Y1 - 1984 VL - 21 SP - 325 EP - 356 PB - North-Holland ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - Corrigendum to our paper “The ellipsoid method and its consequences in combinatorial optimization” JF - Combinatorica Y1 - 1984 VL - 4 IS - 4 SP - 291 EP - 295 ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - Relaxations of Vertex Packing JF - Journal of Combinatorial Theory, Series B Y1 - 1986 VL - 40 SP - 330 EP - 343 ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - The ellipsoid method and its consequences in combinatorial optimization JF - Combinatorica Y1 - 1981 VL - 1 IS - 2 SP - 169 EP - 197 ER - TY - JOUR A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - The ellipsoid method and its consequences in combinatorial optimization JF - IIASA Collab. Proceedings Ser. CP-81-S1 Y1 - 1981 SP - 511 EP - 546 ER - TY - JOUR A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - MIPLIB 2003 JF - Operations Research Letters Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/862/ U6 - https://doi.org/10.1016/j.orl.2005.07.009 VL - 34 IS - 4 SP - 361 EP - 372 PB - Elsevier / North-Holland ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Achterberg, Tobias A1 - Fügenschuh, Armin A1 - Koster, Arie M.C.A. A1 - Wegel, Oliver A1 - Wessäly, Roland ED - Anandalingam, G. ED - Raghavan, S. T1 - Modelling Feasible Network Configurations for UMTS T2 - Telecommunications Network Design and Management Y1 - 2003 UR - http://opus.kobv.de/zib/volltexte/2002/684/ PB - Kluver ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Martin, Alexander ED - Ahr, Dino ED - Fahrion, Roland ED - Oswald, Marcus ED - Reinelt, Gerhard T1 - Optimisation Methods for UMTS Radio Network Planning T2 - Operation Research Proceedings 2003 Y1 - 2003 U6 - https://doi.org/10.1007/978-3-642-17022-5_5 SP - 31 EP - 38 PB - Springer ER - TY - JOUR A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Branching Rules Revisited JF - Operations Research Letters Y1 - 2005 UR - http://opus.kobv.de/zib/volltexte/2004/789/ U6 - https://doi.org/10.1016/j.orl.2004.04.002 VL - 33 IS - 1 SP - 42 EP - 54 PB - Elsevier / North-Holland ER - TY - JOUR A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Solving Steiner tree problems in graphs to optimality JF - Networks Y1 - 1998 UR - http://opus.kobv.de/zib/volltexte/1996/253/ U6 - https://doi.org/10.1002/(SICI)1097-0037(199810)32:3%3C207::AID-NET5%3E3.0.CO;2-O VL - 32 SP - 207 EP - 232 ER - TY - CHAP A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Voß, Stefan ED - Du, D.-Z. ED - Cheng, X. T1 - SteinLib: An Updated Library on Steiner Tree Problems in Graphs T2 - Steiner Trees in Industry Y1 - 2001 U6 - https://doi.org/10.1007/978-1-4613-0255-1_9 SP - 285 EP - 325 PB - Kluwer ER - TY - JOUR A1 - Fiedler, Georg Martin A1 - Leichtle, Alexander Benedikt A1 - Kase, Julia A1 - Baumann, Sven A1 - Ceglarek, Uta A1 - Felix, Klaus A1 - Conrad, Tim A1 - Witzigmann, Helmut A1 - Weimann, Arved A1 - Schütte, Christof A1 - Hauss, Johann A1 - Büchler, Markus A1 - Thiery, Joachim T1 - Serum Peptidome Profiling Revealed Platelet Factor 4 as a Potential Discriminating Peptide Associated With Pancreatic Cancer JF - Clinical Cancer Research Y1 - 2009 UR - http://publications.imp.fu-berlin.de/155/ U6 - https://doi.org/10.1158/1078-0432.CCR-08-2701 VL - 15 IS - 11 SP - 3812 EP - 3819 PB - American Association for Cancer Research, ER - TY - CHAP A1 - Martin, Alexander A1 - Müller, J. A1 - Pokutta, Sebastian T1 - On clearing coupled day-ahead electricity markets T2 - Proceedings of 23rd Australasian Finance and Banking Conference Y1 - 2010 UR - http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1660528 N1 - Additional Note: doi:10.1080/10556788.2013.823544 ER - TY - CHAP A1 - Helmke, H. A1 - Gluchshenko, O. A1 - Martin, Alexander A1 - Peter, A. A1 - Pokutta, Sebastian A1 - Siebert, U. T1 - Optimal Mixed-Mode Runway Scheduling T2 - Proceedings of DACS Y1 - 2011 UR - http://www.box.net/shared/34p1ea2of7exdgq7tlty ER - TY - GEN A1 - Borndörfer, Ralf A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - Matrix Decomposition by Branch-and-Cut 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 MIPLIB 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. T3 - ZIB-Report - SC-97-14 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2839 ER - TY - GEN A1 - Bixby, Robert E. A1 - Martin, Alexander T1 - Parallelizing the Dual Simplex Method N2 - We study the parallelization of the steepest-edge version of the dual simplex algorithm. Three different parallel implementations are examined, each of which is derived from the CPLEX dual simplex implementation. One alternative uses PVM, one general-purpose System V shared-memory constructs, and one the PowerC extension of C on a Silicon Graphics multi-processor. These versions were tested on different parallel platforms, including heterogeneous workstation clusters, Sun S20-502, Silicon Graphics multi-processors, and an IBM SP2. We report on our computational experience. T3 - ZIB-Report - SC-95-45 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2112 ER - TY - GEN A1 - Dahl, Geir A1 - Martin, Alexander A1 - Stoer, Mechthild T1 - Routing through virtual paths in layered telecommunication networks N2 - We study a network configuration problem in telecommunications where one wants to set up paths in a capacitated network to accommodate given point-to-point traffic demand. The problem is formulated as an integer linear programming model where 0-1 variables represent different paths. An associated integral polytope is studied and different classes of facets are described. These results are used in a cutting plane algorithm. Computational results for some realistic problems are reported. T3 - ZIB-Report - SC-95-41 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2070 ER - TY - GEN A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Solving Steiner Tree Problems in Graphs to Optimality N2 - In this paper we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms and primal heuristics. We are able to solve all problem instances discussed in literature to optimality, including one to our knowledge not yet solved problem. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called {\em SteinLib} that is accessible via World Wide Web. T3 - ZIB-Report - SC-96-42 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2526 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Paths and Steiner Trees: Routing of Electronic Circuits. N2 - One of the challenging problems in the design of electronic circuits is the so-called routing problem. Roughly speaking, the task is to connect so-called terminal sets via wires on a predefined area. In addition, certain design rules are to be taken into account and an objective function such as the wiring length must be minimized. The routing problem in general is too complex to be solved in one step. Depending on the user's choice of decomposing the chip design problem into a hierarchy of stages, on the underlying technology, and on the given design rules, various subproblems arise. We discuss several variants of practically relevant routing problems and give a short overview on the underlying technologies and design rules. Many of the routing problems that come up this way can be formulated as the problem of packing so-called Steiner trees in certain graphs. We consider the Steiner tree packing problem from a polyhedral point of view and present three possibilities to define an appropriate polyhedron. Weighing their pros and cons we decide for one of these polytopes and sketch some of our investigations. T3 - ZIB-Report - SC-93-15 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1113 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Souza, Cid C. de A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem. N2 - We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change. T3 - ZIB-Report - SC-94-16 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1450 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Souza, Cid C. de A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - The Node Capacitated Graph Partitioning Problem: A Computational Study. N2 - In this paper we consider the problem of $k$-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. T3 - ZIB-Report - SC-94-17 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1469 ER - TY - GEN A1 - Weismantel, Robert A1 - Ferreira, Carlos E. A1 - Martin, Alexander T1 - A Cutting Plane Based Algorithm for the Multiple Knapsack Problem. N2 - In this paper we describe a cutting plane based algorithm for the multiple knapsack problem. We use our algorithm to solve some practical problem instances arising in the layout of electronic circuits and in the design of main frame computers, and we report on our computational experience. This includes a discussion and evaluation of separation algorithms, an LP-based primal heuristic and some implementation details. The paper is based on the polyhedral theory for the multiple knapsack polytope developed in our companion paper SC 93-04 and meant to turn this theory into an algorithmic tool for the solution of practical problems. T3 - ZIB-Report - SC-93-07 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1031 ER - TY - GEN A1 - Jünger, Michael A1 - Martin, Alexander A1 - Reinelt, Gerhard A1 - Weismantel, Robert T1 - Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits. N2 - The placement in the layout design of electronic circiuts consists of finding a non- overlapping assignment of rectangular cells to positions on the chip so what wireability is guaranteed and certain technical constraints are met.This problem can be modelled as a quadratic 0/1- program subject to linear constraints. We will present a decomposition approach to the placement problem and give results about $NP$-hardness and the existence of $\varepsilon$-approximative algorithms for the involved optimization problems. A graphtheoretic formulation of these problems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines. {\bf Keywords:} Quadratic 0/1 optimization, Computational Complexity, VLSI-Design. T3 - ZIB-Report - SC-92-10 KW - quadratic 0/1 optimization KW - computational complexity KW - VLSI-Design Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-803 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Facets for the Multiple Knapsack Problem. N2 - In this paper we consider the multiple knapsack problem which is defined as follows: given a set $N$ of items with weights $f_i$, $i \in N$, a set $M$ of knapsacks with capacities $F_k$, $k \in M$, and a profit function $c_{ik}, i \in N, k \in M$; find an assignment of a subset of the set of items to the set of knapsacks that yields maximum profit (or minimum cost). With every instance of this problem we associate a polyhedron whose vertices are in one to one correspondence to the feasible solutions of the instance. This polytope is the subject of our investigations. In particular, we present several new classes of inequalities and work out necessary and sufficient conditions under which the corresponding inequality defines a facet. Some of these conditions involve only properties of certain knapsack constraints, and hence, apply to the generalized assignment polytope as well. The results presented here serve as the theoretical basis for solving practical problems. The algorithmic side of our study, i.e., separation algorithms, implementation details and computational experience with a branch and cut algorithm are discussed in the companion paper SC 93-07. T3 - ZIB-Report - SC-93-04 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1007 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Conjunctive Cuts for Integer Programs N2 - This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view. T3 - ZIB-Report - SC-98-18 KW - Polyhedral Combinatorics KW - Integer Programming KW - Separation Algorithm Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3618 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Contributions to General Mixed Integer Knapsack Problems N2 - This paper deals with a general mixed integer knapsack polyhedron for which we introduce and analyze a new family of inequalities. We discuss the value of this family both from a theoretic and a computational point of view. T3 - ZIB-Report - SC-97-38 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3075 ER - TY - JOUR 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 JF - Journal of Computational Mathematics N2 - The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of robust and future-proof decision support systems. The complexity of industrial-scale supply chain optimization, however, often poses limits to the application of general mixed-integer programming solvers. In this paper we describe algorithmic innovations that help to ensure that MIP solver performance matches the complexity of the large supply chain problems and tight time limits encountered in practice. Our computational evaluation is based on a diverse set, modeling real-world scenarios supplied by our industry partner SAP. Y1 - 2019 U6 - https://doi.org/10.4208/jcm.1905-m2019-0055 VL - 37 SP - 866 EP - 888 ER - TY - GEN A1 - Gamrath, Gerald A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Miltenberger, Matthias A1 - Weninger, Dieter T1 - Progress in Presolving for Mixed Integer Programming N2 - Presolving attempts to eliminate redundant information from the problem formulation and simultaneously tries to strengthen the formulation. It can be very effective and is often essential for solving instances. Especially for mixed integer programming problems, fast and effective presolving algorithms are very important. In this paper, we report on three new presolving techniques. The first method searches for singleton continuous columns and tries to fix the corresponding variables. Then we present a presolving technique which exploits a partial order of the variables to induce fixings. Finally, we show an approach based on connected components in graphs. Our computational results confirm the profitable use of the algorithms in practice. T3 - ZIB-Report - 13-48 KW - mixed-integer programming KW - presolving KW - preprocessing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42530 SN - 1438-0064 ER - TY - GEN A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Voß, Stefan T1 - SteinLib: An Updated Library on Steiner Tree Problems in Graphs N2 - In this paper we present the {\em SteinLib}, a library of data sets for the Steiner tree problem in graphs. This library extends former libraries on Steiner tree problems by many new interesting and difficult instances, most of them arising from real-world applications. We give a survey on the difficulty of these problem instances by giving references to state-of-the-art software packages that were the first or are currently among the best to solve these instances. T3 - ZIB-Report - 00-37 KW - Steiner Trees KW - Mathematical Programming Testdata Library Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6056 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Koch, Thorsten A1 - Koster, Arie M.C.A. A1 - Martin, Alexander A1 - Pfender, Tobias A1 - Wegel, Oliver A1 - Wessäly, Roland T1 - Modelling Feasible Network Configurations for UMTS N2 - A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations. T3 - ZIB-Report - 02-16 KW - UMTS KW - radio interface KW - network planning KW - configuration KW - perfect power control KW - mathematical model KW - mixed integer programming KW - MOMENTUM KW - IST-20 Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6837 ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Branching on History Information N2 - Mixed integer programs ($MIPs$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in $SIP$, a state-of-the-art $MIP$ solver. We give computational results that show the superiority of the new strategy. T3 - ZIB-Report - 02-32 KW - Mixed Integer Programming KW - Branch-and-Bound KW - Branching Rules KW - Pseudocost Branching Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6990 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Optimization Methods for UMTS Radio Network Planning N2 - The UMTS radio network planning problem poses the challenge of designing a cost-effective network that provides users with sufficient coverage and capacity. We describe an optimization model for this problem that is based on comprehensive planning data of the EU project MOMENTUM. We present heuristic mathematical methods for this realistic model, including computational results. T3 - ZIB-Report - 03-41 Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7637 ER - TY - THES A1 - Martin, Alexander T1 - Packen von Steinerbäumen: Polyedrische Studien und Anwendung. N2 - Gegeben sei ein Graph $G=(V,E)$ mit positiven Kantenkapazitäten $c_e$ und Knotenmengen $T_1,\ldots,T_N$. Das Steinerbaumpackungs-Problem besteht darin, Kantenmengen $S_1,\ldots,S_N$ zu finden, so da\ss\ jedes $S_k$ die Knoten aus $T_k$ verbindet und jede Kante $e$ in höchstens $c_e$ Kantenmengen aus $S_1,\ldots,S_N$ vorkommt. Eine zulässige Lösung dieses Problems nennen wir eine Steinerbaumpackung. Ist zusätzlich eine Gewichtung der Kanten gegeben und nach einer bezüglich dieser Gewichtung minimalen Steinerbaumpackung gesucht, so sprechen wir vom gewichteten Steinerbaumpackungs-Problem. Die Motivation zum Studium dieses Problems kommt aus dem Entwurf elektronischer Schaltungen. Ein dort auftretendes Teilproblem ist das sogenannte Verdrahtungsproblem, das im wesentlichen darin besteht, gegebene Punktmengen unter bestimmten Nebenbedingungen und Optimalitätskriterien auf einer Grundfläche zu verbinden. Wir studieren das Steinerbaumpackungs-Problem aus polyedrischer Sicht und definieren ein Polyeder, dessen Ecken genau den Steinerbaumpackungen entsprechen. Anschlie\ss end versuchen wir, dieses Polyeder durch gute'' beziehungsweise facetten-definierenden Ungleichungen zu beschreiben. Basierend auf diesen Ungleichungen entwickeln wir ein Schnittebenenverfahren. Die Lösung des Schnittebenenverfahrens liefert eine untere Schranke für die Optimallösung und dient als Grundlage für die Entwicklung guter Primalheuristiken. Wir haben das von uns implementierte Schnittebenenverfahren an einem Spezialfall des Verdrahtungsproblems, dem sogenannten Switchbox-Verdrahtungsproblem, getestet und vielversprechende Ergebnisse erzielt. T3 - ZIB-Report - TR-92-04 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4894 ER - TY - GEN A1 - Marchand, Hugues A1 - Martin, Alexander A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - Cutting Planes in Integer and Mixed Integer Programming N2 - This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored. T3 - ZIB-Report - SC-99-44 KW - Mixed Integer Programming KW - Cutting Planes Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4339 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Intersection of Knapsack Polyhedra and Extensions N2 - This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported. T3 - ZIB-Report - SC-97-61 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3300 ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Branching rules revisited N2 - Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost branching} strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed newstrategy. T3 - ZIB-Report - 04-13 KW - Mixed-integer-programming KW - Branch-and-Bound KW - Variable selection KW - Pseudocost-Branching KW - Strong-Branching KW - Reliability-Branching Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7886 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Geerdes, Hans-Florian A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Wessäly, Roland T1 - UMTS Radio Network Evaluation and Optimization beyond Snapshots N2 - This paper is concerned with UMTS radio network design. Our task is to reconfigure antennas and the related cells as to improve network quality. In contrast to second generation GSM networks, \emph{interference} plays a paramount role when designing third generation radio networks. A known compact formulation for assessing the interference characteristics of a radio network as coupling relations between cells based on user snapshots is generalized to statistical average load. This enables us to overcome the notorious difficulties of snapshot-based network optimization approaches. We recall a mixed-integer programming model for the network design problem that is based on user snapshots and contrast it with a new network design model based on the average coupling formulation. Exemplarily focusing on the important problem of optimizing antenna tilts, we give computational results for a fast local search algorithm and the application of a MIP solver to both models. These results demonstrate that our new average-based approaches outperform state-of-the-art snapshot models for UMTS radio network optimization. T3 - ZIB-Report - 04-15 KW - UMTS KW - Network planning KW - Network design KW - Optimization Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7903 ER - TY - JOUR A1 - Conrad, Tim A1 - Leichtle, Alexander Benedikt A1 - Ceglarek, Uta A1 - Weinert, P. A1 - Nakas, C.T. A1 - Nuoffer, Jean-Marc A1 - Kase, Julia A1 - Witzigmann, Helmut A1 - Thiery, Joachim A1 - Fiedler, Georg Martin T1 - Pancreatic carcinoma, pancreatitis, and healthy controls - metabolite models in a three-class diagnostic dilemma JF - Metabolomics N2 - Background: Metabolomics as one of the most rapidly growing technologies in the ?-omics?field denotes the comprehensive analysis of low molecular-weight compounds and their pathways. Cancer-specific alterations of the metabolome can be detected by high-throughput massspectrometric metabolite profiling and serve as a considerable source of new markers for the early differentiation of malignant diseases as well as their distinction from benign states. However, a comprehensive framework for the statistical evaluation of marker panels in a multi-class setting has not yet been established. Methods: We collected serum samples of 40 pancreatic carcinoma patients, 40 controls, and 23 pancreatitis patients according to standard protocols and generated amino acid profiles by routine mass-spectrometry. In an intrinsic three-class bioinformatic approach we compared these profiles, evaluated their selectivity and computed multi-marker panels combined with the conventional tumor marker CA 19-9. Additionally, we tested for non-inferiority and superiority to determine the diagnostic surplus value of our multi-metabolite marker panels.  Results: Compared to CA 19-9 alone, the combined amino acid-based metabolite panel had a superior selectivity for the discrimination of healthy controls, pancreatitis, and pancreatic carcinoma patients [Volume under ROC surface (VUS) = 0.891 (95\% CI 0.794 - 0.968)]. Conclusions: We combined highly standardized samples, a three-class study design, a highthroughput mass-spectrometric technique, and a comprehensive bioinformatic framework to identify metabolite panels selective for all three groups in a single approach. Our results suggest that metabolomic profiling necessitates appropriate evaluation strategies and ?despite all its current limitations? can deliver marker panels with high selectivity even in multi-class settings. Y1 - 2013 U6 - https://doi.org/10.1007/s11306-012-0476-7 VL - 9 IS - 3 SP - 677 EP - 687 ER - TY - JOUR A1 - Conrad, Tim A1 - Leichtle, Alexander Benedikt A1 - Nuoffer, Jean-Marc A1 - Ceglarek, Uta A1 - Kase, Julia A1 - Witzigmann, Helmut A1 - Thiery, Joachim A1 - Fiedler, Georg Martin T1 - Serum amino acid profiles and their alterations in colorectal cancer JF - Metabolomics N2 - Mass spectrometry-based serum metabolic profiling is a promising tool to analyse complex cancer associated metabolic alterations, which may broaden our pathophysiological understanding of the disease and may function as a source of new cancer-associated biomarkers. Highly standardized serum samples of patients suffering from colon cancer (n = 59) and controls (n = 58) were collected at the University Hospital Leipzig. We based our investigations on amino acid screening profiles using electrospray tandem-mass spectrometry. Metabolic profiles were evaluated using the Analyst 1.4.2 software. General, comparative and equivalence statistics were performed by R 2.12.2. 11 out of 26 serum amino acid concentrations were significantly different between colorectal cancer patients and healthy controls. We found a model including CEA, glycine, and tyrosine as best discriminating and superior to CEA alone with an AUROC of 0.878 (95\% CI 0.815?0.941). Our serum metabolic profiling in colon cancer revealed multiple significant disease-associated alterations in the amino acid profile with promising diagnostic power. Further large-scale studies are necessary to elucidate the potential of our model also to discriminate between cancer and potential differential diagnoses. In conclusion, serum glycine and tyrosine in combination with CEA are superior to CEA for the discrimination between colorectal cancer patients and controls. Y1 - 2012 U6 - https://doi.org/10.1007/s11306-011-0357-5 ER - TY - JOUR A1 - Conrad, Tim A1 - Genzel, Martin A1 - Cvetkovic, Nada A1 - Wulkow, Niklas A1 - Leichtle, Alexander Benedikt A1 - Vybiral, Jan A1 - Kytyniok, Gitta A1 - Schütte, Christof T1 - Sparse Proteomics Analysis – a compressed sensing-based approach for feature selection and classification of high-dimensional proteomics mass spectrometry data JF - BMC Bioinfomatics N2 - Background: High-throughput proteomics techniques, such as mass spectrometry (MS)-based approaches, produce very high-dimensional data-sets. In a clinical setting one is often interested in how mass spectra differ between patients of different classes, for example spectra from healthy patients vs. spectra from patients having a particular disease. Machine learning algorithms are needed to (a) identify these discriminating features and (b) classify unknown spectra based on this feature set. Since the acquired data is usually noisy, the algorithms should be robust against noise and outliers, while the identified feature set should be as small as possible. Results: We present a new algorithm, Sparse Proteomics Analysis (SPA),based on thet heory of compressed sensing that allows us to identify a minimal discriminating set of features from mass spectrometry data-sets. We show (1) how our method performs on artificial and real-world data-sets, (2) that its performance is competitive with standard (and widely used) algorithms for analyzing proteomics data, and (3) that it is robust against random and systematic noise. We further demonstrate the applicability of our algorithm to two previously published clinical data-sets. Y1 - 2017 U6 - https://doi.org/10.1186/s12859-017-1565-4 VL - 18 IS - 160 ER - TY - JOUR A1 - Wilson, David A1 - Anglin, Carolyn A1 - Ambellan, Felix A1 - Grewe, Carl Martin A1 - Tack, Alexander A1 - Lamecker, Hans A1 - Dunbar, Michael A1 - Zachow, Stefan T1 - Validation of three-dimensional models of the distal femur created from surgical navigation point cloud data for intraoperative and postoperative analysis of total knee arthroplasty JF - International Journal of Computer Assisted Radiology and Surgery N2 - Purpose: Despite the success of total knee arthroplasty there continues to be a significant proportion of patients who are dissatisfied. One explanation may be a shape mismatch between pre and post-operative distal femurs. The purpose of this study was to investigate a method to match a statistical shape model (SSM) to intra-operatively acquired point cloud data from a surgical navigation system, and to validate it against the pre-operative magnetic resonance imaging (MRI) data from the same patients. Methods: A total of 10 patients who underwent navigated total knee arthroplasty also had an MRI scan less than 2 months pre-operatively. The standard surgical protocol was followed which included partial digitization of the distal femur. Two different methods were employed to fit the SSM to the digitized point cloud data, based on (1) Iterative Closest Points (ICP) and (2) Gaussian Mixture Models (GMM). The available MRI data were manually segmented and the reconstructed three-dimensional surfaces used as ground truth against which the statistical shape model fit was compared. Results: For both approaches, the difference between the statistical shape model-generated femur and the surface generated from MRI segmentation averaged less than 1.7 mm, with maximum errors occurring in less clinically important areas. Conclusion: The results demonstrated good correspondence with the distal femoral morphology even in cases of sparse data sets. Application of this technique will allow for measurement of mismatch between pre and post-operative femurs retrospectively on any case done using the surgical navigation system and could be integrated into the surgical navigation unit to provide real-time feedback. Y1 - 2017 UR - https://link.springer.com/content/pdf/10.1007%2Fs11548-017-1630-5.pdf U6 - https://doi.org/10.1007/s11548-017-1630-5 VL - 12 IS - 12 SP - 2097 EP - 2105 PB - Springer ER - TY - CHAP A1 - Weinhold, Carsten A1 - Lackorzynski, Adam A1 - Bierbaum, Jan A1 - Küttler, Martin A1 - Planeta, Maksym A1 - Härtig, Hermann A1 - Shiloh, Amnon A1 - Levy, Ely A1 - Ben-Nun, Tal A1 - Barak, Amnon A1 - Steinke, Thomas A1 - Schütt, Thorsten A1 - Fajerski, Jan A1 - Reinefeld, Alexander A1 - Lieber, Matthias A1 - Nagel, Wolfgang T1 - FFMK: A Fast and Fault-tolerant Microkernel-based System for Exascale Computing T2 - SPPEXA Symposium 2016 Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-40528-5_18 ER - TY - JOUR A1 - Heida, Martin A1 - Sikorski, Alexander A1 - Weber, Marcus T1 - Consistency and order 1 convergence of cell-centered finite volume discretizations of degenerate elliptic problems in any space dimension JF - SIAM Journal on Numerical Analysis N2 - We study consistency of cell-centered finite difference methods for elliptic equations with degenerate coefficients in any space dimension $d \geq 2$. This results in order of convergence estimates in the natural weighted energy norm and in the weighted discrete $L^2$-norm on admissible meshes. The cells of meshes under consideration may be very irregular in size. We particularly allow the size of certain cells to remain bounded from below even in the asymptotic limit. For uniform meshes we show that the order of convergence is at least 1 in the energy semi-norm, provided the discrete and continuous solutions exist and the continuous solution has $H^2$ regularity. Y1 - 2022 U6 - https://doi.org/10.20347/WIAS.PREPRINT.2913 ER - TY - JOUR A1 - Sikorski, Alexander A1 - Heida, Martin T1 - Voronoi Graph - Improved raycasting and integration schemes for high dimensional Voronoi diagrams N2 - The computation of Voronoi Diagrams, or their dual Delauney triangulations is difficult in high dimensions. In a recent publication Polianskii and Pokorny propose an iterative randomized algorithm facilitating the approximation of Voronoi tesselations in high dimensions. In this paper, we provide an improved vertex search method that is not only exact but even faster than the bisection method that was previously recommended. Building on this we also provide a depth-first graph-traversal algorithm which allows us to compute the entire Voronoi diagram. This enables us to compare the outcomes with those of classical algorithms like qHull, which we either match or marginally beat in terms of computation time. We furthermore show how the raycasting algorithm naturally lends to a Monte Carlo approximation for the volume and boundary integrals of the Voronoi cells, both of which are of importance for finite Volume methods. We compare the Monte-Carlo methods to the exact polygonal integration, as well as a hybrid approximation scheme. Y1 - 2024 ER - TY - JOUR A1 - Xie, Kunpeng A1 - Gruber, Lennart Johannes A1 - Crampen, Martin A1 - Li, Yao A1 - Ferreira, André A1 - Tappeiner, Elias A1 - Gillot, Maxime A1 - Schepers, Jan A1 - Xu, Jiangchang A1 - Pankert, Tobias A1 - Beyer, Michel A1 - Shahamiri, Negar A1 - ten Brink, Reinier A1 - Dot, Gauthier A1 - Weschke, Charlotte A1 - van Nistelrooij, Niels A1 - Verhelst, Pieter-Jan A1 - Guo, Yan A1 - Xu, Zhibin A1 - Bienzeisler, Jonas A1 - Rashad, Ashkan A1 - Flügge, Tabea A1 - Cotton, Ross A1 - Vinayahalingam, Shankeeth A1 - Ilesan, Robert A1 - Raith, Stefan A1 - Madsen, Dennis A1 - Seibold, Constantin A1 - Xi, Tong A1 - Bergé, Stefaan A1 - Nebelung, Sven A1 - Kodym, Oldřich A1 - Sundqvist, Osku A1 - Thieringer, Florian A1 - Lamecker, Hans A1 - Coppens, Antoine A1 - Potrusil, Thomas A1 - Kraeima, Joep A1 - Witjes, Max A1 - Wu, Guomin A1 - Chen, Xiaojun A1 - Lambrechts, Adriaan A1 - Cevidanes, Lucia H Soares A1 - Zachow, Stefan A1 - Hermans, Alexander A1 - Truhn, Daniel A1 - Alves, Victor A1 - Egger, Jan A1 - Röhrig, Rainer A1 - Hölzle, Frank A1 - Puladi, Behrus T1 - Beyond Benchmarks: Towards Robust Artificial Intelligence Bone Segmentation in Socio-Technical Systems JF - Expert Systems With Applications N2 - Despite the advances in automated medical image segmentation, AI models still underperform in various clinical settings, challenging real-world integration. In this multicenter evaluation, we analyzed 20 state-of-the-art mandibular segmentation models across 19,218 segmentations of 1,000 clinically resampled CT/CBCT scans. We show that segmentation accuracy varies by up to 25% depending on socio-technical factors such as voxel size, bone orientation, and patient conditions such as osteosynthesis or pathology. Higher sharpness, isotropic smaller voxels, and neutral orientation significantly improved results, while metallic osteosynthesis and anatomical complexity led to significant degradation. Our findings challenge the common view of AI models as “plug-and-play” tools and suggest evidence-based optimization recommendations for both clinicians and developers. This will in turn boost the integration of AI segmentation tools in routine healthcare. Y1 - 2025 UR - https://www.medrxiv.org/content/10.1101/2025.06.11.25329022v1 U6 - https://doi.org/10.1016/j.eswa.2025.130031 VL - 299 IS - Part D ER - TY - JOUR A1 - Bärmann, Andreas A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Schneider, Oskar T1 - An Online-Learning Approach to Inverse Optimization Y1 - 2018 ER - TY - JOUR A1 - Eisenblätter, Andreas A1 - Geerdes, Hans-Florian A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Wessäly, Roland T1 - UMTS Radio Network Evaluation and Optimization beyond Snapshots JF - Mathematical Methods of Operations Research Y1 - 2005 UR - http://opus.kobv.de/zib/volltexte/2004/791/ U6 - https://doi.org/10.1007/s00186-005-0002-z VL - 63 IS - 1 SP - 1 EP - 29 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Hess, Wolfgang A1 - Martin, Alexander A1 - Ulbrich, Stefan ED - Groche, P. T1 - Diskrete und kontinuierliche Modelle zur Topologie- und Geometrie-Optimierung von Blechprofilen T2 - Sonderforschungsbereich 666 Y1 - 2007 SP - 37 EP - 47 ER - TY - BOOK A1 - Grötschel, Martin A1 - Lovász, Lászlo A1 - Schrijver, Alexander T1 - Geometric Algorithms and Combinatorial Optimization T3 - Algorithms and Combinatorics Y1 - 1993 SN - 3-540-56740-2, 0-387-56740-2 (U.S.) VL - 2 PB - Springer ET - Second corrected edition ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Koch, Thorsten A1 - Koster, Arie M.C.A. A1 - Martin, Alexander A1 - Pfender, Tobias A1 - Wegel, Oliver A1 - Wessäly, Roland ED - G. Anandalingam, S. T1 - Mathematical Model of Feasible Network Configurations for UMTS T2 - Telecommunications network design and management Y1 - 2002 SP - 1 EP - 24 PB - Kluwer ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Stöveken, Peter ED - Bixby, Robert E. ED - Simchi-Levi, D. ED - Martin, Alexander ED - Zimmermann, U. T1 - Integrated Optimization of School Starting Times and Public Bus Services T2 - Mathematics in the Supply Chain Y1 - 2004 ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Integer Programming Methods for UMTS Radio Network Planning T2 - Proceedings of the WiOpt’04, Cambridge, UK Y1 - 2004 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander ED - Aardal, Karen I. ED - Nemhauser, George ED - Weismantel, R. T1 - Computational Integer Programming and Cutting Planes T2 - Handbooks in Operations Research and Management Science, Vol. 12 Y1 - 2005 SP - 69 EP - 122 PB - North-Holland ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Homfeld, Henning A1 - Huck, Andreas A1 - Martin, Alexander ED - Jacob, R. ED - Müller-Hannemann, Matthias T1 - Locomotive and Wagon Scheduling in Freight Transport T2 - Proceedings of the ATMOS06 Y1 - 2006 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Mehlert, Christian A1 - Stöveken, Peter ED - Günther, H.-O. ED - Mattfeld, D. ED - Suhl, L. T1 - Ein Planungstool zur Schulzeitstaffelung T2 - Supply Chain Management und Logistik Y1 - 2005 SP - 419 EP - 436 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Stöveken, Peter ED - Fleuren, Hein ED - den Hertog, Dick ED - Kort, Peter T1 - Integrated Optimization of School Starting Times and Public Bus Services T2 - Operations Research Proceedings Y1 - 2005 SP - 150 EP - 157 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - Mixed-integer models for topology optimization in sheet metal design T2 - Sixth International Congress on Industrial Applied Mathematics (ICIAM07) and GAMM Annual Meeting, Zürich 2007 Y1 - 2007 SP - 2060049 EP - 2060050 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - ler, Björn A1 - Martin, Alexander A1 - Morsi, Antonio ED - Barnhart, Cynthia ED - Clausen, Uwe ED - Lauther, Ulrich ED - Möhring, Rolf T1 - The Transport PDE and Mixed-Integer Linear Programming T2 - Dagstuhl Seminar Proceedings 09261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Deutschland Y1 - 2009 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Hess, Wolfgang A1 - Schewe, Lars A1 - Martin, Alexander A1 - Ulbrich, Stefan ED - Groche, P. T1 - Verfeinerte Modelle zur Topologie- und Geometrie-Optimierung von Blechprofilen mit Kammern T2 - Sonderforschungsbereich 666 Y1 - 2008 SP - 17 EP - 28 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Karbstein, Marika A1 - Koch, Thorsten A1 - Martin, Alexander ED - Jünger, Michael ED - Reinelt, Gerhard T1 - How many Steiner terminals can you connect in 20 years? T2 - Facets of Combinatorial Optimization; Festschrift for Martin Grötschel Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38189-8_10 SP - 215 EP - 244 PB - Springer ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Ferreira, Carlos A1 - Martin, Alexander T1 - Decomposing Matrices into Blocks JF - SIAM J. Optim. Y1 - 1998 UR - http://opus.kobv.de/zib/volltexte/1997/285/ VL - 9 IS - 1 SP - 236 EP - 269 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Karbstein, Marika A1 - Koch, Thorsten A1 - Martin, Alexander T1 - How Many Steiner Terminals Can You Connect in 20 Years? N2 - Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem. T3 - ZIB-Report - 13-57 KW - Steiner tree KW - Steiner connectivity KW - Steiner tree packing Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42524 SN - 1438-0064 ER - TY - JOUR A1 - Dür, Mirjam A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Schabel, Samuel A1 - Schönberger, Christine A1 - Villforth, Klaus T1 - Steuerung einer Sortieranlage, z.B. für Altpapier JF - Europäische Patentanmeldung Y1 - 2010 VL - EP 09 718 564.9 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Herty, Michael A1 - Klar, Axel A1 - Martin, Alexander T1 - Combinatorial and Continuous Models and Optimization for Traffic Flow on Networks JF - SIAM Journal on Optimization Y1 - 2006 VL - 16 IS - 4 SP - 1155 EP - 1176 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Martin, Alexander T1 - Welche Gemeinsamkeiten haben Jugendliche und Groß banken? JF - mathematiklehren Y1 - 2006 VL - 129 SP - 50 EP - 54 ER - 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 -