Skip to main content
Log in

Routing in grid graphs by cutting planes

  • Articles
  • Published:
Zeitschrift für Operations Research Aims and scope Submit manuscript

Abstract

In this paper we study the following problem, which we call the weighted routing problem. Let be given a graphG = (V, E) with non-negative edge weightsw e ∈ ℝ+ and letN,N ≥ 1, be a list of node sets. The weighted routing problem consists in finding mutually disjoint edge setsS 1,...,S N such that, for eachk ∈ {1, ...,N}, the subgraph (V(S k),S k) contains an [s, t]-path for alls, t ∈ T k and 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 describe 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 switchbox routing 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Burstein M, Pelavin R (1983) Hierarchical wire routing. IEEE Transactions on Computer-Aided-Design CAD-2:223–234

    Google Scholar 

  2. Cohoon JP, Heck PL (1988) BEAVER: A computational-geometry-based tool for switch-box routing. IEEE Transactions on Computer-Aided-Design CAD-7:684–697

    Google Scholar 

  3. Frank A (1990) Packing paths, circuits, and cuts — a survey. In: Korte B, Lovász L, Prömel HJ, Schrijver A (eds.) Paths, Flows, and VLSI-Layout. Springer-Verlag Berlin Heidelberg 47–100

    Google Scholar 

  4. Garey MR, Johnson DS (1977) The rectilinear Steiner tree problem isN P-complete. SIAM J Appl Math 32:826–834

    Google Scholar 

  5. Grötschel M, Martin A, Weismantel R (1992) Packing Steiner trees: Polyhedral investigations. Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 92-8

  6. Grötschel M, Martin A, Weismantel R (1992) Packing Steiner trees: A cutting plane algorithm and computational results. Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 92-9

  7. Grötschel M, Martin A, Weismantel R (1993) Packing Steiner trees: Separation algorithms. Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 93-2

  8. Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of Computer Computations. Plenum Press New York 85–103

    Google Scholar 

  9. Kramer MR, van Leeuwen J (1984) The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. In: Preparata FP (ed) Advances in Computing Research Vol 2. VLSI theory, Jai Press London, 129–146

    Google Scholar 

  10. Kaufmann M, Mehlhorn K (1990) Routing problems in grid graphs. In: Korte B, Lovász L, Prömel HJ, Schrijver A (eds) Paths, Flows, and VLSI-Layout. Springer-Verlag Berlin Heidelberg 165–184

    Google Scholar 

  11. Luk WK (1985) A greedy switch-box router. Integration 3:129–149

    Google Scholar 

  12. Martin A (1992) Packen von Steinerbäumen: Polyedrische Studien und Anwendung. PhD Thesis Technische Universität Berlin

    Google Scholar 

  13. Okamura H, Seymour PD (1983) Multicommodity flows in graphs. Discrete Applied Mathematics 6:55–62

    Google Scholar 

  14. Sarrafzadeh M (1987) Channel-routing problem in the knock-knee mode isN P-complete. IEEE Transactions on Computer-Aided-Design CAD-6:503–506

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Grötschel, M., Martin, A. & Weismantel, R. Routing in grid graphs by cutting planes. ZOR - Methods and Models of Operations Research 41, 255–275 (1995). https://doi.org/10.1007/BF01432359

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01432359

Keywords

Navigation