@misc{JuengerMartinReineltetal., author = {J{\"u}nger, Michael and Martin, Alexander and Reinelt, Gerhard and Weismantel, Robert}, title = {Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-803}, number = {SC-92-10}, abstract = {The placement in the layout design of electronic circiuts consists of finding a non- overlapping assignment of rectangular cells to positions on the chip so what wireability is guaranteed and certain technical constraints are met.This problem can be modelled as a quadratic 0/1- program subject to linear constraints. We will present a decomposition approach to the placement problem and give results about \$NP\$-hardness and the existence of \$\varepsilon\$-approximative algorithms for the involved optimization problems. A graphtheoretic formulation of these problems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines. {\bf Keywords:} Quadratic 0/1 optimization, Computational Complexity, VLSI-Design.}, language = {en} } @misc{AscheuerJuengerReinelt, author = {Ascheuer, Norbert and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {A Branch \& Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3391}, number = {SC-97-70}, abstract = {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.}, language = {en} } @article{GroetschelJuengerReinelt1991, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Optimal Control of Plotting and Drilling Machines}, series = {Zeitschrift f{\"u}r Operations Research}, volume = {35}, journal = {Zeitschrift f{\"u}r Operations Research}, number = {1}, pages = {61 -- 84}, year = {1991}, language = {en} } @inproceedings{GroetschelJuengerReinelt1987, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Calculating Exact Ground States of Spin Glasses}, series = {Proceedings of the Heidelberg Colloquium on "Glassy Dynamics", Lecture Notes in Physics 275}, booktitle = {Proceedings of the Heidelberg Colloquium on "Glassy Dynamics", Lecture Notes in Physics 275}, editor = {van Hemmen, J. and Morgenstern, I.}, publisher = {Springer}, pages = {325 -- 353}, year = {1987}, language = {en} } @article{BarahonaGroetschelJuengeretal.1988, author = {Barahona, Francisco and Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {An application of combinatorial optimization to statistical physics and circuit layout design}, series = {Operations Research}, volume = {36}, journal = {Operations Research}, number = {3}, pages = {493 -- 513}, year = {1988}, language = {en} } @article{GroetschelJuengerReinelt1989, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Via Minimization with Pin Preassignments and Layer Preference}, series = {ZAMM - Zeitschrift f{\"u}r Angewandte Mathematik und Mechanik}, volume = {69}, journal = {ZAMM - Zeitschrift f{\"u}r Angewandte Mathematik und Mechanik}, number = {11}, pages = {393 -- 399}, year = {1989}, language = {en} } @article{GroetschelJuengerReinelt1984, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {A Cutting Plane Algorithm for the Linear Ordering Problem}, series = {Operations Research}, volume = {32}, journal = {Operations Research}, number = {6}, pages = {1195 -- 1220}, year = {1984}, language = {en} } @article{GroetschelJuengerReinelt1984, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Optimal triangulation of large real world input-output matrices}, series = {Statistische Hefte}, volume = {25}, journal = {Statistische Hefte}, pages = {261 -- 295}, year = {1984}, language = {en} } @inproceedings{GroetschelJuengerReinelt1985, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {Acyclic subdigraphs and linear orderings}, series = {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}, booktitle = {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}, editor = {Rival, Ivan}, publisher = {D. Reidel Publishing Company}, pages = {217 -- 264}, year = {1985}, language = {en} } @article{GroetschelJuengerReinelt1985, author = {Gr{\"o}tschel, Martin and J{\"u}nger, Michael and Reinelt, Gerhard}, title = {On the acyclic subgraph polytope}, series = {Mathematical Programming}, volume = {33}, journal = {Mathematical Programming}, number = {1}, publisher = {North-Holland}, pages = {28 -- 42}, year = {1985}, language = {en} }