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 - 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 - Marchand, Hugues A1 - Martin, Alexander A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - Cutting Planes in Integer and Mixed Integer Programming N2 - This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored. T3 - ZIB-Report - SC-99-44 KW - Mixed Integer Programming KW - Cutting Planes Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4339 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Intersection of Knapsack Polyhedra and Extensions N2 - This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported. T3 - ZIB-Report - SC-97-61 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3300 ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Branching rules revisited N2 - Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost branching} strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed newstrategy. T3 - ZIB-Report - 04-13 KW - Mixed-integer-programming KW - Branch-and-Bound KW - Variable selection KW - Pseudocost-Branching KW - Strong-Branching KW - Reliability-Branching Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7886 ER - TY - GEN A1 - Eisenblätter, Andreas A1 - Geerdes, Hans-Florian A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Wessäly, Roland T1 - UMTS Radio Network Evaluation and Optimization beyond Snapshots N2 - This paper is concerned with UMTS radio network design. Our task is to reconfigure antennas and the related cells as to improve network quality. In contrast to second generation GSM networks, \emph{interference} plays a paramount role when designing third generation radio networks. A known compact formulation for assessing the interference characteristics of a radio network as coupling relations between cells based on user snapshots is generalized to statistical average load. This enables us to overcome the notorious difficulties of snapshot-based network optimization approaches. We recall a mixed-integer programming model for the network design problem that is based on user snapshots and contrast it with a new network design model based on the average coupling formulation. Exemplarily focusing on the important problem of optimizing antenna tilts, we give computational results for a fast local search algorithm and the application of a MIP solver to both models. These results demonstrate that our new average-based approaches outperform state-of-the-art snapshot models for UMTS radio network optimization. T3 - ZIB-Report - 04-15 KW - UMTS KW - Network planning KW - Network design KW - Optimization Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7903 ER - TY - JOUR A1 - Bärmann, Andreas A1 - Martin, Alexander A1 - Pokutta, Sebastian A1 - Schneider, Oskar T1 - An Online-Learning Approach to Inverse Optimization Y1 - 2018 ER - TY - JOUR A1 - Eisenblätter, Andreas A1 - Geerdes, Hans-Florian A1 - Koch, Thorsten A1 - Martin, Alexander A1 - Wessäly, Roland T1 - UMTS Radio Network Evaluation and Optimization beyond Snapshots JF - Mathematical Methods of Operations Research Y1 - 2005 UR - http://opus.kobv.de/zib/volltexte/2004/791/ U6 - https://doi.org/10.1007/s00186-005-0002-z VL - 63 IS - 1 SP - 1 EP - 29 ER - TY - 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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - CHAP A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Koch, Thorsten A1 - Koster, Arie M.C.A. A1 - Martin, Alexander A1 - Pfender, Tobias A1 - Wegel, Oliver A1 - Wessäly, Roland ED - G. Anandalingam, S. T1 - Mathematical Model of Feasible Network Configurations for UMTS T2 - Telecommunications network design and management Y1 - 2002 SP - 1 EP - 24 PB - Kluwer ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Stöveken, Peter ED - Bixby, Robert E. ED - Simchi-Levi, D. ED - Martin, Alexander ED - Zimmermann, U. T1 - Integrated Optimization of School Starting Times and Public Bus Services T2 - Mathematics in the Supply Chain Y1 - 2004 ER - TY - CHAP A1 - Eisenblätter, Andreas A1 - Fügenschuh, Armin A1 - Geerdes, Hans-Florian A1 - Junglas, Daniel A1 - Koch, Thorsten A1 - Martin, Alexander T1 - Integer Programming Methods for UMTS Radio Network Planning T2 - Proceedings of the WiOpt’04, Cambridge, UK Y1 - 2004 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander ED - Aardal, Karen I. ED - Nemhauser, George ED - Weismantel, R. T1 - Computational Integer Programming and Cutting Planes T2 - Handbooks in Operations Research and Management Science, Vol. 12 Y1 - 2005 SP - 69 EP - 122 PB - North-Holland ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Homfeld, Henning A1 - Huck, Andreas A1 - Martin, Alexander ED - Jacob, R. ED - Müller-Hannemann, Matthias T1 - Locomotive and Wagon Scheduling in Freight Transport T2 - Proceedings of the ATMOS06 Y1 - 2006 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Martin, Alexander A1 - Mehlert, Christian A1 - Stöveken, Peter ED - Günther, H.-O. ED - Mattfeld, D. ED - Suhl, L. T1 - Ein Planungstool zur Schulzeitstaffelung T2 - Supply Chain Management und Logistik Y1 - 2005 SP - 419 EP - 436 ER -