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 -