TY - JOUR A1 - Enke, Harry A1 - Steinmetz, Matthias A1 - Adorf, Hans-Martin A1 - Beck-Ratzka, Alexander A1 - Breitling, Frank A1 - Brüsemeister, Thomas A1 - Carlson, Arthur A1 - Ensslin, Torsten A1 - Högqvist, Mikael A1 - Nickelt, Iliya A1 - Radke, Thomas A1 - Reinefeld, Alexander A1 - Reiser, Angelika A1 - Scholl, Tobias A1 - Spurzem, Rainer A1 - Steinacker, Jürgen A1 - Voges, Wolfgang A1 - Wambsganß, Joachim A1 - White, Steve T1 - AstroGrid-D: Grid technology for astronomical science JF - New Astronomy Y1 - 2011 UR - http://www.sciencedirect.com/science/article/pii/S1384107610000837 U6 - https://doi.org/10.1016/j.newast.2010.07.005 VL - 16 IS - 2 SP - 79 EP - 93 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Göttlich, Simone A1 - Herty, Michael A1 - Klar, Alexander A1 - Martin, Alexander T1 - A Discrete Optimization Approach to Large Scale Supply Networks Based on Partial Differential Equations JF - SIAM Journal on Scientific Computing Y1 - 2008 VL - 30 IS - 3 SP - 1490 EP - 1507 ER - TY - JOUR A1 - Sekuboyina, Anjany A1 - Husseini, Malek E. A1 - Bayat, Amirhossein A1 - Löffler, Maximilian A1 - Liebl, Hans A1 - Li, Hongwei A1 - Tetteh, Giles A1 - Kukačka, Jan A1 - Payer, Christian A1 - Štern, Darko A1 - Urschler, Martin A1 - Chen, Maodong A1 - Cheng, Dalong A1 - Lessmann, Nikolas A1 - Hu, Yujin A1 - Wang, Tianfu A1 - Yang, Dong A1 - Xu, Daguang A1 - Ambellan, Felix A1 - Amiranashvili, Tamaz A1 - Ehlke, Moritz A1 - Lamecker, Hans A1 - Lehnert, Sebastian A1 - Lirio, Marilia A1 - de Olaguer, Nicolás Pérez A1 - Ramm, Heiko A1 - Sahu, Manish A1 - Tack, Alexander A1 - Zachow, Stefan A1 - Jiang, Tao A1 - Ma, Xinjun A1 - Angerman, Christoph A1 - Wang, Xin A1 - Brown, Kevin A1 - Kirszenberg, Alexandre A1 - Puybareau, Élodie A1 - Chen, Di A1 - Bai, Yiwei A1 - Rapazzo, Brandon H. A1 - Yeah, Timyoas A1 - Zhang, Amber A1 - Xu, Shangliang A1 - Hou, Feng A1 - He, Zhiqiang A1 - Zeng, Chan A1 - Xiangshang, Zheng A1 - Liming, Xu A1 - Netherton, Tucker J. A1 - Mumme, Raymond P. A1 - Court, Laurence E. A1 - Huang, Zixun A1 - He, Chenhang A1 - Wang, Li-Wen A1 - Ling, Sai Ho A1 - Huynh, Lê Duy A1 - Boutry, Nicolas A1 - Jakubicek, Roman A1 - Chmelik, Jiri A1 - Mulay, Supriti A1 - Sivaprakasam, Mohanasankar A1 - Paetzold, Johannes C. A1 - Shit, Suprosanna A1 - Ezhov, Ivan A1 - Wiestler, Benedikt A1 - Glocker, Ben A1 - Valentinitsch, Alexander A1 - Rempfler, Markus A1 - Menze, Björn H. A1 - Kirschke, Jan S. T1 - VerSe: A Vertebrae labelling and segmentation benchmark for multi-detector CT images JF - Medical Image Analysis N2 - Vertebral labelling and segmentation are two fundamental tasks in an automated spine processing pipeline. Reliable and accurate processing of spine images is expected to benefit clinical decision support systems for diagnosis, surgery planning, and population-based analysis of spine and bone health. However, designing automated algorithms for spine processing is challenging predominantly due to considerable variations in anatomy and acquisition protocols and due to a severe shortage of publicly available data. Addressing these limitations, the Large Scale Vertebrae Segmentation Challenge (VerSe) was organised in conjunction with the International Conference on Medical Image Computing and Computer Assisted Intervention (MICCAI) in 2019 and 2020, with a call for algorithms tackling the labelling and segmentation of vertebrae. Two datasets containing a total of 374 multi-detector CT scans from 355 patients were prepared and 4505 vertebrae have individually been annotated at voxel level by a human-machine hybrid algorithm (https://osf.io/nqjyw/, https://osf.io/t98fz/). A total of 25 algorithms were benchmarked on these datasets. In this work, we present the results of this evaluation and further investigate the performance variation at the vertebra level, scan level, and different fields of view. We also evaluate the generalisability of the approaches to an implicit domain shift in data by evaluating the top-performing algorithms of one challenge iteration on data from the other iteration. The principal takeaway from VerSe: the performance of an algorithm in labelling and segmenting a spine scan hinges on its ability to correctly identify vertebrae in cases of rare anatomical variations. The VerSe content and code can be accessed at: https://github.com/anjany/verse. Y1 - 2021 U6 - https://doi.org/10.1016/j.media.2021.102166 VL - 73 ER - TY - JOUR A1 - Sekuboyina, Anjany A1 - Bayat, Amirhossein A1 - Husseini, Malek E. A1 - Löffler, Maximilian A1 - Li, Hongwei A1 - Tetteh, Giles A1 - Kukačka, Jan A1 - Payer, Christian A1 - Štern, Darko A1 - Urschler, Martin A1 - Chen, Maodong A1 - Cheng, Dalong A1 - Lessmann, Nikolas A1 - Hu, Yujin A1 - Wang, Tianfu A1 - Yang, Dong A1 - Xu, Daguang A1 - Ambellan, Felix A1 - Amiranashvili, Tamaz A1 - Ehlke, Moritz A1 - Lamecker, Hans A1 - Lehnert, Sebastian A1 - Lirio, Marilia A1 - de Olaguer, Nicolás Pérez A1 - Ramm, Heiko A1 - Sahu, Manish A1 - Tack, Alexander A1 - Zachow, Stefan A1 - Jiang, Tao A1 - Ma, Xinjun A1 - Angerman, Christoph A1 - Wang, Xin A1 - Wei, Qingyue A1 - Brown, Kevin A1 - Wolf, Matthias A1 - Kirszenberg, Alexandre A1 - Puybareau, Élodie A1 - Valentinitsch, Alexander A1 - Rempfler, Markus A1 - Menze, Björn H. A1 - Kirschke, Jan S. T1 - VerSe: A Vertebrae Labelling and Segmentation Benchmark for Multi-detector CT Images JF - arXiv Y1 - 2020 ER - TY - JOUR A1 - Schimunek, Johannes A1 - Seidl, Philipp A1 - Elez, Katarina A1 - Hempel, Tim A1 - Le, Tuan A1 - Noé, Frank A1 - Olsson, Simon A1 - Raich, Lluís A1 - Winter, Robin A1 - Gokcan, Hatice A1 - Gusev, Filipp A1 - Gutkin, Evgeny M. A1 - Isayev, Olexandr A1 - Kurnikova, Maria G. A1 - Narangoda, Chamali H. A1 - Zubatyuk, Roman A1 - Bosko, Ivan P. A1 - Furs, Konstantin V. A1 - Karpenko, Anna D. A1 - Kornoushenko, Yury V. A1 - Shuldau, Mikita A1 - Yushkevich, Artsemi A1 - Benabderrahmane, Mohammed B. A1 - Bousquet-Melou, Patrick A1 - Bureau, Ronan A1 - Charton, Beatrice A1 - Cirou, Bertrand C. A1 - Gil, Gérard A1 - Allen, William J. A1 - Sirimulla, Suman A1 - Watowich, Stanley A1 - Antonopoulos, Nick A1 - Epitropakis, Nikolaos A1 - Krasoulis, Agamemnon A1 - Itsikalis, Vassilis A1 - Theodorakis, Stavros A1 - Kozlovskii, Igor A1 - Maliutin, Anton A1 - Medvedev, Alexander A1 - Popov, Petr A1 - Zaretckii, Mark A1 - Eghbal-Zadeh, Hamid A1 - Halmich, Christina A1 - Hochreiter, Sepp A1 - Mayr, Andreas A1 - Ruch, Peter A1 - Widrich, Michael A1 - Berenger, Francois A1 - Kumar, Ashutosh A1 - Yamanishi, Yoshihiro A1 - Zhang, Kam Y. J. A1 - Bengio, Emmanuel A1 - Bengio, Yoshua A1 - Jain, Moksh J. A1 - Korablyov, Maksym A1 - Liu, Cheng-Hao A1 - Marcou, Gilles A1 - Glaab, Enrico A1 - Barnsley, Kelly A1 - Iyengar, Suhasini M. A1 - Ondrechen, Mary Jo A1 - Haupt, V. Joachim A1 - Kaiser, Florian A1 - Schroeder, Michael A1 - Pugliese, Luisa A1 - Albani, Simone A1 - Athanasiou, Christina A1 - Beccari, Andrea A1 - Carloni, Paolo A1 - D’Arrigo, Giulia A1 - Gianquinto, Eleonora A1 - Goßen, Jonas A1 - Hanke, Anton A1 - Joseph, Benjamin P. A1 - Kokh, Daria B. A1 - Kovachka, Sandra A1 - Manelfi, Candida A1 - Mukherjee, Goutam A1 - Muñiz-Chicharro, Abraham A1 - Musiani, Francesco A1 - Nunes-Alves, Ariane A1 - Paiardi, Giulia A1 - Rossetti, Giulia A1 - Sadiq, S. Kashif A1 - Spyrakis, Francesca A1 - Talarico, Carmine A1 - Tsengenes, Alexandros A1 - Wade, Rebecca C. A1 - Copeland, Conner A1 - Gaiser, Jeremiah A1 - Olson, Daniel R. A1 - Roy, Amitava A1 - Venkatraman, Vishwesh A1 - Wheeler, Travis J. A1 - Arthanari, Haribabu A1 - Blaschitz, Klara A1 - Cespugli, Marco A1 - Durmaz, Vedat A1 - Fackeldey, Konstantin A1 - Fischer, Patrick D. A1 - Gorgulla, Christoph A1 - Gruber, Christian A1 - Gruber, Karl A1 - Hetmann, Michael A1 - Kinney, Jamie E. A1 - Padmanabha Das, Krishna M. A1 - Pandita, Shreya A1 - Singh, Amit A1 - Steinkellner, Georg A1 - Tesseyre, Guilhem A1 - Wagner, Gerhard A1 - Wang, Zi-Fu A1 - Yust, Ryan J. A1 - Druzhilovskiy, Dmitry S. A1 - Filimonov, Dmitry A. A1 - Pogodin, Pavel V. A1 - Poroikov, Vladimir A1 - Rudik, Anastassia V. A1 - Stolbov, Leonid A. A1 - Veselovsky, Alexander V. A1 - De Rosa, Maria A1 - De Simone, Giada A1 - Gulotta, Maria R. A1 - Lombino, Jessica A1 - Mekni, Nedra A1 - Perricone, Ugo A1 - Casini, Arturo A1 - Embree, Amanda A1 - Gordon, D. Benjamin A1 - Lei, David A1 - Pratt, Katelin A1 - Voigt, Christopher A. A1 - Chen, Kuang-Yu A1 - Jacob, Yves A1 - Krischuns, Tim A1 - Lafaye, Pierre A1 - Zettor, Agnès A1 - Rodríguez, M. Luis A1 - White, Kris M. A1 - Fearon, Daren A1 - Von Delft, Frank A1 - Walsh, Martin A. A1 - Horvath, Dragos A1 - Brooks III, Charles L. A1 - Falsafi, Babak A1 - Ford, Bryan A1 - García-Sastre, Adolfo A1 - Yup Lee, Sang A1 - Naffakh, Nadia A1 - Varnek, Alexandre A1 - Klambauer, Günter A1 - Hermans, Thomas M. T1 - A community effort in SARS-CoV-2 drug discovery JF - Molecular Informatics KW - COVID-19 KW - drug discovery KW - machine learning KW - SARS-CoV-2 Y1 - 2023 U6 - https://doi.org/https://doi.org/10.1002/minf.202300262 VL - 43 IS - 1 SP - e202300262 ER - TY - CHAP A1 - Weinhold, Carsten A1 - Lackorzynski, Adam A1 - Bierbaum, Jan A1 - Küttler, Martin A1 - Planeta, Maksym A1 - Weisbach, Hannes A1 - Hille, Matthias A1 - Härtig, Hermann A1 - Margolin, Alexander A1 - Sharf, Dror A1 - Levy, Ely A1 - Gak, Pavel A1 - Barak, Amnon A1 - Gholami, Masoud A1 - Schintke, Florian A1 - Schütt, Thorsten A1 - Reinefeld, Alexander A1 - Lieber, Matthias A1 - Nagel, Wolfgang T1 - FFMK: A Fast and Fault-Tolerant Microkernel-Based System for Exascale Computing T2 - Software for Exascale Computing - SPPEXA 2016-2019 Y1 - 2019 U6 - https://doi.org/10.1007/978-3-030-47956-5_16 SP - 483 EP - 516 PB - Springer ER - TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - The Orientation Model for Frequency Assignment Problems N2 - Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem. T3 - ZIB-Report - TR-98-01 KW - Minimum-Cost Flow Problems KW - Cellular Radio Telephone Systems KW - Frequency Assignment Problem KW - Integer Programming Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5627 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Consecutive Case N2 - We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.~e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets. T3 - ZIB-Report - SC-95-31 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1976 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Frequency Assignment in Cellular Phone Networks N2 - We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice. T3 - ZIB-Report - SC-97-35 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3044 ER - TY - GEN A1 - Bruns, Winfried A1 - Gubeladze, Joseph A1 - Henk, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - A counterexample to an integer analogue of Caratheodorys theorem N2 - For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed. T3 - ZIB-Report - SC-98-28 KW - Integral pointed cones KW - Hilbert basis KW - integral Carathéodory property Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3718 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Polyhedral Investigations. N2 - Let $G=(V,E)$ be a graph and $T\subseteq V$ be a node set. We call an edge set $S$ a Steiner tree with respect to $T$ if $S$ connects all pairs of nodes in $T$. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph $G=(V,E)$ with edge weights $w_e$, edge capacities $c_e, e \in E,$ and node sets $T_1,\ldots,T_N$, find edge sets $S_1,\ldots,S_N$ such that each $S_k$ is a Steiner tree with respect to $T_k$, at most $c_e$ of these edge sets use edge $e$ for each $e\in E$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing Problem from a polyhedral point of view and define an appropriate polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper SC 92-09. T3 - ZIB-Report - SC-92-08 KW - cutting planes KW - Facets KW - Packing KW - polyhedron KW - Steiner tree Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-786 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results. N2 - In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems. T3 - ZIB-Report - SC-92-09 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-792 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Steiner Tree Packing Problem in VLSI-Design. N2 - In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing. T3 - ZIB-Report - SC-94-02 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1328 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Grötschel, Martin A1 - Kiefl, Stefan A1 - Krispenz, Ludwig A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Some Integer Programs Arising in the Design of Main Frame Computers. N2 - In this paper we describe and discuss a problem that arises in the (global) design of a main frame computer. The task is to assign certain functional units to a given number of so called multi chip modules or printed circuit boards taking into account many technical constraints and minimizing a complex objective function. We describe the real world problem. A thorough mathematical modelling of all aspects of this problem results in a rather complicated integer program that seems to be hopelessly difficult -- at least for the present state of integer programming technology. We introduce several relaxations of the general model, which are also $NP$-hard, but seem to be more easily accessible. The mathematical relations between the relaxations and the exact formulation of the problem are discussed as well. T3 - ZIB-Report - SC-92-25 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-957 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Routing in Grid Graphs by Cutting Planes. N2 - {\def\N{{\cal N}} \def\R{\hbox{\rm I\kern-2pt R}} \def\MN{{\rm I\kern-2pt N}} In this paper we study the following problem, which we call the weighted routing problem. Let be given a graph $G=(V,E)$ with non-negative edge weights $w_e\in\R_+$ and integer edge capacities $c_e\in\MN$ and let $\N=\{T_1,\ldots,T_N\}$, $N\ge 1$, be a list of node sets. The weighted routing problem consists in finding edge sets $S_1,\ldots,S_N$ such that, for each $k\in\{1,\ldots,N\}$, the subgraph $(V(S_k),S_k)$ contains an $[s,t]$-path for all $s,t\in T_k$, at most $c_e$ of these edge sets use edge $e$ for each $e\in E$, and such that the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from the routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the weighted routing problem from a polyhedral point of view. We define an appropriate polyhedron and try to (partially) describe this polyhedron by means of inequalities. We briefly sketch our separation algorithms for some of the presented classes of inequalities. Based on these separation routines we have implemented a branch and cut algorithm. Our algorithm is applicable to an important subclass of routing problems arising in VLSI-design, namely to problems where the underlying graph is a grid graph and the list of node sets is located on the outer face of the grid. We report on our computational experience with this class of problem instances.} T3 - ZIB-Report - SC-92-26 KW - routing in VLSI-design KW - Steiner tree KW - Steiner tree packing KW - cutting plane algorithm Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-967 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Further Facets. N2 - In this paper we continue the investigations in [GMW92a] for the \def\sbppo{Steiner tree packing polyhedron} \sbppo. We present several new classes of valid inequalities and give sufficient (and necessary) conditions for these inequalities to be facet-defining. It is intended to incorporate these inequalities into an existing cutting plane algorithm that is applicable to practical problems arising in the design of electronic circuits. T3 - ZIB-Report - SC-93-01 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-975 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Separation Algorithms. N2 - In this paper we investigate separation problems for classes of inequalities valid for the polytope associated with the Steiner tree packing problem, a problem that arises, e.~g., in VLSI routing. The separation problem for Steiner partition inequalities is ${\cal N}\hskip-2pt{\cal P}$-hard in general. We show that it can be solved in polynomial time for those instances that come up in switchbox routing. Our algorithm uses dynamic programming techniques. These techniques are also applied to the much more complicated separation problem for alternating cycle inequalities. In this case we can compute in polynomial time, given some point $y$, a lower bound for the gap $\alpha-a^Ty$ over all alternating cycle inequalities $a^Tx\ge\alpha$. This gives rise to a very effective separation heuristic. A by-product of our algorithm is the solution of a combinatorial optimization problem that is interesting in its own right: Find a shortest path in a graph where the ``length'' of a path is its usual length minus the length of its longest edge. T3 - ZIB-Report - SC-93-02 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-984 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Noncrossing Case. N2 - We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that no two terminal pairs cross, then a path packing, i.~e.,a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets. T3 - ZIB-Report - SC-93-26 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1225 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 - CHAP A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert ED - Rinaldi, Giovanni ED - Wolsey, Laurence T1 - Routing in grid graphs by cutting planes T2 - Integer Programming and Combinatorial Optimization. Proceedings of a Conference held at Centro Ettore Majorana, Erice, Italy, April 29 - May 1, 1993 Y1 - 1993 SP - 447 EP - 461 PB - Librarian CORE CY - Louvain-la-Neuve ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Steiner tree packing problem in VLSI design JF - Mathematical Programming Y1 - 1997 VL - 78 IS - 2 SP - 265 EP - 281 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - Frequency assignment in cellular phone networks JF - Annals of Operations Research Y1 - 1998 U6 - https://doi.org/10.1023/A:1018908907763 VL - 76 SP - 73 EP - 93 PB - J. C. Baltzer AG, Science Publishers ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Routing in Grid Graphs by Cutting Planes JF - ZOR - Mathematical Methods of Operations Research Y1 - 1995 VL - 41 IS - 3 SP - 255 EP - 275 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Further Facets JF - European Journal of Combinatorics Y1 - 1996 U6 - https://doi.org/10.1006/eujc.1996.0004 VL - 17 IS - 1 SP - 39 EP - 52 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner Trees: Separation Algorithms JF - SIAM Journal on Discrete Mathematics Y1 - 1996 U6 - https://doi.org/10.1137/S0895480193258716 VL - 9 IS - 2 SP - 233 EP - 257 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels JF - Computers and Mathematics with Applications Y1 - 1996 VL - 31 IS - 11 SP - 23 EP - 35 PB - Elsevier ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner trees: Polyhedral Investigations JF - Mathematical Programming, Series A Y1 - 1996 U6 - https://doi.org/10.1007/BF02592085 VL - 72 IS - 2 SP - 101 EP - 123 ER - TY - JOUR A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Steiner trees: a cutting plane algorithm and computational results JF - Mathematical Programming, Series A Y1 - 1996 U6 - https://doi.org/10.1007/BF02592086 VL - 72 IS - 2 SP - 125 EP - 145 ER - TY - JOUR A1 - Ferreira, Carlos A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert A1 - Kiefl, Stefan A1 - Krispenz, Ludwig T1 - Some Integer Programs Arising in the Design of Main Frame Computers JF - ZOR - Methods and Models of Operations Research Y1 - 1993 VL - 38 IS - 1 SP - 77 EP - 100 ER - TY - JOUR 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 JF - Optimization Methods and Software 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 feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before. Y1 - 2014 U6 - https://doi.org/10.1080/10556788.2014.888426 PB - Taylor & Francis ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Gollmer, Ralf A1 - Hayn, Christine A1 - Henrion, René 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 JF - Energy Systems 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 were 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 discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network’s capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations. Y1 - 2013 U6 - https://doi.org/10.1007/s12667-013-0099-8 VL - 5 IS - 3 SP - 449 EP - 473 PB - Springer Berlin Heidelberg CY - Berlin ER - TY - CHAP A1 - Birkhofer, Herbert A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Wäldele, Martin T1 - Algorithmenbasierte Produktentwicklung für integrale Blechbauweisen höherer Verzweigungsordnung T2 - Optimierung in der Produktentwicklung, 5. Geimeinsames Kolloquium Konstruktionstechnik Y1 - 2007 ER - TY - CHAP A1 - Birkhofer, Herbert A1 - Fügenschuh, Armin A1 - Günther, Ute A1 - Junglas, Daniel A1 - Martin, Alexander A1 - Sauer, Thorsten A1 - Ulbrich, Stefan A1 - Wäldele, Martin A1 - Walter, Stephan ED - Haasis, Hans-Dietrich ED - Kopfer, Herbert ED - Schönberger, Jörn T1 - Topology- and shape-optimization of branched sheet metal products T2 - Operations Research Proceedings Y1 - 2006 SP - 327 EP - 336 ER - TY - CHAP A1 - Martin, Alexander A1 - Geißler, Björn A1 - Heyn, 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 T2 - Optimierung in der Energiewirtschaft Y1 - 2011 SP - 105 EP - 114 PB - VDI-Verlag, Düsseldorf 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 - 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 - 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 - JOUR A1 - Koch, Thorsten A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger T1 - Capacity Evaluation for Large-Scale Gas Networks JF - German Success Stories in Industrial Mathematics Y1 - 2020 SN - 978-3-030-81454-0 U6 - https://doi.org/10.1007/978-3-030-81455-7 VL - 35 SP - 23 EP - 28 ER - TY - JOUR A1 - Aigner, Kevin-Martin A1 - Clarner, Jan-Patrick A1 - Liers, Frauke A1 - Martin, Alexander T1 - Robust Approximation of Chance Constrained DC Optimal Power Flow under Decision-Dependent Uncertainty JF - European Journal of Operational Research N2 - We propose a mathematical optimization model and its solution for joint chance constrained DC Optimal Power Flow. In this application, it is particularly important that there is a high probability of transmission limits being satisfied, even in the case of uncertain or fluctuating feed-in from renewable energy sources. In critical network situations where the network risks overload, renewable energy feed-in has to be curtailed by the transmission system operator (TSO). The TSO can reduce the feed-in in discrete steps at each network node. The proposed optimization model minimizes curtailment while ensuring that there is a high probability of transmission limits being maintained. The latter is modeled via (joint) chance constraints that are computationally challenging. Thus, we propose a solution approach based on the robust safe approximation of these constraints. Hereby, probabilistic constraints are replaced by robust constraints with suitably defined uncertainty sets constructed from historical data. The ability to discretely control the power feed-in then leads to a robust optimization problem with decision-dependent uncertainties, i.e. the uncertainty sets depend on decision variables. We propose an equivalent mixed-integer linear reformulation for box uncertainties with the exact linearization of bilinear terms. Finally, we present numerical results for different test cases from the Nesta archive, as well as for a real network. We consider the discrete curtailment of solar feed-in, for which we use real-world weather and network data. The experimental tests demonstrate the effectiveness of this method and run times are very fast. Moreover, on average the calculated robust solutions only lead to a small increase in curtailment, when compared to nominal solutions. Y1 - 2021 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 -