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 - Ascheuer, Norbert A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints N2 - In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time. T3 - ZIB-Report - SC-97-70 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3391 ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - Optimal Control of Plotting and Drilling Machines JF - Zeitschrift für Operations Research Y1 - 1991 VL - 35 IS - 1 SP - 61 EP - 84 ER - TY - CHAP A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard ED - van Hemmen, J. ED - Morgenstern, I. T1 - Calculating Exact Ground States of Spin Glasses T2 - Proceedings of the Heidelberg Colloquium on “Glassy Dynamics”, Lecture Notes in Physics 275 Y1 - 1987 SP - 325 EP - 353 PB - Springer ER - TY - JOUR A1 - Barahona, Francisco A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - An application of combinatorial optimization to statistical physics and circuit layout design JF - Operations Research Y1 - 1988 VL - 36 IS - 3 SP - 493 EP - 513 ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - Via Minimization with Pin Preassignments and Layer Preference JF - ZAMM – Zeitschrift für Angewandte Mathematik und Mechanik Y1 - 1989 VL - 69 IS - 11 SP - 393 EP - 399 ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - A Cutting Plane Algorithm for the Linear Ordering Problem JF - Operations Research Y1 - 1984 VL - 32 IS - 6 SP - 1195 EP - 1220 ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - Optimal triangulation of large real world input-output matrices JF - Statistische Hefte Y1 - 1984 VL - 25 SP - 261 EP - 295 ER - TY - CHAP A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard ED - Rival, Ivan T1 - Acyclic subdigraphs and linear orderings T2 - Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and its Applications, Proceedings of NATO ASI, Ser. C 147, Banff/Canada 1984 Y1 - 1985 SP - 217 EP - 264 PB - D. Reidel Publishing Company ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - On the acyclic subgraph polytope JF - Mathematical Programming Y1 - 1985 VL - 33 IS - 1 SP - 28 EP - 42 PB - North-Holland ER - TY - JOUR A1 - Grötschel, Martin A1 - Jünger, Michael A1 - Reinelt, Gerhard T1 - Facets of the linear ordering polytope JF - Mathematical Programming Y1 - 1985 VL - 33 IS - 1 SP - 43 EP - 60 PB - North-Holland ER - TY - CHAP A1 - Hildenbrandt, Achim A1 - Reinelt, Gerhard A1 - Heismann, Olga T1 - Integer Programming Models for the Target Visitation Problem T2 - Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013 N2 - The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinato- rial optimization problems: the traveling salesman and the linear ordering problem. In this paper we present several possible IP-Models for this problem and compared them to their usability for branch-and-cut approaches. Y1 - 2013 SP - 569 EP - 572 ER - TY - GEN A1 - Heismann, Olga A1 - Hildenbrandt, Achim A1 - Silvestri, Francesco A1 - Reinelt, Gerhard A1 - Borndörfer, Ralf T1 - HUHFA: A Framework for Facet Classification N2 - Usually complete linear descriptions of polytopes consist of an enormous number of facet-defining inequalities already for very small problem sizes. In this paper, we describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of a polytope. We propose an algorithm for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem. T3 - ZIB-Report - 13-45 KW - facet classification KW - symmetry KW - polyhedral structure Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42230 SN - 1438-0064 ER -