Publications

• Generating Partitions of a Graph into a Fixed Number of Minimum Weight Cuts
  (G. Reinelt, K.M. Wenger)
  To appear in: Discrete Optimization, 2008
   
• Optimizing in graphs with expensive computation of edge weights
  (F. Noé, M. Oswald, G. Reinelt)
  To appear in: Operations Research Proceedings 2007, Selected Papers of OR'2007, Saarbrücken, September 5-7, 2007
   
• Odd minimum cut-sets and b-matchings revisited
  (A.N. Letchford, G. Reinelt, D.O. Theis) (2008)
  To appear in: SIAM J. Discrete Mathematics, 2008
   
• Improved Analysis of an Algorithm for the Coupled Task Problem with UET Jobs
  (J. Békési, G. Galambos, M. Oswald, G. Reinelt)
  Technical Report, 2008
   
• The Virtual Private Network Design Tree Routing Conjecture for Outerplanar Networks
  (F. Fiorini, G. Oriolo, L. Sanità, D.0. Theis)
  Technical report, 2008
   
• Lower Bound for the Online Bin Packing Problem with Restricted Repacking
  (J. Balogh, J. Békési, G. Galambos, G. Reinelt)
  SIAM Journal on Computing, 38, 2008
   
• Spectral coverage of tooth color in the middle- and high-aged patient by Vita Classical and Vita 3D-Master
  (C. Cocking, E. Cervirgen, M. Oswald, P. Rammelsberg, G. Reinelt A. Hassel)
  Technical Report, 2007
   
• Direct Methods with Maximal Lower Bound for Mixed-Integer Optimal Control Problems
  (S. Sager, H.-G. Bock, G. Reinelt)
  Mathematical Programming, DOI10.1007/s10107-007-0185-6, 2007
   
• On convex sets associated with permutations, path-metrics and cuts
  (A. Letchford, H. Seitz, G. Reinelt, D. O. Theis)
  Technical report, 2007
   
• Computing Finest Mincut Partitions of a Graph and Application to Routing Problems
  (G. Reinelt, D.O. Theis, K.M. Wenger)
  Discrete Applied Mathematics, R. Eglese, A. Letchford, M. Wright and A. Clark (eds): Special Issue on the Combinatorial Optimization Conference(CO'04), Lancaster (UK), March, 28-31 2004, Elsevier, 156(2008), 385-396
   
• On the General Routing polytope
  (G. Reinelt, D. O. Theis)
  Discrete Applied Mathematics, R. Eglese, A. Letchford, M. Wright and A. Clark (eds): Special Issue on the Combinatorial Optimization Conference(CO'04), Lancaster (UK), March, 28-31 2004, Elsevier, 156(2008), 368-384
   
• Compression of Digital Road Networks
  (J. Suh, S. Jung, M. Pfeifle, K.T. Vo, M. Oswald, G. Reinelt)
  In: Advances in Spatial and Temporal Databases, SSTD2007, Proceedings 10th International Symposium on Spatial and Temporary Databases, Boston (USA), July 16-18, 2007, LNCS 4605, Springer, 2007, 423-440
   
• On the Graphical Relaxation of the Symmetric Traveling Salesman Polytope
  (M. Oswald, G. Reinelt, D.O. Theis)
  Mathematical Programming, 110, 2007, 175-193
   
• Numerical Methods for Optimal Control Binary Control Functions Applied to a Lotka-Volterra Type Problem
  (S. Sager, H.G. Bock, M. Diehl, G. Reinelt, J.P. Schlöder)
  In: A. Seeger (ed.): Recent Advances in Optimization. Proceedings of the 12th French-German-Spanish Conference on Optimization held in Avignon (France), September 20-24, 2004, Lectures Notes in Economics and Mathematical Systems 563, Springer, 2006, 269-289
   
• Solutions to city bus scheduling problems
  C. Surapholchai, G. Reinelt, H.-G. Bock},
  In: Lenbury, Yongwimon and Van Sanh, Nguyen (eds): Contributions in Mathematics and Applications, East-West Journal of Mathematics, 2005, 129-142
   
• Computing Best Transition Pathways in High-Dimensional Dynamical Systems
  (F. Noé, M. Oswald, G. Reinelt, J.C. Smith and S. Fischer)
  SIAM Multiscale Modeling and Simulation,Vol. 5(2), 2006, 393-419
   
• Locating Health Facilities in Nouna District, Burkina Faso
  C. Cocking, S. Fleßa, G. Reinelt
  In: H.-D. Haasis, H. Kopfer, J. Schönberger (eds.) Operations Research Proceedings 2005: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Bremen, September 7-9, 2005, Springer, 2006, 431-436
   
• Maximally Violated Mod-p Cuts for the Capacitated Vehicle Routing Problem
  (G. Reinelt, K.M. Wenger)
  INFORMS, Journal on Computing 18, 2006, 466-479
   
• A Tabu Search Algorithm for the Min-Max k-Chinese Postman Problem
  (D. Ahr, G. Reinelt) 
  Computers and Operations Research 33, 2006, 3403-3422
   
• Discovering functional gene expression patterns in the metabolic network of Escherichia coli with wavelets transforms
  (R. Konig, G. Schramm, M. Oswald, H. Seitz, S. Sager, M. Zapatka, G. Reinelt, R. Eils)
  BMC Bioinformatics 2006 7:119, 2006
   
• Numerical Methods for Optimal Control Binary Control Functions Applied to a Lotka-Volterra Type Fishing Problem
  (S. Sager, H.-G. Bock, M. Diehl, G. Reinelt, J.P. Schlöder)
  In: A. Seeger (ed.): Recent Advances in Optimization. Proc. of the 12th French-German-Spanish Conference on Optimization held in Avignon (France), September 20-24, 2004,
  Lectures Notes in Economics and Mathematical Systems 353, Springer, 2006, 269-289
   
• BoxSteps Methods for Crew Pairing Problems
  (T.V. Hoai, G. Reinelt, H.-G. Bock) 
  Optimization and Engineering 7, 2006, 33-46
   
• A note on the Undirected Rural Postman Problem polytope
  (D.O. Theis, G. Reinelt)
  Mathematical Programming 106, 2006, 447-452
   
• Transformation of Facets of the General Routing Problem Polytope
  (D.O. Theis, G. Reinelt)
  SIAM Journal on Optimization 16, 2005, 220-234
   
• Not every GTSP facet induces an STSP facet
  (M. Oswald, D.O. Theis, G. Reinelt)
  In: M. Jünger, V. Kaibel (eds): Proc. of 11th Conference on Integer Programming & Combinatorial Optimization (IPCO XI), Berlin, June 08-10 2005
  Lecture Notes in Computer Science 3509, Springer, 2005, 468-482
   
• Polyhedra and algorithms for the General Routing Problem
  (D.O. Theis)
  PhD Thesis, Universität Heidelberg, 2005
   
• Solving Large Scale Crew Prairing Problems
  (V.H. Tran) 
  PhD Thesis, Universität Heidelberg, 2005 
   
• Contributions to Multiple Postmen Problems
  (D. Ahr) 
  PhD Thesis, Universität Heidelberg, 2004 
   
• Advanced Techniques in the Column Generation for Crew Pairing Problems
  (V.H. Tran, G. Reinelt, H.-G. Bock) 
  In: H.-G. Bock, E. Kostina, X.P. Hoang, R. Rannacher (eds.): Proc. of International Conference on High Performance Scientific Computing: Modelling, Simulation and Optimization of Complex Processes, Hanoi, Vietnam, March 10-14 2003,
  Springer, 2004, 203-214
   
• Computing Exact Ground States of Hard Ising Spin Glass Problems by Branch-and-Cut
  (F. Liers, M. Jünger, G. Reinelt, G. Rinaldi) 
  In: A. Hartmann, H. Rieger (eds.): New Optimization Algorithms in Physics,
  Wiley-VCH, 2004, 47-70
   
• A Faster Exact Separation Algorithm for Blossom Inequalities
  (A.N. Letchford, D.O. Theis, G. Reinelt) 
  In: D. Bienstock, G. Nemhauser (eds.): Proc. of Integer Programming & Combinatorial Optimization X (IPCO X), New York, June 7-11 2004,
  Lecture Notes in Computer Science 3064, Springer, 2004, 196-205
   
• A rather long note on the Padberg-Rao algorithm for capacitated blossom separation
  (A.N. Letchford, D.O. Theis, G. Reinelt) 
  Technical Report, 2004: PS, PDF
   
• An Exact Algorithm for Scheduling Identical Coupled Tasks
  (D. Ahr, J. Békési, G. Galambos, M. Oswald, G. Reinelt) 
  Mathematical Methods of Operations Research 59(2), 2004, 193-203
   
• Computing Optimal Consecutive Ones Matrices
  (M.Oswald, G.Reinelt) 
  In: M. Grötschel (ed.): The Sharpest Cut, The Impact of Manfred Padberg and His Work, MPS/SIAM, Series on Optimization, 2004, 173-184
   
• Combinatorial Optimization and Integer Programming
  (M.Jünger, G.Reinelt) 
  In: 6.5: Optimization and Operations Research (U. Derigs, ed.), in: Encyclopedia of Life Support Systems EOLSS, Eolss Publishers, 2004, 321-327
   
• Small Instance Relaxations for the Traveling Salesman Problem
  (K.M. Wenger, G. Reinelt) 
  In: D. Ahr, R. Fahrion, M. Oswald, G. Reinelt (eds.): Selected Papers of the International Conference on Operations Research 2003 (OR'03), Heidelberg, September 3-5 2003,
  Springer, 2004, 371-378
   
• A Parallel Approach to the Pricing Step in Crew Scheduling Problems
  (V.H. Tran, G. Reinelt, H.-G. Bock) 
  In: D. Ahr, R. Fahrion, M. Oswald, G. Reinelt (eds.): Selected Papers of the International Conference on Operations Research 2003 (OR'03), Heidelberg, September 3-5 2003,
  Springer, 2004, 165-172
   
• Selected Papers of the International Conference on Operations Research 2003 (OR'03), Heidelberg, September 3-5 2003
  (D. Ahr, R. Fahrion, M. Oswald, G. Reinelt (eds.)) 
  Springer, 2004
   
• The Weighted Consecutive Ones Problem for a Fixed Number of Rows or Columns
  (M. Oswald, G. Reinelt) 
  Operations Research Letters 31, 2003, 350-356
   
• Combinatorial Optimization - Eureka, You Shrink!, Papers Dedicated to Jack Edmonds, 5th International Workshop, Aussois, France, March 5-9 2001, Revised Papers
  (M. Jünger, G. Reinelt, G. Rinaldi (eds.))
  Lecture Notes in Computer Science 2570, Springer, 2003
   
• Constructing New Facets of the Consecutive Ones Polytope
  (M. Oswald, G. Reinelt) 
  In: M. Jünger, G. Reinelt, G. Rinaldi (eds.): Combinatorial Optimization - Eureka, You Shrink!, Papers Dedicated to Jack Edmonds,5th International Workshop, Aussois, France, March 5-9 2001, Revised Papers,
  Lecture Notes in Computer Science 2570, Springer, 2003, 147-157
   
• Weighted Consecutive Ones Problems
  (M. Oswald) 
  PhD Thesis, Universität Heidelberg, 2003 
   
• Generic Cut Generation Methods for Routing Problems
  (K.M. Wenger) 
  PhD Thesis, Universität Heidelberg, 2003, Shaker Verlag 2003
   
• Generalization of Clauses Containing Cross Connection
  (C. Surapholchai, B. Kijsirikul, M. E. Hall)
  In: Proc. International Conference on Computational Mathematics and Modeling, Special Volume of East-West Journal of Mathematics, 2002, 165-147
   
• New Heuristics and Lower Bounds for the Min-Max k-Chinese Postman Problem
  (D. Ahr, G. Reinelt)
  In: R. Möhring, R. Raman (eds.): Algorithms - ESA 2002: Proc. 10th Annual European Symposium, Rome, Italy, September 17-21 2002,
  Lecture Notes in Computer Science 2461, Springer, 2002, 64-74
   
• A New Approach to Cactus Construction Applied to TSP Support Graphs 
  (K.M. Wenger)
  In: W.J. Cook and A.S. Schulz (eds.): Integer Programming and Combinatorial Optimization, Proc. 9th International IPCO Conference, Cambridge, USA, May 27-29 2002,
  Lecture Notes in Computer Science 2337, Springer, 2002, 109-126
   
• Some Relations Between Consecutive Ones and Betweenness Polytopes
  (M. Oswald, G. Reinelt) 
  In: P. Chamoni, R. Leisten, A. Martin, J. Minnemann, H. Stadler (eds.): Operations Research Proc. 2001. Selected Papers of the International Conference on Operations Research 2001 (OR'01), Duisburg, September 3-5 2001, Springer, 2002, 277-283
   
• Algorithmic: Aspects of Using Small Instance Relaxations in Parallel Branch-and-Cut.
  (T. Christof, G. Reinelt) 
  Algorithmica 30, 2001, 597-629
   
• Decomposition and Parallelization Techniques for Enumerating the Facets of Combinatorial Polytopes
  (T. Christof, G. Reinelt)
  International Journal of Computational Geometry & Applications 11, 2001, 423-437
   
• Das General Routing Problem mit binären Variablen
  (Dirk Oliver Theis)
  Diploma Thesis, Institut für Informatik, Universität Heidelberg, 2001
   
• Modeling Cash Flows in Bond Structures
  (B. Adams, J. Cadet, L. Du, X. Du, C.Surapholchai, X.Wang)
  In: Proc. Industrial Mathematics Modeling Workshop for Graduate Students, Technical Report CRSC-TR00-24, North Carolina State University, 2000
   
• Polyhedral Aspects of the Consecutive Ones Problem
  (M. Oswald, G. Reinelt)
  In: D.-Z. Du, P. Eades, V. Estivill-Castro et al. (eds.): Computing and Combinatorics, Proc.of the 6th Annual International Conference on Computing and Combinatorics, (COCOON 2000), Sydney, Australia, July 26-28 2000,
  Lecture Notes in Computer Science 1858, Springer, 2000, 373-382 
   
• A Branch-and-Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints 
  (N. Ascheuer, M. Jünger, G. Reinelt) 
  Computational Optimization and Applications 17, 2000, 61-84 
   
• Polyhedral Aspects of the Consecutive Ones Problem
  (M. Oswald, G. Reinelt) 
  In: K.Inderfurth, G. Schwödiauer, W. Domschke, F. Juhnke, P. Kleinschmidt, G. Wäscher (eds.): Selected Papers of the Symposium on Operations Research, (SOR'99), September 1-3 1999, Magdeburg,
  Springer, 2000, 81-85
   
• Kaktus-Repräsentationen der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP
  (K. M. Wenger)
  Diploma Thesis, Institut für Informatik, Universität Heidelberg, 2001
   
• Consecutive Ones and a Betweenness Problem in Computational Biology 
  (T. Christof, M. Oswald, G. Reinelt)
  In: R.E. Bixby, E.A. Boyd, R.Z. Rios-Mercado (eds.): Proc. Sixth Conference on Integer Programming and Combinatorial Optimization, (IPCO VI), Houston, USA
  Lecture Notes in Computer Science 1412, Springer, 1998, 213-228
   
• Low-Dimensional 0/1-Polytopes and Branch-and-Cut in Combinatorial Optimization
  (T. Christof) 
  Dissertation, Uni Heidelberg, 1997, Shaker Verlag 
   
• The Traveling Salesman Problem: A Bibliography 
  (M. Jünger, G. Reinelt, G. Rinaldi) 
  In: M. Dell'Amico, F. Maffioli, S. Martello (eds.): Annotated Bibliography in Combinatorial Optimization, Wiley, 1997, 199-221 
   
• Low-dimensional Linear Ordering Polytopes 
  (T. Christof, G. Reinelt) 
  Working Paper, Uni Heidelberg, 1997 
   
• Allgemeine Feedback Vertex Set Probleme 
  (M. Funke) 
  Dissertation, Uni Heidelberg, 1997, Herbert Utz Verlag  
   
• A Branch-and-Cut Approach to Physical Mapping of Chromosomes by Unique End-probes 
  (T. Christof, M. Jünger, J. Kececioglu, P. Mutzel, G. Reinelt) 
  Journal of Computational Biology 4(4), 1997, 433-447
   
• A Branch-and-Cut Approach to Physical Mapping with End-probes 
  (T. Christof, M. Jünger, J. Kececioglu, P. Mutzel, G. Reinelt) 
  In: Proc. of the First Annual Conference on Computational Molecular Biology RECOMB, 1997, 84-92 
   
• A Polyhedral Approach to the Feedback Vertex Set 
  (M. Funke, G. Reinelt) 
  In: William H. Cunningham, S. Thomas McCormick, Maurice Queyranne (eds.): Proc. 5th International Conference on Integer Programming and Combinatorial Optimization, (IPCO), Vancouver, British Columbia, Canada, June 3-5 1996,
  Lecture Notes in Computer Science 1084, Springer, 1996, 445-459
   
• Exact Ground States of Two-Dimensional +-J Ising Spin Glasses 
  (C. De Simone, M. Diehl, M. Jünger, P. Mutzel, G. Reinelt, G. Rinaldi) 
  Journal of Statistical Physics 84, 1996, 1363-1371 
   
• Combinatorial Optimization and Small Polytopes 
  (T. Christof, G. Reinelt) 
  Top (Spanish Statistical and Operations Research Society) 4, 1996, 1-64 
   
• Exact Ground States of Ising Spin Glasses: New Experimental Results with a Branch and Cut Algorithm 
  (C. De Simone, M. Diehl, M. Jünger, P. Mutzel, G. Reinelt, G. Rinaldi) 
  Journal of Statistical Physics 80, 1995, 487-496 
   
• The Traveling Salesman Problem 
  (M.Jünger, G.Reinelt, G.Rinaldi) 
  In: M.Ball, T.Magnanti, C.L.Monma, G.Nemhauser (eds.), Handbooks in Operations Research and Management Sciences, Vol.7: Network Models, North Holland, 1995, 225-330 
   
• Parallel Cutting Plane Generation for the TSP 
  (T. Christof, G. Reinelt) 
  in: P. Fritzson, L. Finmo (eds.), Parallel Programming and Applications, 1995, IOS Press, 163-169 
   
• Kombinatorische Optimierung und VLSI-Entwurf 
  (G. Reinelt) 
  in: A.Bachem, M.Jünger, R.Schrader (eds.), Mathematik in der Praxis, Springer, 1995, 237-260 
   
• Practical Problem Solving with Cutting Plane Algorithms in Combinatorial Optimization 
  (M. Jünger, G. Reinelt, S. Thienel) 
  In: William Cook, Laszlo Lovasz, Paul Seymour (eds), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 20, 1995, 111-152
   
• The Traveling Salesman: Computational Solutions for TSP Applications 
  (G.Reinelt) 
  Lecture Notes in Computer Science 840, Springer, 1994
  Online Publication, Info
   
• Quadratic 0/1-Optimization and a Decomposition Approach for the Placement of Electronic Circuits 
  (M. Jünger, A. Martin, G. Reinelt, R. Weismantel) 
  Mathematical Programming 63, 1994, 257-280 
   
• Provably Good Solutions for the Traveling Salesman Problem 
  (M. Jünger, G. Reinelt, S. Thienel) 
  Zeitschrift für Operations Research 40, 1994, 183-217 
   
• Verfahrwegoptimierung bei Maskenerstellung und Produktion von Leiterplatten 
  (M. Jünger, G. Reinelt) 
  DGOR-Praxisbericht, 1994 
   
• A Note on Small Linear Ordering Polytopes 
  (G. Reinelt) 
  Discrete & Computational Geometry 10, 1993, 67-78 
   
• Schnittebenenverfahren in der Kombinatorischen Optimierung 
  (M. Jünger, G. Reinelt) 
  GAMM Mitteilungen, 15, 1992, 120-134 
   
• Fast Heuristics for Large Geometric Traveling Salesman Problems 
  (G. Reinelt) 
  ORSA Journal on Computing 2, 1992, 206-217 
   
• Optimal Control of Plotting and Drilling Machines: A Case Study 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  Zeitschrift für Operations Research - Methods and Models of Operations Research 35, 1991, 61-84 
   
• Computing the Convex Hull in the Euclidean Plane in Linear Expected Time. 
  (K.H. Borgwardt, N. Gaffke, M. Jünger, G. Reinelt) 
  In: P. Gritzmann, B. Sturmfels: The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 4, 1991, 91-107 
   
• Computing Correct Delaunay Triangulations. 
  (M. Jünger, G. Reinelt, D. Zepf) 
  Computing 47, 1991, 43-49 
   
• TSPLIB - A Traveling Salesman Problem Library. 
  (G. Reinelt) 
  ORSA Journal on Computing 3, 1991, 376-384 
   
• A Complete Description of the Traveling Salesman Polytope on 8 Nodes 
  (T. Christof, M. Jünger, G. Reinelt) 
  Operations Research Letters 10, 1991, 497-500 
   
• Simultaneous Placement in the Sea Of Gates Layout Style 
  (M. Jünger, A. Martin, G. Reinelt, R. Weismantel) 
  Methods of Operations Research 62, 1990, 273-275 
   
• Polyedrische Methoden zur Lösung großer kombinatorischer Optimierungsprobleme 
  (G. Reinelt) 
  In: Andreas Reuter (ed.): GI - 20. Jahrestagung II, Informatik auf dem Weg zum Anwender, Stuttgart, 8.-12. Oktober 1990, Proc.},
  Informatik-Fachberichte 258, Springer, 1990 
   
• Experiments in Quadratic 0-1 Programming 
  (F. Barahona, M. Jünger, G. Reinelt) 
  Mathematical Programming 44, 1989, 127-138 
   
• Via Minimization with Pin Preassignments and Layer Preference 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  Zeitschrift fürr Angewandte Mathematik und Mechanik 69, 1989, 393-399 
   
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design 
  (F. Barahona, M. Grötschel, M. Jünger, G. Reinelt) 
  Operations Research 36, 1988, 493-513. 
   
• Calculating Exact Ground States of Spin Glasses: A Polyhedral Approach 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  in: J.L.van Hemmen, I.Morgenstern (eds.): Proc. of the Heidelberg Colloquium on "Glassy Dynamics", Lecture Notes in Physics 275, Springer, 1987, 325-353 
   
• Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra 
  (R. Euler, M. Jünger, G. Reinelt) 
  Mathematics of Operations Research 12, 1987, 451-462 
   
• Acyclic Subdigraphs and Linear Orderings: Polytopes, Facets and a Cutting Plane Algorithm 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  In: I. Rival (ed.): Graphs and Order. The Role of Graphs in the Theory of Ordered Sets and its Applications, D. Reidel, 1985, 218-264
   
• On the Acyclic Subgraph Polytope 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  Mathematical Programming 33, 1985, 28-42 
   
• Facets of the Linear Ordering Polytope 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  Mathematical Programming 33, 1985, 43-60 
   
• The Linear Ordering Problem: Algorithms and Applications 
  (G. Reinelt) 
  Research and Expositions in Mathematics 8
  Heldermann Verlag, 1985
   
• On Partitioning the Edges of Graphs into Connected Subgraphs 
  (M. Jünger, W.R. Pulleyblank, G. Reinelt) 
  Journal of Graph Theory 9, 1985, 539-549 
   
• A Cutting Plane Algorithm for the Linear Ordering Problem 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  Operations Research 32, 1984, 1195-1220 
   
• Optimal Triangulation of Large Real World Input-Output Matrices 
  (M. Grötschel, M. Jünger, G. Reinelt) 
  Statistische Hefte 25, 1984, 261-295