TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - Test sets of the knapsack problem and simultaneous diophantine approximation N2 - 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. T3 - ZIB-Report - SC-97-13 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2825 ER - TY - GEN A1 - Thomas, Rekha R. A1 - Weismantel, Robert T1 - Test sets and inequalities for integer programs: extended abstract N2 - 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. T3 - ZIB-Report - SC-95-36 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2021 ER - TY - GEN A1 - Helmberg, Christoph A1 - Rendl, Franz A1 - Weismantel, Robert T1 - Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract N2 - 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. T3 - ZIB-Report - SC-95-37 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2031 ER - TY - GEN A1 - Helmberg, Christoph A1 - Weismantel, Robert T1 - Cutting Plane Algorithms for Semidefinite Relaxations N2 - 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. T3 - ZIB-Report - SC-97-02 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2719 ER - TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - Hilbert bases of cones related to simultaneous Diophantine approximations and linear Diophantine equations N2 - 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. T3 - ZIB-Report - SC-97-29 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2989 ER - TY - GEN A1 - Helmberg, Christoph A1 - Rendl, Franz A1 - Weismantel, Robert T1 - A Semidefinite Programming Approach to the Quadratic Knapsack Problem N2 - 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. T3 - ZIB-Report - SC-96-10 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2211 ER - TY - GEN A1 - Henk, Martin A1 - Weismantel, Robert T1 - On Hilbert bases of polyhedral cones N2 - 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. T3 - ZIB-Report - SC-96-12 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2230 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Consecutive Case N2 - 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. T3 - ZIB-Report - SC-95-31 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1976 ER - TY - GEN A1 - Weismantel, Robert T1 - On the 0/1 Knapsack Polytope. N2 - {\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.} T3 - ZIB-Report - SC-94-01 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1312 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - The Steiner Tree Packing Problem in VLSI-Design. N2 - 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. T3 - ZIB-Report - SC-94-02 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1328 ER - TY - GEN A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Packing Paths and Steiner Trees: Routing of Electronic Circuits. N2 - One of the challenging problems in the design of electronic circuits is the so-called routing problem. Roughly speaking, the task is to connect so-called terminal sets via wires on a predefined area. In addition, certain design rules are to be taken into account and an objective function such as the wiring length must be minimized. The routing problem in general is too complex to be solved in one step. Depending on the user's choice of decomposing the chip design problem into a hierarchy of stages, on the underlying technology, and on the given design rules, various subproblems arise. We discuss several variants of practically relevant routing problems and give a short overview on the underlying technologies and design rules. Many of the routing problems that come up this way can be formulated as the problem of packing so-called Steiner trees in certain graphs. We consider the Steiner tree packing problem from a polyhedral point of view and present three possibilities to define an appropriate polyhedron. Weighing their pros and cons we decide for one of these polytopes and sketch some of our investigations. T3 - ZIB-Report - SC-93-15 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1113 ER - TY - GEN A1 - Grötschel, Martin A1 - Martin, Alexander A1 - Weismantel, Robert T1 - Optimum Path Packing on Wheels: The Noncrossing Case. N2 - We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that no two terminal pairs cross, 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. T3 - ZIB-Report - SC-93-26 Y1 - 1993 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1225 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Souza, Cid C. de A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - Formulations and Valid Inequalities for the Node Capacitated Graph Partitioning Problem. N2 - We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change. T3 - ZIB-Report - SC-94-16 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1450 ER - TY - GEN A1 - Ferreira, Carlos E. A1 - Martin, Alexander A1 - Souza, Cid C. de A1 - Weismantel, Robert A1 - Wolsey, Laurence T1 - The Node Capacitated Graph Partitioning Problem: A Computational Study. N2 - In this paper we consider the problem of $k$-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. T3 - ZIB-Report - SC-94-17 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1469 ER - TY - GEN A1 - Weismantel, Robert T1 - Hilbert Bases and the Facets of Special Knapsack Polytopes. N2 - {\def\N{{\mbox{{\rm I\kern-0.22emN}}}} Let a set $N$ of items, a capacity $F \in \N$ and weights $a_i \in \N$, $i \in N$ be given. The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy the inequality $$\sum_{i \in N} a_i x_i \leq F.$$ In this paper we present a linear description of the 0/1 knapsack polytope for the special case where $a_i \in \{\mu,\lambda\}$ for all items $i \in N$ and $1 \leq \mu < \lambda \leq b$ are two natural numbers. The inequalities needed for this description involve elements of the Hilbert basis of a certain cone. The principle of generating inequalities based on elements of a Hilbert basis suggests further extensions.} T3 - ZIB-Report - SC-94-19 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1475 ER - TY - GEN A1 - Schulz, Andreas S. A1 - Weismantel, Robert A1 - Ziegler, Günter M. T1 - 0/1-Integer Programming: Optimization and Augmentation are Equivalent N2 - {\def\xnew{x^{\mbox{\tiny new}}}\def\Z{{{\rm Z}\!\! Z}}For every fixed set ${\cal F}\subseteq\{0,1\}^n$ the following problems are strongly polynomial time equivalent: given a feasible point $x\in\cal F$ and a linear objective function $c\in\Z^n$, \begin{itemize} \item find a feasible point $x^*\in\cal F$ that maximizes $cx$ (Optimization), \item find a feasible point $\xnew\in\cal F$ with $c\xnew>cx$ (Augmentation), and \item find a feasible point $\xnew\in\cal F$ with $c\xnew>cx$ such that $\xnew-x$ is ``irreducible''\\(Irreducible Augmentation). \end{itemize} This generalizes results and techniques that are well known for $0/1$--integer programming problems that arise from various classes of combinatorial optimization problems.} T3 - ZIB-Report - SC-95-08 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1744 ER - TY - GEN A1 - Thomas, Rekha R. A1 - Weismantel, Robert T1 - Truncated Gröbner Bases for Integer Programming N2 - {\def\N{{\mbox{{\rm I\kern-0.22emN}}}}In this paper we introduce a multivariate grading of the toric ideal associated with the integer program $min \{ cx : Ax = b, x \in \N^n \}$, and a truncated Buchberger algorithm to solve the program. In the case of $max \{ cx : Ax \leq b, x \leq u, x \in \N^n \}$ in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in UWZ94}. T3 - ZIB-Report - SC-95-09 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1750 ER - TY - GEN A1 - Sturmfels, Bernd A1 - Weismantel, Robert A1 - Ziegler, Günter M. T1 - Gröbner bases of lattices, corner polyhedra, and integer programming N2 - We investigate the generating sets (``Gröbner bases'') of integer lattices which correspond to the Gröbner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gröbner basis in terms of the vertices and edges of the associated corner polyhedra. We emphasize the special case where the lattice has finite index. In this case the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming'' Schrijver, p.~363. We present exponential lower and upper bounds for the size of a reduced Gröbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron. T3 - ZIB-Report - SC-94-26 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1548 ER - TY - GEN A1 - Urbaniak, Regina A1 - Weismantel, Robert A1 - Ziegler, Günter M. T1 - A New Variant of Buchberger's Algorithm for Integer Programming N2 - In this paper we modify Buchberger's $S$-pair reduction algorithm for computing a Gröbner basis of a toric ideal so as to apply to an integer program in inequality form with fixed right hand sides and fixed upper bounds on the variables. We formulate the algorithm in the original space and interpret the reduction steps geometrically. In fact, three variants of this algorithm are presented and we give elementary proofs for their correctness. A relationship between these (exact) algorithms, iterative improvement heuristics and the Kernighan-Lin procedure is established. T3 - ZIB-Report - SC-94-29 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1570 ER - TY - GEN A1 - Pochet, Yves A1 - Weismantel, Robert T1 - The Sequential Knapsack Polytope N2 - In this paper we describe the convex hull of all solutions of the integer bounded knapsack problem in the special case when the weights of the items are divisible. The corresponding inequalities are defined via an inductive scheme that can also be used in a more general setting. T3 - ZIB-Report - SC-94-30 Y1 - 1994 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-1588 ER -