@article{MartinMuellerPokutta2014, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {Strict linear prices in non-convex European day-ahead electricity markets}, volume = {29}, journal = {Optimization Methods and Software}, number = {1}, pages = {189 -- 221}, year = {2014}, language = {en} } @book{GroetschelLovaszSchrijver1988, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Geometric Algorithms and Combinatorial Optimization}, volume = {2}, journal = {Algorithms and Combinatorics}, publisher = {Springer}, isbn = {3-540-13624-X, 0-387-13624-X (U.S.)}, year = {1988}, language = {en} } @inproceedings{GroetschelLovaszSchrijver1984, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Geometric Methods in Combinatorial Optimization}, booktitle = {Progress in Combinatorial Optimization, (Conference Waterloo/Ontario 1982)}, editor = {Pulleyblank, William}, publisher = {Academic Press}, pages = {167 -- 183}, year = {1984}, language = {en} } @incollection{GroetschelLovaszSchrijver1984, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Polynomial algorithms for perfect graphs}, volume = {21}, booktitle = {Topics on perfect graphs}, editor = {Berge, Claude and Chv{\´a}tal, Vašek}, publisher = {North-Holland}, pages = {325 -- 356}, year = {1984}, language = {en} } @article{GroetschelLovaszSchrijver1984, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Corrigendum to our paper "The ellipsoid method and its consequences in combinatorial optimization"}, volume = {4}, journal = {Combinatorica}, number = {4}, pages = {291 -- 295}, year = {1984}, language = {en} } @article{GroetschelLovaszSchrijver1986, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {Relaxations of Vertex Packing}, volume = {40}, journal = {Journal of Combinatorial Theory, Series B}, pages = {330 -- 343}, year = {1986}, language = {en} } @article{GroetschelLovaszSchrijver1981, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {The ellipsoid method and its consequences in combinatorial optimization}, volume = {1}, journal = {Combinatorica}, number = {2}, pages = {169 -- 197}, year = {1981}, language = {en} } @article{GroetschelLovaszSchrijver1981, author = {Gr{\"o}tschel, Martin and Lov{\´a}sz, L{\´a}szlo and Schrijver, Alexander}, title = {The ellipsoid method and its consequences in combinatorial optimization}, journal = {IIASA Collab. Proceedings Ser. CP-81-S1}, pages = {511 -- 546}, year = {1981}, language = {en} } @article{AchterbergKochMartin2006, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {MIPLIB 2003}, volume = {34}, journal = {Operations Research Letters}, number = {4}, publisher = {Elsevier / North-Holland}, doi = {10.1016/j.orl.2005.07.009}, pages = {361 -- 372}, year = {2006}, language = {en} } @inproceedings{EisenblaetterKochMartinetal.2003, author = {Eisenbl{\"a}tter, Andreas and Koch, Thorsten and Martin, Alexander and Achterberg, Tobias and F{\"u}genschuh, Armin and Koster, Arie M.C.A. and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Modelling Feasible Network Configurations for UMTS}, booktitle = {Telecommunications Network Design and Management}, editor = {Anandalingam, G. and Raghavan, S.}, publisher = {Kluver}, year = {2003}, language = {en} } @inproceedings{EisenblaetterFuegenschuhGeerdesetal.2003, author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Geerdes, Hans-Florian and Junglas, Daniel and Koch, Thorsten and Martin, Alexander}, title = {Optimisation Methods for UMTS Radio Network Planning}, booktitle = {Operation Research Proceedings 2003}, editor = {Ahr, Dino and Fahrion, Roland and Oswald, Marcus and Reinelt, Gerhard}, publisher = {Springer}, doi = {10.1007/978-3-642-17022-5_5}, pages = {31 -- 38}, year = {2003}, language = {en} } @article{AchterbergKochMartin2005, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {Branching Rules Revisited}, volume = {33}, journal = {Operations Research Letters}, number = {1}, publisher = {Elsevier / North-Holland}, doi = {10.1016/j.orl.2004.04.002}, pages = {42 -- 54}, year = {2005}, language = {en} } @article{KochMartin1998, author = {Koch, Thorsten and Martin, Alexander}, title = {Solving Steiner tree problems in graphs to optimality}, volume = {32}, journal = {Networks}, doi = {10.1002/(SICI)1097-0037(199810)32:3\%3C207::AID-NET5\%3E3.0.CO;2-O}, pages = {207 -- 232}, year = {1998}, language = {en} } @incollection{KochMartinVoss2001, author = {Koch, Thorsten and Martin, Alexander and Voß, Stefan}, title = {SteinLib: An Updated Library on Steiner Tree Problems in Graphs}, booktitle = {Steiner Trees in Industry}, editor = {Du, D.-Z. and Cheng, X.}, publisher = {Kluwer}, doi = {10.1007/978-1-4613-0255-1_9}, pages = {285 -- 325}, year = {2001}, language = {en} } @article{FiedlerLeichtleKaseetal.2009, author = {Fiedler, Georg Martin and Leichtle, Alexander Benedikt and Kase, Julia and Baumann, Sven and Ceglarek, Uta and Felix, Klaus and Conrad, Tim and Witzigmann, Helmut and Weimann, Arved and Sch{\"u}tte, Christof and Hauss, Johann and B{\"u}chler, Markus and Thiery, Joachim}, title = {Serum Peptidome Profiling Revealed Platelet Factor 4 as a Potential Discriminating Peptide Associated With Pancreatic Cancer}, volume = {15}, journal = {Clinical Cancer Research}, number = {11}, publisher = {American Association for Cancer Research,}, doi = {10.1158/1078-0432.CCR-08-2701}, pages = {3812 -- 3819}, year = {2009}, language = {en} } @inproceedings{MartinMuellerPokutta2010, author = {Martin, Alexander and M{\"u}ller, J. and Pokutta, Sebastian}, title = {On clearing coupled day-ahead electricity markets}, booktitle = {Proceedings of 23rd Australasian Finance and Banking Conference}, year = {2010}, language = {en} } @inproceedings{HelmkeGluchshenkoMartinetal.2011, author = {Helmke, H. and Gluchshenko, O. and Martin, Alexander and Peter, A. and Pokutta, Sebastian and Siebert, U.}, title = {Optimal Mixed-Mode Runway Scheduling}, booktitle = {Proceedings of DACS}, year = {2011}, language = {en} } @misc{BorndoerferFerreiraMartin1997, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Matrix Decomposition by Branch-and-Cut}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2839}, number = {SC-97-14}, year = {1997}, abstract = {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.}, language = {en} } @misc{BixbyMartin1996, author = {Bixby, Robert E. and Martin, Alexander}, title = {Parallelizing the Dual Simplex Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2112}, number = {SC-95-45}, year = {1996}, abstract = {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.}, language = {en} } @misc{DahlMartinStoer1995, author = {Dahl, Geir and Martin, Alexander and Stoer, Mechthild}, title = {Routing through virtual paths in layered telecommunication networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2070}, number = {SC-95-41}, year = {1995}, abstract = {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.}, language = {en} } @misc{KochMartin1996, author = {Koch, Thorsten and Martin, Alexander}, title = {Solving Steiner Tree Problems in Graphs to Optimality}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2526}, number = {SC-96-42}, year = {1996}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1993, author = {Martin, Alexander and Weismantel, Robert}, title = {Packing Paths and Steiner Trees: Routing of Electronic Circuits.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1113}, number = {SC-93-15}, year = {1993}, abstract = {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.}, language = {en} } @misc{FerreiraMartinSouzaetal.1994, author = {Ferreira, Carlos E. and Martin, Alexander and Souza, Cid C. de and Weismantel, Robert and Wolsey, Laurence}, title = {Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1450}, number = {SC-94-16}, year = {1994}, abstract = {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.}, language = {en} } @misc{FerreiraMartinSouzaetal.1994, author = {Ferreira, Carlos E. and Martin, Alexander and Souza, Cid C. de and Weismantel, Robert and Wolsey, Laurence}, title = {The Node Capacitated Graph Partitioning Problem: A Computational Study.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1469}, number = {SC-94-17}, year = {1994}, abstract = {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.}, language = {en} } @misc{WeismantelFerreiraMartin1993, author = {Weismantel, Robert and Ferreira, Carlos E. and Martin, Alexander}, title = {A Cutting Plane Based Algorithm for the Multiple Knapsack Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1031}, number = {SC-93-07}, year = {1993}, abstract = {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.}, language = {en} } @misc{JuengerMartinReineltetal.1992, author = {J{\"u}nger, Michael and Martin, Alexander and Reinelt, Gerhard and Weismantel, Robert}, title = {Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-803}, number = {SC-92-10}, year = {1992}, abstract = {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.}, language = {en} } @misc{FerreiraMartinWeismantel1993, author = {Ferreira, Carlos E. and Martin, Alexander and Weismantel, Robert}, title = {Facets for the Multiple Knapsack Problem.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1007}, number = {SC-93-04}, year = {1993}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1998, author = {Martin, Alexander and Weismantel, Robert}, title = {Conjunctive Cuts for Integer Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3618}, number = {SC-98-18}, year = {1998}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1997, author = {Martin, Alexander and Weismantel, Robert}, title = {Contributions to General Mixed Integer Knapsack Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3075}, number = {SC-97-38}, year = {1997}, abstract = {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.}, language = {en} } @article{GamrathGleixnerKochetal.2019, author = {Gamrath, Gerald and Gleixner, Ambros and Koch, Thorsten and Miltenberger, Matthias and Kniasew, Dimitri and Schl{\"o}gel, Dominik and Martin, Alexander and Weninger, Dieter}, title = {Tackling Industrial-Scale Supply Chain Problems by Mixed-Integer Programming}, volume = {37}, journal = {Journal of Computational Mathematics}, doi = {10.4208/jcm.1905-m2019-0055}, pages = {866 -- 888}, year = {2019}, abstract = {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.}, language = {en} } @misc{GamrathKochMartinetal.2013, author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in Presolving for Mixed Integer Programming}, issn = {1438-0064}, doi = {10.1007/s12532-015-0083-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42530}, year = {2013}, abstract = {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.}, language = {en} } @misc{KochMartinVoss2000, author = {Koch, Thorsten and Martin, Alexander and Voß, Stefan}, title = {SteinLib: An Updated Library on Steiner Tree Problems in Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6056}, number = {00-37}, year = {2000}, abstract = {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.}, language = {en} } @misc{EisenblaetterFuegenschuhKochetal.2002, author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Koch, Thorsten and Koster, Arie M.C.A. and Martin, Alexander and Pfender, Tobias and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Modelling Feasible Network Configurations for UMTS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6837}, number = {02-16}, year = {2002}, abstract = {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.}, language = {en} } @misc{AchterbergKochMartin2002, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {Branching on History Information}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6990}, number = {02-32}, year = {2002}, abstract = {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.}, language = {en} } @misc{EisenblaetterFuegenschuhGeerdesetal.2003, author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Geerdes, Hans-Florian and Junglas, Daniel and Koch, Thorsten and Martin, Alexander}, title = {Optimization Methods for UMTS Radio Network Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7637}, number = {03-41}, year = {2003}, abstract = {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.}, language = {en} } @phdthesis{Martin1992, author = {Martin, Alexander}, title = {Packen von Steinerb{\"a}umen: Polyedrische Studien und Anwendung.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4894}, number = {TR-92-04}, year = {1992}, abstract = {Gegeben sei ein Graph \$G=(V,E)\$ mit positiven Kantenkapazit{\"a}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{\"o}chstens \$c_e\$ Kantenmengen aus \$S_1,\ldots,S_N\$ vorkommt. Eine zul{\"a}ssige L{\"o}sung dieses Problems nennen wir eine Steinerbaumpackung. Ist zus{\"a}tzlich eine Gewichtung der Kanten gegeben und nach einer bez{\"u}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{\"a}tskriterien auf einer Grundfl{\"a}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{\"o}sung des Schnittebenenverfahrens liefert eine untere Schranke f{\"u}r die Optimall{\"o}sung und dient als Grundlage f{\"u}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.}, language = {de} } @misc{MarchandMartinWeismanteletal.1999, author = {Marchand, Hugues and Martin, Alexander and Weismantel, Robert and Wolsey, Laurence}, title = {Cutting Planes in Integer and Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4339}, number = {SC-99-44}, year = {1999}, abstract = {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.}, language = {en} } @misc{MartinWeismantel1997, author = {Martin, Alexander and Weismantel, Robert}, title = {The Intersection of Knapsack Polyhedra and Extensions}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3300}, number = {SC-97-61}, year = {1997}, abstract = {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.}, language = {en} } @misc{AchterbergKochMartin2004, author = {Achterberg, Tobias and Koch, Thorsten and Martin, Alexander}, title = {Branching rules revisited}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7886}, number = {04-13}, year = {2004}, abstract = {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.}, language = {en} } @misc{EisenblaetterGeerdesKochetal.2004, author = {Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Koch, Thorsten and Martin, Alexander and Wess{\"a}ly, Roland}, title = {UMTS Radio Network Evaluation and Optimization beyond Snapshots}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7903}, number = {04-15}, year = {2004}, abstract = {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.}, language = {en} } @article{ConradLeichtleCeglareketal.2013, author = {Conrad, Tim and Leichtle, Alexander Benedikt and Ceglarek, Uta and Weinert, P. and Nakas, C.T. and Nuoffer, Jean-Marc and Kase, Julia and Witzigmann, Helmut and Thiery, Joachim and Fiedler, Georg Martin}, title = {Pancreatic carcinoma, pancreatitis, and healthy controls - metabolite models in a three-class diagnostic dilemma}, volume = {9}, journal = {Metabolomics}, number = {3}, doi = {10.1007/s11306-012-0476-7}, pages = {677 -- 687}, year = {2013}, abstract = {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.}, language = {en} } @article{ConradLeichtleNuofferetal.2012, author = {Conrad, Tim and Leichtle, Alexander Benedikt and Nuoffer, Jean-Marc and Ceglarek, Uta and Kase, Julia and Witzigmann, Helmut and Thiery, Joachim and Fiedler, Georg Martin}, title = {Serum amino acid profiles and their alterations in colorectal cancer}, journal = {Metabolomics}, doi = {10.1007/s11306-011-0357-5}, year = {2012}, abstract = {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.}, language = {en} } @article{ConradGenzelCvetkovicetal.2017, author = {Conrad, Tim and Genzel, Martin and Cvetkovic, Nada and Wulkow, Niklas and Leichtle, Alexander Benedikt and Vybiral, Jan and Kytyniok, Gitta and Sch{\"u}tte, Christof}, title = {Sparse Proteomics Analysis - a compressed sensing-based approach for feature selection and classification of high-dimensional proteomics mass spectrometry data}, volume = {18}, journal = {BMC Bioinfomatics}, number = {160}, doi = {10.1186/s12859-017-1565-4}, year = {2017}, abstract = {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.}, language = {en} } @article{WilsonAnglinAmbellanetal.2017, author = {Wilson, David and Anglin, Carolyn and Ambellan, Felix and Grewe, Carl Martin and Tack, Alexander and Lamecker, Hans and Dunbar, Michael and Zachow, Stefan}, title = {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}, volume = {12}, journal = {International Journal of Computer Assisted Radiology and Surgery}, number = {12}, publisher = {Springer}, doi = {10.1007/s11548-017-1630-5}, pages = {2097 -- 2105}, year = {2017}, abstract = {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.}, language = {en} } @inproceedings{WeinholdLackorzynskiBierbaumetal.2016, author = {Weinhold, Carsten and Lackorzynski, Adam and Bierbaum, Jan and K{\"u}ttler, Martin and Planeta, Maksym and H{\"a}rtig, Hermann and Shiloh, Amnon and Levy, Ely and Ben-Nun, Tal and Barak, Amnon and Steinke, Thomas and Sch{\"u}tt, Thorsten and Fajerski, Jan and Reinefeld, Alexander and Lieber, Matthias and Nagel, Wolfgang}, title = {FFMK: A Fast and Fault-tolerant Microkernel-based System for Exascale Computing}, booktitle = {SPPEXA Symposium 2016}, doi = {10.1007/978-3-319-40528-5_18}, year = {2016}, language = {en} } @article{HeidaSikorskiWeber2022, author = {Heida, Martin and Sikorski, Alexander and Weber, Marcus}, title = {Consistency and order 1 convergence of cell-centered finite volume discretizations of degenerate elliptic problems in any space dimension}, journal = {SIAM Journal on Numerical Analysis}, doi = {10.20347/WIAS.PREPRINT.2913}, year = {2022}, abstract = {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.}, language = {en} } @article{SikorskiHeida2024, author = {Sikorski, Alexander and Heida, Martin}, title = {Voronoi Graph - Improved raycasting and integration schemes for high dimensional Voronoi diagrams}, arxiv = {http://arxiv.org/abs/2405.10050}, year = {2024}, abstract = {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.}, language = {en} } @article{XieGruberCrampenetal.2025, author = {Xie, Kunpeng and Gruber, Lennart Johannes and Crampen, Martin and Li, Yao and Ferreira, Andr{\´e} and Tappeiner, Elias and Gillot, Maxime and Schepers, Jan and Xu, Jiangchang and Pankert, Tobias and Beyer, Michel and Shahamiri, Negar and ten Brink, Reinier and Dot, Gauthier and Weschke, Charlotte and van Nistelrooij, Niels and Verhelst, Pieter-Jan and Guo, Yan and Xu, Zhibin and Bienzeisler, Jonas and Rashad, Ashkan and Fl{\"u}gge, Tabea and Cotton, Ross and Vinayahalingam, Shankeeth and Ilesan, Robert and Raith, Stefan and Madsen, Dennis and Seibold, Constantin and Xi, Tong and Berg{\´e}, Stefaan and Nebelung, Sven and Kodym, Oldřich and Sundqvist, Osku and Thieringer, Florian and Lamecker, Hans and Coppens, Antoine and Potrusil, Thomas and Kraeima, Joep and Witjes, Max and Wu, Guomin and Chen, Xiaojun and Lambrechts, Adriaan and Cevidanes, Lucia H Soares and Zachow, Stefan and Hermans, Alexander and Truhn, Daniel and Alves, Victor and Egger, Jan and R{\"o}hrig, Rainer and H{\"o}lzle, Frank and Puladi, Behrus}, title = {Beyond Benchmarks: Towards Robust Artificial Intelligence Bone Segmentation in Socio-Technical Systems}, volume = {299}, journal = {Expert Systems With Applications}, number = {Part D}, doi = {10.1016/j.eswa.2025.130031}, year = {2025}, abstract = {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.}, language = {en} } @article{BaermannMartinPokuttaetal.2018, author = {B{\"a}rmann, Andreas and Martin, Alexander and Pokutta, Sebastian and Schneider, Oskar}, title = {An Online-Learning Approach to Inverse Optimization}, year = {2018}, language = {en} } @article{EisenblaetterGeerdesKochetal.2005, author = {Eisenbl{\"a}tter, Andreas and Geerdes, Hans-Florian and Koch, Thorsten and Martin, Alexander and Wess{\"a}ly, Roland}, title = {UMTS Radio Network Evaluation and Optimization beyond Snapshots}, volume = {63}, journal = {Mathematical Methods of Operations Research}, number = {1}, doi = {10.1007/s00186-005-0002-z}, pages = {1 -- 29}, year = {2005}, language = {en} } @inproceedings{FuegenschuhHessMartinetal.2007, author = {F{\"u}genschuh, Armin and Hess, Wolfgang and Martin, Alexander and Ulbrich, Stefan}, title = {Diskrete und kontinuierliche Modelle zur Topologie- und Geometrie-Optimierung von Blechprofilen}, booktitle = {Sonderforschungsbereich 666}, editor = {Groche, P.}, pages = {37 -- 47}, year = {2007}, language = {en} }