<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>80</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1992-04-09</completedDate>
    <publishedDate>1992-04-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">SC-92-10</identifier>
    <identifier type="opus3-id">79</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-803</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Programming vol. 63 (1994) pp. 257-279</enrichment>
    <author>Michael Jünger</author>
    <author>Alexander Martin</author>
    <author>Gerhard Reinelt</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-92-10</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>quadratic 0/1 optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>computational complexity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>VLSI-Design</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/80/SC-92-10.pdf</file>
  </doc>
  <doc>
    <id>95</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1993-01-13</completedDate>
    <publishedDate>1993-01-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Some Integer Programs Arising in the Design of Main Frame Computers.</title>
    <abstract language="eng">In this paper we describe and discuss a problem that arises in the (global) design of a main frame computer. The task is to assign certain functional units to a given number of so called multi chip modules or printed circuit boards taking into account many technical constraints and minimizing a complex objective function. We describe the real world problem. A thorough mathematical modelling of all aspects of this problem results in a rather complicated integer program that seems to be hopelessly difficult -- at least for the present state of integer programming technology. We introduce several relaxations of the general model, which are also $NP$-hard, but seem to be more easily accessible. The mathematical relations between the relaxations and the exact formulation of the problem are discussed as well.</abstract>
    <identifier type="serial">SC-92-25</identifier>
    <identifier type="opus3-id">94</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-957</identifier>
    <enrichment key="SourceTitle">Appeared in: Zeitschrift für Operations Research 38 1 (1993) pp. 77-100.</enrichment>
    <author>Carlos E. Ferreira</author>
    <author>Martin Grötschel</author>
    <author>Stefan Kiefl</author>
    <author>Ludwig Krispenz</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-92-25</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/95/SC-92-25.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/95/SC-92-25.pdf</file>
  </doc>
  <doc>
    <id>96</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1992-12-02</completedDate>
    <publishedDate>1992-12-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Routing in Grid Graphs by Cutting Planes.</title>
    <abstract language="eng">{\def\N{{\cal N}} \def\R{\hbox{\rm I\kern-2pt R}} \def\MN{{\rm I\kern-2pt N}} In this paper we study the following problem, which we call the weighted routing problem. Let be given a graph $G=(V,E)$ with non-negative edge weights $w_e\in\R_+$ and integer edge capacities $c_e\in\MN$ and let $\N=\{T_1,\ldots,T_N\}$, $N\ge 1$, be a list of node sets. The weighted routing problem consists in finding edge sets $S_1,\ldots,S_N$ such that, for each $k\in\{1,\ldots,N\}$, the subgraph $(V(S_k),S_k)$ contains an $[s,t]$-path for all $s,t\in T_k$, at most $c_e$ of these edge sets use edge $e$ for each $e\in E$, and such that 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 briefly sketch 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 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.}</abstract>
    <identifier type="serial">SC-92-26</identifier>
    <identifier type="opus3-id">95</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-967</identifier>
    <enrichment key="SourceTitle">Appeared in: Integer Programming and Combinatorial Optimization - IPCO-03. Proc. of a Conf., Erice, April 29 - May 1, 1993. Core, Louvain-la-Neuve, Belgium, 1993, pp. 447-461. An extended version appeared in: ZOR - Mathematical Methods of Operations Research 41 (1995) pp. 255-275</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-92-26</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>routing in VLSI-design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Steiner tree</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Steiner tree packing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cutting plane algorithm</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/96/SC-92-26.pdf</file>
  </doc>
  <doc>
    <id>97</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1992-12-02</completedDate>
    <publishedDate>1992-12-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Packing Steiner Trees: Further Facets.</title>
    <abstract language="eng">In this paper we continue the investigations in [GMW92a] for the \def\sbppo{Steiner tree packing polyhedron} \sbppo. We present several new classes of valid inequalities and give sufficient (and necessary) conditions for these inequalities to be facet-defining. It is intended to incorporate these inequalities into an existing cutting plane algorithm that is applicable to practical problems arising in the design of electronic circuits.</abstract>
    <identifier type="serial">SC-93-01</identifier>
    <identifier type="opus3-id">96</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-975</identifier>
    <identifier type="doi">10.1006/eujc.1996.0004</identifier>
    <enrichment key="SourceTitle">Appeared in: Europ. J. Combinatorics (1996) 17, 39-52</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-93-01</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/97/SC-93-01.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/97/SC-93-01.pdf</file>
  </doc>
  <doc>
    <id>98</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1992-12-02</completedDate>
    <publishedDate>1992-12-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Packing Steiner Trees: Separation Algorithms.</title>
    <abstract language="eng">In this paper we investigate separation problems for classes of inequalities valid for the polytope associated with the Steiner tree packing problem, a problem that arises, e.~g., in VLSI routing. The separation problem for Steiner partition inequalities is ${\cal N}\hskip-2pt{\cal P}$-hard in general. We show that it can be solved in polynomial time for those instances that come up in switchbox routing. Our algorithm uses dynamic programming techniques. These techniques are also applied to the much more complicated separation problem for alternating cycle inequalities. In this case we can compute in polynomial time, given some point $y$, a lower bound for the gap $\alpha-a^Ty$ over all alternating cycle inequalities $a^Tx\ge\alpha$. This gives rise to a very effective separation heuristic. A by-product of our algorithm is the solution of a combinatorial optimization problem that is interesting in its own right: Find a shortest path in a graph where the ``length'' of a path is its usual length minus the length of its longest edge.</abstract>
    <identifier type="serial">SC-93-02</identifier>
    <identifier type="opus3-id">97</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-984</identifier>
    <identifier type="doi">10.1137/S0895480193258716</identifier>
    <enrichment key="SourceTitle">Appeared in: SIAM J. Discrete Math. 9 (1996) pp. 233-257</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-93-02</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/98/SC-93-02.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/98/SC-93-02.pdf</file>
  </doc>
  <doc>
    <id>100</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1993-02-12</completedDate>
    <publishedDate>1993-02-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Facets for the Multiple Knapsack Problem.</title>
    <abstract language="eng">In this paper we consider the multiple knapsack problem which is defined as follows: given a set $N$ of items with weights $f_i$, $i \in N$, a set $M$ of knapsacks with capacities $F_k$, $k \in M$, and a profit function $c_{ik}, i \in N, k \in M$; find an assignment of a subset of the set of items to the set of knapsacks that yields maximum profit (or minimum cost). With every instance of this problem we associate a polyhedron whose vertices are in one to one correspondence to the feasible solutions of the instance. This polytope is the subject of our investigations. In particular, we present several new classes of inequalities and work out necessary and sufficient conditions under which the corresponding inequality defines a facet. Some of these conditions involve only properties of certain knapsack constraints, and hence, apply to the generalized assignment polytope as well. The results presented here serve as the theoretical basis for solving practical problems. The algorithmic side of our study, i.e., separation algorithms, implementation details and computational experience with a branch and cut algorithm are discussed in the companion paper SC 93-07.</abstract>
    <identifier type="serial">SC-93-04</identifier>
    <identifier type="opus3-id">99</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-1007</identifier>
    <enrichment key="SourceTitle">SC 93-04 and SC 93-07 appeared under the title: Solving Multiple Knapsack Problems by Cutting Planes in: SIAM J. Optimization 6 (1996) pp. 858-877</enrichment>
    <author>Carlos E. Ferreira</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-93-04</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/100/SC-93-04.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/100/SC-93-04.pdf</file>
  </doc>
  <doc>
    <id>361</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-07-06</completedDate>
    <publishedDate>1998-07-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Conjunctive Cuts for Integer Programs</title>
    <abstract language="eng">This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view.</abstract>
    <identifier type="serial">SC-98-18</identifier>
    <identifier type="opus3-id">362</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3618</identifier>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-18</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Polyhedral Combinatorics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Separation Algorithm</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/361/SC-98-18.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/361/SC-98-18.pdf</file>
  </doc>
  <doc>
    <id>307</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-08-21</completedDate>
    <publishedDate>1997-08-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Contributions to General Mixed Integer Knapsack Problems</title>
    <abstract language="eng">This paper deals with a general mixed integer knapsack polyhedron for which we introduce and analyze a new family of inequalities. We discuss the value of this family both from a theoretic and a computational point of view.</abstract>
    <identifier type="serial">SC-97-38</identifier>
    <identifier type="opus3-id">308</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3075</identifier>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-38</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/307/SC-97-38.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/307/SC-97-38.pdf</file>
  </doc>
  <doc>
    <id>371</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-11-02</completedDate>
    <publishedDate>1998-11-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A counterexample to an integer analogue of Caratheodorys theorem</title>
    <abstract language="eng">For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed.</abstract>
    <identifier type="serial">SC-98-28</identifier>
    <identifier type="opus3-id">372</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3718</identifier>
    <enrichment key="SourceTitle">Appeared in: Journal für die Reine und Angewandte Mathematik 510, 1999, pp. 179-185</enrichment>
    <author>Winfried Bruns</author>
    <author>Joseph Gubeladze</author>
    <author>Martin Henk</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-28</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integral pointed cones</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Hilbert basis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integral Carathéodory property</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/371/SC-98-28.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/371/SC-98-28.pdf</file>
  </doc>
  <doc>
    <id>488</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1992-07-17</completedDate>
    <publishedDate>1992-07-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Plazieren von Zellen: Theorie und Lösung eines quadratischen 0/1- Optimierungsproblems.</title>
    <abstract language="deu">Die vorliegende Arbeit beschäftigt sich mit dem Plazierungsproblem, welches beim Entwurf elektronischer Schaltungen auftritt. Das Plazierungsproblem modellieren wir als ein quadratisches 0/1 Optimierungsproblem unter linearen Nebenbedingungen und untersuchen das Modell komplexitätstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die Lösung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur Lösung dieser Beispiele wurde ein Prototyp implementiert und mit state of the art"-Plazierungsverfahren verglichen. Schlie\ss lich werden wir uns mit dem Clusteringproblem, das eine Variante des Mehrfachschnitt-Problems darstellt, beschäftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gelöst werden können und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden.</abstract>
    <identifier type="serial">TR-92-03</identifier>
    <identifier type="opus3-id">488</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-4883</identifier>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>TR-92-03</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/488/TR-92-03.pdf</file>
  </doc>
  <doc>
    <id>433</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-12-16</completedDate>
    <publishedDate>1999-12-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cutting Planes in Integer and Mixed Integer Programming</title>
    <abstract language="eng">This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.</abstract>
    <identifier type="serial">SC-99-44</identifier>
    <identifier type="opus3-id">433</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-4339</identifier>
    <enrichment key="SourceTitle">Paper available at URL http://www.core.ucl.ac.be/services/psfiles/dp99/dp9953.pdf Technical Report CORE DP9953, Universite Catholique de Louvain, Louvain-la-Neuve, Belgium, 1999</enrichment>
    <author>Hugues Marchand</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <author>Laurence Wolsey</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-44</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cutting Planes</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/433/SC_99_44.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/433/SC_99_44.pdf</file>
  </doc>
  <doc>
    <id>330</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-12-04</completedDate>
    <publishedDate>1997-12-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Intersection of Knapsack Polyhedra and Extensions</title>
    <abstract language="eng">This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported.</abstract>
    <identifier type="serial">SC-97-61</identifier>
    <identifier type="opus3-id">331</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3300</identifier>
    <enrichment key="SourceTitle">Appeared in: Integer Programming and Combinatorial Optimization (R.E. Bixby, E.A. Boyd, and R.Z. Rios-Mercado, Hsg.), Proceedings of the 6th IPCO Conference, 1998, 243-256</enrichment>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-97-61</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/330/SC-97-61.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/330/SC-97-61.pdf</file>
  </doc>
  <doc>
    <id>8842</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimizing a low-dimensional convex function over a high-dimensional cub</title>
    <parentTitle language="eng">SIAM Journal on Optimization</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="AcceptedDate">2022-11-01</enrichment>
    <author>Christoph Hunkenschröder</author>
    <submitter>Christoph Spiegel</submitter>
    <author>Sebastian Pokutta</author>
    <author>Robert Weismantel</author>
    <collection role="persons" number="pokutta">Pokutta, Sebastian</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="projects" number="Math+EF1-14">Math+EF1-14</collection>
  </doc>
  <doc>
    <id>9491</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimizing a low-dimensional convex function over a high-dimensional cube</title>
    <parentTitle language="eng">SIAM Journal on Optimization</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Christoph Hunkenschröder</author>
    <submitter>Christoph Spiegel</submitter>
    <author>Sebastian Pokutta</author>
    <author>Robert Weismantel</author>
    <collection role="persons" number="pokutta">Pokutta, Sebastian</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>3105</id>
    <completedYear>1996</completedYear>
    <publishedYear>1996</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>101</pageFirst>
    <pageLast>123</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>72</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Packing Steiner trees: Polyhedral Investigations</title>
    <parentTitle language="eng">Mathematical Programming, Series A</parentTitle>
    <identifier type="doi">10.1007/BF02592085</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-786</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3104</id>
    <completedYear>1996</completedYear>
    <publishedYear>1996</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>23</pageFirst>
    <pageLast>35</pageLast>
    <pageNumber/>
    <edition/>
    <issue>11</issue>
    <volume>31</volume>
    <type>article</type>
    <publisherName>Elsevier</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimum Path Packing on Wheels</title>
    <parentTitle language="eng">Computers and Mathematics with Applications</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-1976</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3106</id>
    <completedYear>1996</completedYear>
    <publishedYear>1996</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>125</pageFirst>
    <pageLast>145</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>72</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Packing Steiner trees: a cutting plane algorithm and computational results</title>
    <parentTitle language="eng">Mathematical Programming, Series A</parentTitle>
    <identifier type="doi">10.1007/BF02592086</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-792</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3114</id>
    <completedYear>1997</completedYear>
    <publishedYear>1997</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>265</pageFirst>
    <pageLast>281</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>78</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Steiner tree packing problem in VLSI design</title>
    <parentTitle language="eng">Mathematical Programming</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-1328</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3079</id>
    <completedYear>1993</completedYear>
    <publishedYear>1993</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>447</pageFirst>
    <pageLast>461</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName>Librarian CORE</publisherName>
    <publisherPlace>Louvain-la-Neuve</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Routing in grid graphs by cutting planes</title>
    <parentTitle language="eng">Integer Programming and Combinatorial Optimization. Proceedings of a Conference held at Centro Ettore Majorana, Erice, Italy, April 29 - May 1, 1993</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-967</enrichment>
    <author>Martin Grötschel</author>
    <editor>Giovanni Rinaldi</editor>
    <author>Alexander Martin</author>
    <editor>Laurence Wolsey</editor>
    <author>Robert Weismantel</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>2851</id>
    <completedYear>2000</completedYear>
    <publishedYear>2000</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>425</pageFirst>
    <pageLast>450</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>88</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Set Packing Relaxations of Some Integer Programs</title>
    <parentTitle language="eng">Math. Programming</parentTitle>
    <identifier type="url">http://opus.kobv.de/zib/volltexte/1997/300/</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-2998</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Robert Weismantel</author>
    <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>
  </doc>
  <doc>
    <id>2852</id>
    <completedYear>2001</completedYear>
    <publishedYear>2001</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>11</pageFirst>
    <pageLast>26</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1–3</issue>
    <volume>112</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Discrete Relaxations of Combinatorial Programs</title>
    <parentTitle language="eng">Discrete Appl. Math.</parentTitle>
    <identifier type="url">http://opus.kobv.de/zib/volltexte/1997/324/</identifier>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-3230</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Robert Weismantel</author>
    <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>
  </doc>
  <doc>
    <id>3076</id>
    <completedYear>1993</completedYear>
    <publishedYear>1993</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>77</pageFirst>
    <pageLast>100</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>38</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Some Integer Programs Arising in the Design of Main Frame Computers</title>
    <parentTitle language="eng">ZOR - Methods and Models of Operations Research</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-957</enrichment>
    <author>Carlos Ferreira</author>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <author>Stefan Kiefl</author>
    <author>Ludwig Krispenz</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3096</id>
    <completedYear>1995</completedYear>
    <publishedYear>1995</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>255</pageFirst>
    <pageLast>275</pageLast>
    <pageNumber/>
    <edition/>
    <issue>3</issue>
    <volume>41</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Routing in Grid Graphs by Cutting Planes</title>
    <parentTitle language="eng">ZOR - Mathematical Methods of Operations Research</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-967</enrichment>
    <author>Martin Grötschel</author>
    <author>Alexander Martin</author>
    <author>Robert Weismantel</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
