<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>323</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1997-11-07</completedDate>
    <publishedDate>1997-11-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Discrete Relaxations of Combinatorial Programs</title>
    <abstract language="eng">This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code.</abstract>
    <identifier type="serial">SC-97-54</identifier>
    <identifier type="opus3-id">324</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3230</identifier>
    <enrichment key="SourceTitle">Rev. vers. appeared in: Discrete Appl. Math. 112 (2001) 11-26</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-54</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/323/SC_97_54.orig.Vers.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/323/SC-97-54.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/323/SC-97-54.pdf</file>
  </doc>
</export-example>
