@misc{HenkWeismantel1997, author = {Henk, Martin and Weismantel, Robert}, title = {Test sets of the knapsack problem and simultaneous diophantine approximation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2825}, number = {SC-97-13}, year = {1997}, abstract = {This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem.}, language = {en} } @misc{ThomasWeismantel1995, author = {Thomas, Rekha R. and Weismantel, Robert}, title = {Test sets and inequalities for integer programs: extended abstract}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2021}, number = {SC-95-36}, year = {1995}, abstract = {This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix \$A\$ transforms to the state polytope as we pass from linear programs that have \$A\$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs.}, language = {en} } @misc{HelmbergRendlWeismantel1995, author = {Helmberg, Christoph and Rendl, Franz and Weismantel, Robert}, title = {Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2031}, number = {SC-95-37}, year = {1995}, abstract = {We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.}, language = {en} } @misc{HelmbergWeismantel1997, author = {Helmberg, Christoph and Weismantel, Robert}, title = {Cutting Plane Algorithms for Semidefinite Relaxations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2719}, number = {SC-97-02}, year = {1997}, abstract = {We investigate the potential and limits of interior point based cutting plane algorithms for semidefinite relaxations on basis of implementations for max-cut and quadratic 0-1 knapsack problems. Since the latter has not been described before we present the algorithm in detail and include numerical results.}, language = {en} } @misc{HenkWeismantel1997, author = {Henk, Martin and Weismantel, Robert}, title = {Hilbert bases of cones related to simultaneous Diophantine approximations and linear Diophantine equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2989}, number = {SC-97-29}, year = {1997}, abstract = {This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem.}, language = {en} } @misc{HelmbergRendlWeismantel1996, author = {Helmberg, Christoph and Rendl, Franz and Weismantel, Robert}, title = {A Semidefinite Programming Approach to the Quadratic Knapsack Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2211}, number = {SC-96-10}, year = {1996}, abstract = {We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.}, language = {en} } @misc{HenkWeismantel1996, author = {Henk, Martin and Weismantel, Robert}, title = {On Hilbert bases of polyhedral cones}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2230}, number = {SC-96-12}, year = {1996}, abstract = {For a polyhedral cone \$C=\$ pos \$\{a^1,\dots,a^m\}\subset R^d\$, \$a^i\in Z^d\$, a subset of integral vectors \$H(C)\subset C \cap Z^d\$ is called a Hilbert basis of \$C\$ iff (i) each element of \$C\cap Z^d\$ can be written as a non-negative integer combination of elements of \$H(C)\$ and (ii) \$H(C)\$ has minimal cardinality with respect to all subsets of \$C \cap Z^d\$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates.}, language = {en} } @misc{GroetschelMartinWeismantel1995, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {Optimum Path Packing on Wheels: The Consecutive Case}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1976}, number = {SC-95-31}, year = {1995}, abstract = {We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.~e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.}, language = {en} } @misc{Weismantel1994, author = {Weismantel, Robert}, title = {On the 0/1 Knapsack Polytope.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1312}, number = {SC-94-01}, year = {1994}, abstract = {{\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Given a set \$N\$ of items and a capacity \$b \in \N\$, and let \$N_j\$ be the set of items with weight \$j\$, \$1 \leq j \leq b\$. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality \$\$\sum_{j=1}^b \sum_{i \in N_j} jx_i \leq b.\$\$ In this paper we first present a complete linear description of the 0/1 knapsack polytope for two special cases: (a) \$N_j = \emptyset\$ for all \$1 < j \leq \lfloor {b \over 2} \rfloor\$ and (b) \$N_j = \emptyset\$ for all \$1 < j \leq \lfloor {b \over 3} \rfloor\$ and \$N_j = \emptyset\$ for all \$j \geq \lfloor {b \over 2} \rfloor + 1\$. It turns out that the inequalities that are needed for the complete description of these special polytopes are derived by means of some ``reduction principle''. This principle is then generalized to yield valid and in many cases facet defining inequalities for the general 0/1 knapsack polytope. The separation problem for this class of inequalities can be solved in pseudo polynomial time via dynamic programming techniques.}}, language = {en} } @misc{GroetschelMartinWeismantel1994, author = {Gr{\"o}tschel, Martin and Martin, Alexander and Weismantel, Robert}, title = {The Steiner Tree Packing Problem in VLSI-Design.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1328}, number = {SC-94-02}, year = {1994}, abstract = {In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.}, language = {en} }