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 - 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 - THES A1 - Weismantel, Robert T1 - Plazieren von Zellen: Theorie und Lösung eines quadratischen 0/1- Optimierungsproblems. N2 - Die vorliegende Arbeit beschäftigt sich mit dem Plazierungsproblem, welches beim Entwurf elektronischer Schaltungen auftritt. Das Plazierungsproblem modellieren wir als ein quadratisches 0/1 Optimierungsproblem unter linearen Nebenbedingungen und untersuchen das Modell komplexitätstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die Lösung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur Lösung dieser Beispiele wurde ein Prototyp implementiert und mit state of the art"-Plazierungsverfahren verglichen. Schlie\ss lich werden wir uns mit dem Clusteringproblem, das eine Variante des Mehrfachschnitt-Problems darstellt, beschäftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gelöst werden können und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden. T3 - ZIB-Report - TR-92-03 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4883 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 - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cub JF - SIAM Journal on Optimization Y1 - 2022 ER - TY - JOUR A1 - Hunkenschröder, Christoph A1 - Pokutta, Sebastian A1 - Weismantel, Robert T1 - Optimizing a low-dimensional convex function over a high-dimensional cube JF - SIAM Journal on Optimization Y1 - 2022 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 - 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 - 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 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Set Packing Relaxations of Some Integer Programs JF - Math. Programming Y1 - 2000 UR - http://opus.kobv.de/zib/volltexte/1997/300/ VL - 88 SP - 425 EP - 450 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs JF - Discrete Appl. Math. Y1 - 2001 UR - http://opus.kobv.de/zib/volltexte/1997/324/ VL - 112 IS - 1–3 SP - 11 EP - 26 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 - 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: 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 - 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 - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Set Packing Relaxations of Some Integer Programs N2 - This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation. T3 - ZIB-Report - SC-97-30 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2998 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Weismantel, Robert T1 - Discrete Relaxations of Combinatorial Programs N2 - This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code. T3 - ZIB-Report - SC-97-54 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3230 ER -