<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1055</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-01-15</completedDate>
    <publishedDate>2008-01-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Angebotsplanung im öffentlichen Nahverkehr</title>
    <title language="eng">Service Design in Public Transport</title>
    <abstract language="deu">Die Angebotsplanung im öffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen für die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenhänge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abhängigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.</abstract>
    <identifier type="serial">08-04</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1084</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10555</identifier>
    <enrichment key="SourceTitle">To appear in Heureka '08</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Marika Neumann</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-04</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Preisplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Linienplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierung</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="91B74">Models of real-world systems</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1055/ZR_08_04.pdf</file>
  </doc>
  <doc>
    <id>1061</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-02-20</completedDate>
    <publishedDate>2008-02-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the cardinality constrained matroid polytope</title>
    <abstract language="eng">Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Grötschel's cardinality forcing inequalities, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.</abstract>
    <identifier type="serial">08-08</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1090</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10614</identifier>
    <author>Rüdiger Stephan</author>
    <submitter>unknown unknown</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>08-08</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Matroid-Polytop</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kardinalitätsbeschränkung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Separationsalgorithmus</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Matroid Polytope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cardinality constraints</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Separation algorithm</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="05B35">Matroids, geometric lattices [See also 52B40, 90C27]</collection>
    <collection role="msc" number="52B40">Matroids (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) [See also 05B35, 52Cxx]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="CCCO">CCCO</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1061/MatroidCard_ZIB.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1061/MatroidCard_ZIB.ps</file>
  </doc>
  <doc>
    <id>1052</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-01-04</completedDate>
    <publishedDate>2008-01-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming: a New Approach to Integrate CP and MIP</title>
    <abstract language="eng">This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving. SCIP is available in source code and free for non-commercial use. We demonstrate the usefulness of CIP on two tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.</abstract>
    <identifier type="serial">08-01</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1081</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10520</identifier>
    <enrichment key="SourceTitle">Appeared in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 5th International Conference, CPAIOR 2008 (L. Perron und M. A. Trick, eds.), Lecture Notes in Computer Science, 5015, 2008, pp. 6–20</enrichment>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Timo Berthold</author>
    <author>Thorsten Koch</author>
    <author>Kati Wolter</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-01</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Constraint Programming</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Branch-And-Cut</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierungssoftware</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Chipverifikation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chip verification</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1052/ZR_08_01.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1052/ZR_08_01.ps</file>
  </doc>
  <doc>
    <id>1032</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-11-09</completedDate>
    <publishedDate>2007-11-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Routing and Capacity Optimization for IP networks</title>
    <abstract language="eng">This article describes the main concepts and techniques that have been developed during the last year at ZIB to solve dimensioning and routing optimization problems for IP networks. We discuss the problem of deciding if a given path set corresponds to an unsplittable shortest path routing, the fundamental properties of such path sets, and the computational complexity of some basic network planning problems for this routing type. Then we describe an integer-linear programming approach to solve such problems in practice. This approach has been used successfully in the planning of the German national education and research network for several years.</abstract>
    <identifier type="serial">07-33</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1062</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10323</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2007. J. Kalcsics, S. Nickel (eds.) Springer 2008, pp. 9-16</enrichment>
    <author>Andreas Bley</author>
    <submitter>unknown unknown</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>07-33</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>kombinatorische Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>gemischt-ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>kürzeste-Wege Routing</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Approximationsalgorithmen</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed-integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>shortest path routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>approximation algorithms</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="BMBF-Eibone">BMBF-Eibone</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1032/zib_preprint.pdf</file>
  </doc>
  <doc>
    <id>1028</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-11-01</completedDate>
    <publishedDate>2007-11-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Heuristics of the Branch-Cut-and-Price-Framework SCIP</title>
    <abstract language="eng">In this paper we give an overview of the heuristics which are integrated into the open source branch-cut-and-price-framework SCIP. We briefly describe the fundamental ideas of different categories of heuristics and present some computational results which demonstrate the impact of heuristics on the overall solving process of SCIP.</abstract>
    <identifier type="serial">07-30</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1055</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10280</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2007, Jörg Kalcsics and Stefan Nickel (eds.) 2008, pp. 31-36</enrichment>
    <author>Timo Berthold</author>
    <submitter>unknown unknown</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>07-30</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Primalheuristiken</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Gemischt-Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Branch and Cut</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>SCIP</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>primal heuristics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch and cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>SCIP</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1028/ZR_07_30.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1028/ZR_07_30.ps</file>
  </doc>
  <doc>
    <id>878</id>
    <completedYear>2005</completedYear>
    <publishedYear>2005</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-11-04</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Auctioning Approach to Railway Slot Allocation</title>
    <abstract language="eng">We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.</abstract>
    <identifier type="serial">05-45</identifier>
    <identifier type="opus3-id">878</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8786</identifier>
    <enrichment key="SourceTitle">Appeared in: Competition and Regulation in Network Industries 1 (2006) 163-196</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-8786</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Sascha Lukac</author>
    <author>Kay Mitusch</author>
    <author>Thomas Schlechte</author>
    <author>Sören Schultz</author>
    <author>Andreas Tanner</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-45</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Slot Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Train Dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial Auctions</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/878/ZR-05-45.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/878/ZR-05-45.ps</file>
  </doc>
  <doc>
    <id>5350</id>
    <completedYear/>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2015-01-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Metric Inequalities for Routings on Direct Connections with Application in Line Planning</title>
    <abstract language="eng">We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct   connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows.&#13;
The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with  transfers.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">10.1016/j.disopt.2015.07.004</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-53507</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Optimization 18 (2015) 56-75</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Marika Karbstein</submitter>
    <author>Marika Karbstein</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>transfers</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>direct connection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>metric inequalities</value>
    </subject>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5350/ZR_15_07.pdf</file>
  </doc>
  <doc>
    <id>1009</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-10-02</completedDate>
    <publishedDate>2007-10-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On cardinality constrained cycle and path polytopes</title>
    <abstract language="eng">We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.</abstract>
    <identifier type="serial">07-25</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1024</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10093</identifier>
    <enrichment key="SourceTitle">Appeared in: On cardinality constrained cycle and path polytopes Math. Program. (Ser. A) 123 (2), 2010, 371-394</enrichment>
    <author>Volker Kaibel</author>
    <submitter>unknown unknown</submitter>
    <author>Rüdiger Stephan</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-25</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>path</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cycles</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer characterizations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>facets</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="05C38">Paths and cycles [See also 90B10]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="CCCO">CCCO</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1009/ZR_07_25.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1009/ZR_07_25.ps</file>
  </doc>
  <doc>
    <id>945</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>This work was funded by the Federal Ministry of Economics and Technology (BMWi), project Trassenbörse, grant 19M4031A</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-01-08</completedDate>
    <publishedDate>2007-01-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Models for Railway Track Allocation</title>
    <abstract language="eng">This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.</abstract>
    <identifier type="serial">07-02</identifier>
    <identifier type="opus3-id">945</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9451</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceeding of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2007) (C. Liebchen, R. K. Ahuja und J. A. Mesa, Hg.), Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2007</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-02</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Slot Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Train Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Linear and Integer Programming</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/945/ZR_07_02.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/945/ZR_07_02.ps</file>
  </doc>
  <doc>
    <id>963</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-08-02</completedDate>
    <publishedDate>2007-08-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Railway Track Allocation Problems</title>
    <abstract language="eng">The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.</abstract>
    <identifier type="serial">07-20</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">974</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9631</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2007. J. Kalcsics, S. Nickel (eds.)Springer 2008, pp. 117-122</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-20</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway track allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/963/ZR_07_20.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/963/ZR_07_20.ps</file>
  </doc>
</export-example>
